More Like this

1. Quasi-polynomial time approximation schemes for the Maximum Weight Independent Set Problem in H-free graphs

   https://doi.org/10.1137/1.9781611975994.139  

   Chudnovsky, Maria.; Pillipczuk, Marcin.; Pillipczuk, Mihal; and Thomasse, Stephan. (April 2020, Proceedings of the annual ACMSIAM symposium on discrete algorithms)

   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. That is, we show that for every graph H for which Maximum Independent Set is not known to be APX-hard in H-free graphs, the problem admits a quasi-polynomial time approximation scheme in this graph class. Our algorithm works also 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. 

   more » « less
2. Polynomial-time algorithm for Maximum Independent Set in bounded-degree graphs with no long induced claws

   Chudnovsky, M. with (January 2022, 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA))

   For graphs G and H, we say that G is H-free if it does not contain H as an induced subgraph. Already in the early 1980s Alekseev observed that if H is connected, then the Max Weight Independent Set problem (MWIS) remains NP-hard in H-free graphs, unless H is a path or a subdivided claw, i.e., a graph obtained from the three-leaf star by subdividing each edge some number of times (possibly zero). Since then determining the complexity of MWIS in these remaining cases is one of the most important problems in algorithmic graph theory. A general belief is that the problem is polynomial-time solvable, which is witnessed by algorithmic results for graphs excluding some small paths or subdivided claws. A more conclusive evidence was given by the recent breakthrough result by Gartland and Lokshtanov [FOCS 2020]: They proved that MWIS can be solved in quasipolynomial time in H-free graphs, where H is any fixed path. If H is an arbitrary subdivided claw, we know much less: The problem admits a QPTAS and a subexponential-time algorithm [Chudnovsky et al., SODA 2019]. In this paper we make an important step towards solving the problem by showing that for any subdivided claw H, MWIS is polynomial-time solvable in H-free graphs of bounded degree. 

   more » « less
3. Complexity of Ck-Coloring in Hereditary Classes of Graphs

   Chudnovsky, M.; Huang, S.; Rzazewski, P.; Spirkl, S.; and Zhong, M. (September 2019, European Symposium on Algorithms)

   For a graph F, a graph G is F-free if it does not contain an induced subgraph isomorphic to F. For two graphs G and H, an H-coloring of G is a mapping f : V (G) → V (H) such that for every edge uv ∈ E(G) it holds that f(u)f(v) ∈ E(H). We are interested in the complexity of the problem H-Coloring, which asks for the existence of an H-coloring of an input graph G. In particular, we consider H-Coloring of F-free graphs, where F is a fixed graph and H is an odd cycle of length at least 5. This problem is closely related to the well known open problem of determining the complexity of 3-Coloring of Pt-free graphs. We show that for every odd k ≥ 5 the Ck-Coloring problem, even in the precoloring-extension variant, can be solved in polynomial time in P9-free graphs. On the other hand, we prove that the extension version of Ck-Coloring is NP-complete for F-free graphs whenever some component of F is not a subgraph of a subdivided claw. 

   more » « less
4. Submodular Functions and Perfect Graphs

   https://doi.org/10.1287/moor.2021.0302  

   Abrishami, Tara; Chudnovsky, Maria; Dibek, Cemil; Vušković, Kristina (February 2025, Mathematics of Operations Research)

   We give a combinatorial polynomial-time algorithm to find a maximum weight independent set in perfect graphs of bounded degree that do not contain a prism or a hole of length four as an induced subgraph. An even pair in a graph is a pair of vertices all induced paths between which are even. An even set is a set of vertices every two of which are an even pair. We show that every perfect graph that does not contain a prism or a hole of length four as an induced subgraph has a balanced separator which is the union of a bounded number of even sets, where the bound depends only on the maximum degree of the graph. This allows us to solve the maximum weight independent set problem using the well-known submodular function minimization algorithm. Funding: This work was supported by the Engineering and Physical Sciences Research Council [Grant EP/V002813/1]; the National Science Foundation [Grants DMS-1763817, DMS-2120644, and DMS-2303251]; and Alexander von Humboldt-Stiftung. 

   more » « less
5. Induced subgraphs and tree decompositions XII. Grid theorem for pinched graphs

   https://doi.org/10.5802/igt.6  

   Alecu, Bogdan; Chudnovsky, Maria; Hajebi, Sepehr; Spirkl, Sophie (January 2025, Innovations in Graph Theory)

   Given c ∈ N, we say a graph G is c-pinched if G does not contain an induced subgraph consisting of c cycles, all going through a single common vertex and otherwise pairwise disjoint and with no edges between them. What can be said about the structure of c-pinched graphs? For instance, 1-pinched graphs are exactly graphs of treewidth 1. However, bounded treewidth for c > 1 is immediately seen to be a false hope because complete graphs, complete bipartite graphs, subdivided walls and line graphs of subdivided walls are all examples of 2-pinched graphs with arbitrarily large treewidth. There is even a fifth obstruction for larger values of c, discovered by Pohoata and later independently by Davies, consisting of 3-pinched graphs with unbounded treewidth and no large induced subgraph isomorphic to any of the first four obstructions. We fuse the above five examples into a grid-type theorem fully describing the unavoidable induced subgraphs of pinched graphs with large treewidth. More precisely, we prove that for every c ∈ N, a c-pinched graph G has large treewidth if and only if G contains one of the following as an induced subgraph: a large complete graph, a large complete bipartite graph, a subdivision of a large wall, the line graph of a subdivision of a large wall, or a large graph from the Pohoata-Davies construction. Our main result also generalizes to an extension of pinched graphs where the lengths of excluded cycles are lower-bounded. 

   more » « less