Search

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 long-standing 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\in C with vertex weights and an integer k, one can, in time, n\scrO (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., 31 (2001), pp. 212--232] and extended by Fomin, Todinca, and Villanger [SIAM J. Comput., 44 (2015), pp. 54--87], this framework allows us to solve a wide 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 [Lokshtanov, Vatshelle, and Villanger, SODA 2014, pp. 570--581] or P6-free graphs [Grzesik, Klimo\v sov\'a, Pilipczuk, and Pilipczuk, ACM Trans. Algorithms, 18 (2022), pp. 4:1--4:57]), 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 PMC: a superset of the maximal clique that intersects the sought solution only in the vertices of the PMC. This strengthening of the framework not only allows us to obtain our main result but also leads to significant simplifications of the reasoning in previous papers. [ABSTRACT FROM AUTHOR]

In the Maximum Independent Set problem we are asked to find a set of pairwise nonadjacent vertices in a given graph with the maximum possible cardinality. In general graphs, this classical problem is known to be NP-hard and hard to approximate within a factor of n1-ε for any ε> 0. Due to this, investigating the complexity of Maximum Independent Set in various graph classes in hope of finding better tractability results is an active research direction. In H-free graphs, that is, graphs not containing a fixed graph H as an induced subgraph, the problem is known to remain NP-hard and APX-hard whenever H contains a cycle, a vertex of degree at least four, or two vertices of degree at least three in one connected component. For the remaining cases, where every component of H is a path or a subdivided claw, the complexity of Maximum Independent Set remains widely open, with only a handful of polynomial-time solvability results for small graphs H such as P5, P6, the claw, or the fork. We prove that for every such "possibly tractable" graph H there exists an algorithm that, given an H-free graph G and an accuracy parameter ε> 0, finds an independent set in G of cardinality within a factor of (1 - ε) of the optimum in time exponential in a polynomial of log | V (G)| and ε-1. Furthermore, an independent set of maximum size can be found in subexponential time 2\scrO (| V (G)| 8/9| V (G)|). That is, we show that for every graph H for which Maximum Independent Set is not known to be APX-hard and SUBEXP-hard in H-free graphs, the problem admits a quasi-polynomial time approximation scheme and a subexponential-time exact algorithm in this graph class. Our algorithms also work in the more general weighted setting, where the input graph is supplied with a weight function on vertices and we are maximizing the total weight of an independent set. [ABSTRACT FROM AUTHOR]