Tight Lower Bounds for Problems Parameterized by Rank-Width
Publication date
2023-03-01
Authors
Bergougnoux, Benjamin
Korhonen, Tuukka
Nederlof, Jesper
Editors
Berenbrink, Petra
Bouyer, Patricia
Dawar, Anuj
Kanté, Mamadou Moustapha
Advisors
Supervisors
Document Type
Part of book
Metadata
Show full item recordCollections
License
cc_by
Abstract
We show that there is no 2o(k2)nO(1) time algorithm for Independent Set on n-vertex graphs with rank-width k, unless the Exponential Time Hypothesis (ETH) fails. Our lower bound matches the 2O(k2)nO(1) time algorithm given by Bui-Xuan, Telle, and Vatshelle [Discret. Appl. Math., 2010] and it answers the open question of Bergougnoux and Kanté [SIAM J. Discret. Math., 2021]. We also show that the known 2O(k2)nO(1) time algorithms for Weighted Dominating Set, Maximum Induced Matching and Feedback Vertex Set parameterized by rank-width k are optimal assuming ETH. Our results are the first tight ETH lower bounds parameterized by rank-width that do not follow directly from lower bounds for n-vertex graphs.
Keywords
Boolean-width, dominating set, exponential time hypothesis, feedback vertex set, independent set, maximum induced matching, parameterized algorithms, rank-width, Software
Citation
Bergougnoux, B, Korhonen, T & Nederlof, J 2023, Tight Lower Bounds for Problems Parameterized by Rank-Width. in P Berenbrink, P Bouyer, A Dawar & M M Kanté (eds), 40th International Symposium on Theoretical Aspects of Computer Science, STACS 2023. vol. 254, 11, Leibniz International Proceedings in Informatics, LIPIcs, vol. 254, Schloss Dagstuhl – Leibniz-Zentrum für Informatik GmbH, pp. 11:1-11:17. https://doi.org/10.4230/LIPIcs.STACS.2023.11