Tight Lower Bounds for Problems Parameterized by Rank-Width

Benjamin Bergougnoux; Tuukka Korhonen; Jesper Nederlof

doi:10.4230/LIPIcs.STACS.2023.11

Tight Lower Bounds for Problems Parameterized by Rank-Width

Benjamin Bergougnoux, Tuukka Korhonen, Jesper Nederlof

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

Abstract

We show that there is no 2^o⁽^k²⁾n^O⁽¹⁾ 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 2^O⁽^k²⁾n^O⁽¹⁾ 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 2^O⁽^k²⁾n^O⁽¹⁾ 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.

Original language	English
Title of host publication	40th International Symposium on Theoretical Aspects of Computer Science, STACS 2023
Editors	Petra Berenbrink, Patricia Bouyer, Anuj Dawar, Mamadou Moustapha Kanté
Publisher	Schloss Dagstuhl – Leibniz-Zentrum für Informatik GmbH
Pages	11:1-11:17
Volume	254
ISBN (Electronic)	9783959772662
DOIs	https://doi.org/10.4230/LIPIcs.STACS.2023.11
Publication status	Published - 1 Mar 2023

Publication series

Name	Leibniz International Proceedings in Informatics, LIPIcs
Volume	254
ISSN (Print)	1868-8969

Bibliographical note

Funding Information:
Funding Tuukka Korhonen: Supported by the Research Council of Norway via the project BWCA (grant no. 314528). Jesper Nederlof : Supported by the project CRACKNP that has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 853234).

Funding Information:
Funding Tuukka Korhonen: Supported by the Research Council of Norway via the project BWCA (grant no. 314528). Jesper Nederlof: Supported by the project CRACKNP that has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation pro-gramme (grant agreement No 853234).

Publisher Copyright:
© Benjamin Bergougnoux, Tuukka Korhonen, and Jesper Nederlof.

Keywords

Boolean-width
dominating set
exponential time hypothesis
feedback vertex set
independent set
maximum induced matching
parameterized algorithms
rank-width

Access to Document

10.4230/LIPIcs.STACS.2023.11Licence: CC BY

LIPIcs-STACS-2023-11Final published version, 1.19 MBLicence: CC BY

https://doi.org/10.4230/LIPIcs.STACS.2023.11

Cite this

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, pp. 11:1-11:17). Article 11 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 254). Schloss Dagstuhl – Leibniz-Zentrum für Informatik GmbH. https://doi.org/10.4230/LIPIcs.STACS.2023.11

Bergougnoux, Benjamin ; Korhonen, Tuukka ; Nederlof, Jesper. / Tight Lower Bounds for Problems Parameterized by Rank-Width. 40th International Symposium on Theoretical Aspects of Computer Science, STACS 2023. editor / Petra Berenbrink ; Patricia Bouyer ; Anuj Dawar ; Mamadou Moustapha Kanté. Vol. 254 Schloss Dagstuhl – Leibniz-Zentrum für Informatik GmbH, 2023. pp. 11:1-11:17 (Leibniz International Proceedings in Informatics, LIPIcs).

@inproceedings{2778e14538704042b20d78f129f12c37,

title = "Tight Lower Bounds for Problems Parameterized by Rank-Width",

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{\'e} [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",

author = "Benjamin Bergougnoux and Tuukka Korhonen and Jesper Nederlof",

note = "Funding Information: Funding Tuukka Korhonen: Supported by the Research Council of Norway via the project BWCA (grant no. 314528). Jesper Nederlof : Supported by the project CRACKNP that has received funding from the European Research Council (ERC) under the European Union{\textquoteright}s Horizon 2020 research and innovation programme (grant agreement No 853234). Funding Information: Funding Tuukka Korhonen: Supported by the Research Council of Norway via the project BWCA (grant no. 314528). Jesper Nederlof: Supported by the project CRACKNP that has received funding from the European Research Council (ERC) under the European Union{\textquoteright}s Horizon 2020 research and innovation pro-gramme (grant agreement No 853234). Publisher Copyright: {\textcopyright} Benjamin Bergougnoux, Tuukka Korhonen, and Jesper Nederlof.",

year = "2023",

month = mar,

day = "1",

doi = "10.4230/LIPIcs.STACS.2023.11",

language = "English",

volume = "254",

series = "Leibniz International Proceedings in Informatics, LIPIcs",

publisher = "Schloss Dagstuhl – Leibniz-Zentrum f{\"u}r Informatik GmbH",

pages = "11:1--11:17",

editor = "Petra Berenbrink and Patricia Bouyer and Anuj Dawar and Kant{\'e}, {Mamadou Moustapha}",

booktitle = "40th International Symposium on Theoretical Aspects of Computer Science, STACS 2023",

}

Bergougnoux, B, Korhonen, T & Nederlof, J 2023, Tight Lower Bounds for Problems Parameterized by Rank-Width. in P Berenbrink, P Bouyer, A Dawar & MM 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

Tight Lower Bounds for Problems Parameterized by Rank-Width. / Bergougnoux, Benjamin; Korhonen, Tuukka; Nederlof, Jesper.
40th International Symposium on Theoretical Aspects of Computer Science, STACS 2023. ed. / Petra Berenbrink; Patricia Bouyer; Anuj Dawar; Mamadou Moustapha Kanté. Vol. 254 Schloss Dagstuhl – Leibniz-Zentrum für Informatik GmbH, 2023. p. 11:1-11:17 11 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 254).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Tight Lower Bounds for Problems Parameterized by Rank-Width

AU - Bergougnoux, Benjamin

AU - Korhonen, Tuukka

AU - Nederlof, Jesper

N1 - Funding Information: Funding Tuukka Korhonen: Supported by the Research Council of Norway via the project BWCA (grant no. 314528). Jesper Nederlof : Supported by the project CRACKNP that has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 853234). Funding Information: Funding Tuukka Korhonen: Supported by the Research Council of Norway via the project BWCA (grant no. 314528). Jesper Nederlof: Supported by the project CRACKNP that has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation pro-gramme (grant agreement No 853234). Publisher Copyright: © Benjamin Bergougnoux, Tuukka Korhonen, and Jesper Nederlof.

PY - 2023/3/1

Y1 - 2023/3/1

N2 - 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.

AB - 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.

KW - Boolean-width

KW - dominating set

KW - exponential time hypothesis

KW - feedback vertex set

KW - independent set

KW - maximum induced matching

KW - parameterized algorithms

KW - rank-width

UR - http://www.scopus.com/inward/record.url?scp=85149823300&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.STACS.2023.11

DO - 10.4230/LIPIcs.STACS.2023.11

M3 - Conference contribution

VL - 254

T3 - Leibniz International Proceedings in Informatics, LIPIcs

SP - 11:1-11:17

BT - 40th International Symposium on Theoretical Aspects of Computer Science, STACS 2023

A2 - Berenbrink, Petra

A2 - Bouyer, Patricia

A2 - Dawar, Anuj

A2 - Kanté, Mamadou Moustapha

PB - Schloss Dagstuhl – Leibniz-Zentrum für Informatik GmbH

ER -

Bergougnoux B, Korhonen T, Nederlof J. Tight Lower Bounds for Problems Parameterized by Rank-Width. In Berenbrink P, Bouyer P, Dawar A, Kanté MM, editors, 40th International Symposium on Theoretical Aspects of Computer Science, STACS 2023. Vol. 254. Schloss Dagstuhl – Leibniz-Zentrum für Informatik GmbH. 2023. p. 11:1-11:17. 11. (Leibniz International Proceedings in Informatics, LIPIcs). doi: 10.4230/LIPIcs.STACS.2023.11

Tight Lower Bounds for Problems Parameterized by Rank-Width

Abstract

Publication series

Bibliographical note

Keywords

Access to Document

Other files and links

Fingerprint

Cite this