TY - GEN
T1 - Induced subgraphs of bounded treewidth and the container method
AU - Abrishami, Tara
AU - Chudnovsky, Maria
AU - Pilipczuk, Marcin
AU - Rzążewski, Paweł
AU - Seymour, Paul
N1 - Publisher Copyright: Copyright © 2021 by SIAM
PY - 2021
Y1 - 2021
N2 - A hole in a graph is an induced cycle of length at least 4. A hole is long if its length is at least 5. By Pt we denote a path on t vertices. In this paper we give polynomial-time algorithms for the following problems: • the Maximum Weight Independent Set problem in long-hole-free graphs, and • the Feedback Vertex Set problem in P5-free graphs. Each of the above results resolves a corresponding longstanding open problem. An extended C5 is a five-vertex hole with an additional vertex adjacent to one or two consecutive vertices of the hole. Let C be the class of graphs excluding an extended C5 and holes of length at least 6 as induced subgraphs; C contains all long-hole-free graphs and all P5-free graphs. We show that, given an n-vertex graph G ∈ C with vertex weights and an integer k, one can in time nO(k) find a maximum-weight induced subgraph of G of treewidth less than k. This implies both aforementioned results. To achieve this goal, we extend the framework of potential maximal cliques (PMCs) to containers. Developed by Bouchitté and Todinca [SIAM J. Comput. 2001] and extended by Fomin, Todinca, and Villanger [SIAM J. Comput. 2015], this framework allows to solve high variety of tasks, including finding a maximum-weight induced subgraph of treewidth less than k for fixed k, in time polynomial in the size of the graph and the number of potential maximal cliques. Further developments, tailored to solve the Maximum Weight Independent Set problem within this framework (e.g., for P5-free [SODA 2014] or P6-free graphs [SODA 2019]), enumerate only a specifically chosen subset of all PMCs of a graph. In all aforementioned works, the final step is an involved dynamic programming algorithm whose state space is based on the considered list of PMCs. Here we modify the dynamic programming algorithm and show that it is sufficient to consider only a container for each potential maximal clique: a superset of the maximal clique that intersects the sought solution only in the vertices of the potential maximal clique. This strengthening of the framework not only allows us to obtain our main result, but also leads to significant simplifications of reasonings in previous papers.
AB - A hole in a graph is an induced cycle of length at least 4. A hole is long if its length is at least 5. By Pt we denote a path on t vertices. In this paper we give polynomial-time algorithms for the following problems: • the Maximum Weight Independent Set problem in long-hole-free graphs, and • the Feedback Vertex Set problem in P5-free graphs. Each of the above results resolves a corresponding longstanding open problem. An extended C5 is a five-vertex hole with an additional vertex adjacent to one or two consecutive vertices of the hole. Let C be the class of graphs excluding an extended C5 and holes of length at least 6 as induced subgraphs; C contains all long-hole-free graphs and all P5-free graphs. We show that, given an n-vertex graph G ∈ C with vertex weights and an integer k, one can in time nO(k) find a maximum-weight induced subgraph of G of treewidth less than k. This implies both aforementioned results. To achieve this goal, we extend the framework of potential maximal cliques (PMCs) to containers. Developed by Bouchitté and Todinca [SIAM J. Comput. 2001] and extended by Fomin, Todinca, and Villanger [SIAM J. Comput. 2015], this framework allows to solve high variety of tasks, including finding a maximum-weight induced subgraph of treewidth less than k for fixed k, in time polynomial in the size of the graph and the number of potential maximal cliques. Further developments, tailored to solve the Maximum Weight Independent Set problem within this framework (e.g., for P5-free [SODA 2014] or P6-free graphs [SODA 2019]), enumerate only a specifically chosen subset of all PMCs of a graph. In all aforementioned works, the final step is an involved dynamic programming algorithm whose state space is based on the considered list of PMCs. Here we modify the dynamic programming algorithm and show that it is sufficient to consider only a container for each potential maximal clique: a superset of the maximal clique that intersects the sought solution only in the vertices of the potential maximal clique. This strengthening of the framework not only allows us to obtain our main result, but also leads to significant simplifications of reasonings in previous papers.
UR - http://www.scopus.com/inward/record.url?scp=85105309396&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85105309396&partnerID=8YFLogxK
U2 - 10.1137/1.9781611976465.116
DO - 10.1137/1.9781611976465.116
M3 - Conference contribution
T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
SP - 1948
EP - 1964
BT - ACM-SIAM Symposium on Discrete Algorithms, SODA 2021
A2 - Marx, Daniel
PB - Association for Computing Machinery
T2 - 32nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2021
Y2 - 10 January 2021 through 13 January 2021
ER -