Abstract
It has long been known that Feedback Vertex Set can be solved in time \(2^{{\mathcal {O}}(w\log w)}n^{{\mathcal {O}}(1)}\) on n-vertex graphs of treewidth w, but it was only recently that this running time was improved to \(2^{{\mathcal {O}}(w)}n^{{\mathcal {O}}(1)}\), that is, to single-exponential parameterized by treewidth. We investigate which generalizations of Feedback Vertex Set can be solved in a similar running time. Formally, for a class \({\mathcal {P}}\) of graphs, the Bounded\({\mathcal {P}}\)-Block Vertex Deletion problem asks, given a graph G on n vertices and positive integers k and d, whether G contains a set S of at most k vertices such that each block of \(G-S\) has at most d vertices and is in \({\mathcal {P}}\). Assuming that \({\mathcal {P}}\) is recognizable in polynomial time and satisfies a certain natural hereditary condition, we give a sharp characterization of when single-exponential parameterized algorithms are possible for fixed values of d:
-
if \({\mathcal {P}}\) consists only of chordal graphs, then the problem can be solved in time \(2^{{\mathcal {O}}(wd^2)} n^{{\mathcal {O}}(1)}\),
-
if \({\mathcal {P}}\) contains a graph with an induced cycle of length \(\ell \geqslant 4\), then the problem is not solvable in time \(2^{o(w\log w)} n^{{\mathcal {O}}(1)}\) even for fixed \(d=\ell \), unless the ETH fails.
We also study a similar problem, called Bounded\({\mathcal {P}}\)-Component Vertex Deletion, where the target graphs have connected components of small size rather than blocks of small size, and we present analogous results. For this problem, we also show that if d is part of the input and \({\mathcal {P}}\) contains all chordal graphs, then it cannot be solved in time \(f(w)n^{o(w)}\) for some function f, unless the ETH fails.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Baste, J., Sau, I., Thilikos, D.M.: Optimal algorithms for hitting (topological) minors on graphs of bounded treewidth. In: 12th International Symposium on Parameterized and Exact Computation, volume 89 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 4:1–4:12 (2018)
Baste, J., Sau, I., Thilikos, D.M.: A complexity dichotomy for hitting small planar minors parameterized by treewidth. In: 13th International Symposium on Parameterized and Exact Computation, volume 115 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 2:1–2:13 (2019)
Bodlaender, H.L., Cygan, M., Kratsch, S., Nederlof, J.: Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth. Inf. Comput. 243, 86–111 (2015)
Bodlaender, H.L., Drange, P.G., Dregi, M.S., Fomin, F.V., Lokshtanov, D., Pilipczuk, M.: A \(c^k n\) 5-approximation algorithm for treewidth. SIAM J. Comput. 45(2), 317–378 (2016)
Bonnet, É., Brettell, N., Kwon, O., Marx, D.: Generalized feedback vertex set problems on bounded-treewidth graphs: chordality is the key to single-exponential parameterized algorithms. In: 12th International Symposium on Parameterized and Exact Computation, volume 89 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 7:1–7:13 (2018)
Bonnet, É., Brettell, N., Kwon, O., Marx, D.: Parameterized vertex deletion problems for hereditary graph classes with a block property. In: Graph-Theoretic Concepts in Computer Science, volume 9941 of Lecture Notes in Computer Science, pp. 233–244 (2016)
Courcelle, B.: The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Inf. Comput. 85(1), 12–75 (1990)
Cygan, M., Fomin, F.V., Kowalik, Ł., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Berlin (2015)
Cygan, M., Nederlof, J., Pilipczuk, M., Pilipczuk, M., van Rooij, J.M.M., Wojtaszczyk, J.O.: Solving connectivity problems parameterized by treewidth in single exponential time. In: 52nd Annual Symposium on Foundations of Computer Science, pp. 150–159 (2011)
Drange, P.G., Dregi, M., van ’t Hof, P.: On the computational complexity of vertex integrity and component order connectivity. Algorithmica 76(4), 1181–1202 (2016)
Enright, J., Meeks, K.: Deleting edges to restrict the size of an epidemic: a new application for treewidth. In: Combinatorial Optimization and Applications, volume 9486 of Lecture Notes in Computer Science, pp. 574–585. Springer (2015)
Fellows, M.R., Fomin, F.V., Lokshtanov, D., Rosamond, F., Saurabh, S., Szeider, S., Thomassen, C.: On the complexity of some colorful problems parameterized by treewidth. Inf. Comput. 209(2), 143–153 (2011)
Fomin, F.V., Lokshtanov, D., Panolan, F., Saurabh, S.: Efficient computation of representative families with applications in parameterized and exact algorithms. J. ACM 63(4), 60 (2016). Art. 29
Lokshtanov, D., Marx, D., Saurabh, S.: Lower bounds based on the exponential time hypothesis. Bull. EATCS 105, 41–72 (2011)
Lokshtanov, D., Marx, D., Saurabh, S.: Known algorithms on graphs of bounded treewidth are probably optimal. ACM Trans. Algorithms 14(2), 30 (2018). Art. 13
Lokshtanov, D., Marx, D., Saurabh, S.: Slightly superexponential parameterized problems. SIAM J. Comput. 47(3), 675–702 (2018)
Marx, D.: Can you beat treewidth? Theory Comput. 6(1), 85–112 (2010)
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
All authors were supported by ERC Starting Grant PARAMTIGHT (No. 280152). O-joung Kwon was supported by the National Research Foundation of Korea (NRF) Grant funded by the Ministry of Education (No. NRF-2018R1D1A1B07050294). Dániel Marx was supported by ERC Consolidator Grant SYSTEMATICGRAPH (No. 725978).
An extended abstract appeared in Proceedings of the 12th International Symposium on Parameterized and Exact Computations, 2017 [5]. The corresponding author is O-joung Kwon.
Rights and permissions
About this article
Cite this article
Bonnet, É., Brettell, N., Kwon, Oj. et al. Generalized Feedback Vertex Set Problems on Bounded-Treewidth Graphs: Chordality is the Key to Single-Exponential Parameterized Algorithms. Algorithmica 81, 3890–3935 (2019). https://doi.org/10.1007/s00453-019-00579-4
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00453-019-00579-4