1 results
Approximation Algorithm and FPT Algorithm for Connected-k-Subgraph Cover on Minor-Free Graphs
-
- Journal:
- Mathematical Structures in Computer Science / Volume 34 / Issue 3 / March 2024
- Published online by Cambridge University Press:
- 10 January 2024, pp. 180-192
-
- Article
-
- You have access
- HTML
- Export citation
-
Given a graph G, the minimum Connected-k-Subgraph Cover problem (MinCkSC) is to find a minimum vertex subset C of G such that every connected subgraph of G on k vertices has at least one vertex in C. If furthermore the subgraph of G induced by C is connected, then the problem is denoted as MinCkSC
$_{con}$. In this paper, we first present a PTAS for MinCkSC on an H-minor-free graph, where H is a graph with a constant number of vertices. Then, we design an 
$O((\omega+1)(2(k-1)(\omega+2))^{3\omega+3})|V|$-time FPT algorithm for MinCkSC
$_{con}$ on a graph with treewidth 
$\omega$, based on which we further design an 
$O(2^{O(\sqrt{t}\log t)}|V|^{O(1)})$ time subexponential FPT algorithm for MinCkSC
$_{con}$ on an H-minor-free graph, where t is an upper bound of solution size.
