×

Fast exact algorithms for some connectivity problems parameterized by clique-width. (English) Zbl 1423.68328

Summary: Given a clique-width \(k\)-expression of a graph \(G\), we provide \(2^{O(k)} \cdot n\) time algorithms for connectivity constraints on locally checkable properties such as Node-Weighted Steiner Tree, Connected Dominating Set, or Connected Vertex Cover. We also propose a \(2^{O(k)} \cdot n\) time algorithm for Feedback Vertex Set. The best running times for all the considered problems were \(2^{O(k \cdot \log(k))} \cdot n^{O(1)}\).

MSC:

68R10 Graph theory (including graph drawing) in computer science
05C40 Connectivity
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Bergougnoux, Benjamin; Kanté, Mamadou Moustapha, Rank based approach on graphs with structured neighborhood (2018), CoRR
[2] Bodlaender, Hans L.; Cygan, Marek; Kratsch, Stefan; Nederlof, Jesper, Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth, Inform. and Comput., 243, 86-111 (2015) · Zbl 1327.68126
[3] Bui-Xuan, Binh-Minh; Suchý, Ondřej; Telle, Jan Arne; Vatshelle, Martin, Feedback vertex set on graphs of low clique-width, European J. Combin., 34, 3, 666-679 (2013) · Zbl 1257.05165
[4] Bui-Xuan, Binh-Minh; Telle, Jan Arne; Vatshelle, Martin, Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems, Theoret. Comput. Sci., 511, 66-76 (2013) · Zbl 1408.68111
[5] Courcelle, Bruno; Engelfriet, Joost, Graph Structure and Monadic Second-Order Logic, Encyclopedia Math. Appl., vol. 138 (2012), Cambridge University Press: Cambridge University Press Cambridge, A language-theoretic approach, With a foreword by Maurice Nivat · Zbl 1257.68006
[6] Courcelle, Bruno; Engelfriet, Joost; Rozenberg, Grzegorz, Handle-rewriting hypergraph grammars, J. Comput. System Sci., 46, 2, 218-270 (1993) · Zbl 0825.68446
[7] Courcelle, Bruno; Olariu, Stephan, Upper bounds to the clique width of graphs, Discrete Appl. Math., 101, 1-3, 77-114 (2000) · Zbl 0958.05105
[8] Cygan, Marek; Nederlof, Jesper; Pilipczuk, Marcin; Pilipczuk, Michał; van Rooij, Johan M. M.; Wojtaszczyk, Jakub Onufry, Solving connectivity problems parameterized by treewidth in single exponential time (extended abstract), (2011 IEEE 52nd Annual Symposium on Foundations of Computer Science—FOCS 2011 (2011), IEEE Computer Soc.: IEEE Computer Soc. Los Alamitos, CA), 150-159 · Zbl 1292.68122
[9] Diestel, Reinhard, Graph Theory, Grad. Texts in Math., vol. 173 (2005), Springer · Zbl 1074.05001
[10] Downey, Rodney G.; Fellows, Michael R., Fundamentals of Parameterized Complexity, Texts Comput. Sci. (2013), Springer: Springer London · Zbl 1358.68006
[13] Ganian, Robert; Hliněný, Petr, On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width, Discrete Appl. Math., 158, 7, 851-867 (2010) · Zbl 1231.05096
[14] Ganian, Robert; Hliněný, Petr; Obdržálek, Jan, Clique-width: when hard does not mean impossible, (28th International Symposium on Theoretical Aspects of Computer Science. 28th International Symposium on Theoretical Aspects of Computer Science, LIPIcs. Leibniz Int. Proc. Inform., vol. 9 (2011), Schloss Dagstuhl. Leibniz-Zent. Inform.: Schloss Dagstuhl. Leibniz-Zent. Inform. Wadern), 404-415 · Zbl 1230.68109
[15] Impagliazzo, Russell; Paturi, Ramamohan, On the complexity of k-sat, J. Comput. System Sci., 62, 2, 367-375 (2001) · Zbl 0990.68079
[16] Oum, Sang-Il, Approximating rank-width and clique-width quickly, ACM Trans. Algorithms, 5, 1, Article 10 pp. (2009), 20 · Zbl 1451.05231
[17] Oum, Sang-il; Sæther, Sigve Hortemo; Vatshelle, Martin, Faster algorithms for vertex partitioning problems parameterized by clique-width, Theoret. Comput. Sci., 535, 16-24 (2014) · Zbl 1419.05204
[19] Robertson, Neil; Seymour, Paul D., Graph minors. II. Algorithmic aspects of tree-width, J. Algorithms, 7, 3, 309-322 (1986) · Zbl 0611.05017
[20] Telle, Jan Arne; Proskurowski, Andrzej, Algorithms for vertex partitioning problems on partial \(k\)-trees, SIAM J. Discrete Math., 10, 4, 529-550 (1997) · Zbl 0885.68118
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.