English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Treewidth is a useful tool in designing graph algorithms. Although manyNP-hard graph problems can be solved in linear time when the input graphs havesmall treewidth, there are problems which remain hard on graphs of boundedtreewidth. In this paper, we consider three vertex selection problems that areW[1]-hard when parameterized by the treewidth of the input graph, namely thecapacitated vertex cover problem, the target set selection problem and thevector dominating set problem. We provide two new methods to obtain FPTapproximation algorithms for these problems. For the capacitated vertex coverproblem and the vector dominating set problem, we obtain$(1+o(1))$-approximation FPT algorithms. For the target set selection problem,we give an FPT algorithm providing a tradeoff between its running time and theapproximation ratio.

FPT Approximation using Treewidth: Capacitated Vertex Cover, Target Set Selection and Vector Dominating Set