betaFeedback

WorksMathematics

Induced matching treewidth in classes with a forbidden structure

Abstract

Induced matching treewidth is a tree-decomposition based parameter where we bound the size of an induced matching whose every edge intersects a single bag of the decomposition. It is known that many computational problems can be solved efficiently in graphs of bounded induced matching treewidth. In this paper we are interested in understanding what classes of graphs have bounded induced matching treewidth. We provide dichotomy theorems for all classes defined by excluding a single graph with respect to six basic containment relations: (induced) subgraph, (induced) topological minor, and (induced) minor. Furthermore, we study the case where the input graph has minimum degree at least 2, as well as the more restrictive case where it is 2-connected. This can be assumed without loss of generality for many computational problems. It turns out that for classes excluding some graph as an induced minor, this restrictions yield some new cases of bounded induced matching treewidth. As a consequence, our results imply new algorithmic results, as well as the existence of balanced separators dominated by a constant number of vertices in the considered classes. This confirms some special cases of two conjectures of Gartland and Lokshtanov.

Introduction

Graph decompositions are a general set of tools that allow us to break graphs into smaller pieces, connected to each other in somewhat restricted way. One of the motivations behind this line of study is algorithmic: many computational problems can often be solved using some kind of dynamic programming over a decomposition, and the “complexity” (usually referred to as width) of the decompositions restricts the number of states one needs to consider.

Arguably, the best known type of graph decompositions are tree decompositions, discovered independently by several groups of authors with different motivations [4, 6, 38, 47]. Intuitively, a tree decomposition of a graph GG is a tree TT whose vertices (typically called nodes) are equipped with subsets of the vertex set of GG, called bags, so that the general structure of GG is reflected by the structure of TT. If each bag is “simple,” then the whole graph is considered “simple.” Perhaps the most straightforward notion of simplicity is constant size. This leads to the definition of treewidth: a graph has treewidth kk if it admits a tree decomposition whose every bag is of size less than kk. Consequently, if a graph has small treewidth, then it “resembles a tree.”

The drawback of treewidth is that its boundedness implies that the graph is sparse, i.e., it has a linear number of edges. Thus, this parameter is not suitable for studying classes of “well-structured” dense graphs, like chordal graphs. As a remedy, in recent years there is a growing interest in structured tree decompositions where we do not aim to obtain small bags, but rather bags of “simple structure.” A motivating example is the class of chordal graphs mentioned above: they are precisely graphs that admit tree decompositions whose every bag is a clique. Such cliques can be arbitrarily large, but their structure is indeed rather simple.

A generalization of this idea is the tree-independence number (denoted by tree-α(G)\alpha(G)), introduced independently by Yolov [50] and by Dallard, Milanič, and Štorgel [27]. Here, for every bag of a tree decomposition, we measure the size of a largest independent set in the graph induced by the bag. In particular, chordal graphs are precisely graphs of tree-independence number 1. We remark that tree-independence number is always upper-bounded by treewidth (plus 1).

As already observed by Yolov [50], tree-independence number might still be large on graphs of simple structure, like complete bipartite graphs. Thus, he introduced another parameter, minor-matching hypertreewidth, which is now usually called induced matching treewidth and denoted by tree-μ(G)\mu(G). This time, for every bag of a tree decomposition, we measure the size of a largest induced matching whose every edge intersects the bag (note that the matching might not be contained in the bag). It is not hard to observe that induced matching treewidth never exceeds tree-independence number, but can be much smaller. In particular, bicliques have induced matching treewidth 1.

When introducing a new graph parameter, there are three important questions to have in mind:

(Q1) If the parameter is bounded, can we solve some interesting computational problems efficiently?

(Q2) If the parameter is bounded, can we compute a corresponding decomposition efficiently?

(Q3) Are there any interesting classes of graphs in which the parameter is bounded?

Let us briefly discuss the state of art concerning these three questions for tree-independence number and induced matching treewidth.

Concerning (Q1), Yolov [50] showed that some classic problems including Max Weight Independent Set (MWIS) and kk-Coloring are solvable in polynomial time for graphs given with a tree decomposition witnessing that tree-independence number or induced matching treewidth is bounded. Another family of problems that are tractable in the discussed setting concern packing induced subgraphs, possibly with distance constraints [27, 28]. Lima, Milanič, Murišić, Okrasa, Rzążewski, and Štorgel [28] showed that (tw⁡≤r,ψ)(\operatorname{tw} \le r,\psi)-MWIS, a wide generalization of MWIS (see § 10 for the definition) can be solved efficiently in classes of bounded tree-independence number (see also the refined version of this result [41]). The authors conjectured that the same holds for induced matching treewidth, supporting this with several partial results. The conjecture was recently confirmed by Bodlaender, Fomin, and Korhonen [8].

Concerning (Q2), already in the first paper introducing both parameters, Yolov [50] showed that both tree-independence number and induced matching treewidth admit XP-approximation algorithm with respect to the value of the parameter. More precisely, given an nn-vertex graph GG and an integer kk, in time nO(k3)n^{O(k^3)} one can compute a tree decomposition witnessing that tree⁡-α(G)=O(k3)\operatorname{tree}\text{-}\alpha(G)=O(k^3) (resp., tree⁡-μ(G)=O(k3)\operatorname{tree}\text{-}\mu(G)=O(k^3)) or conclude that the corresponding parameter is larger than kk. Later, Dallard, Fomin, Golovach, Korhonen, and Milanič [25] proposed a refined algorithm that runs in time 2O(k2)nO(k)2^{O(k^2)}n^{O(k)} and returns a tree decomposition showing that tree⁡-α(G)≤8k\operatorname{tree}\text{-}\alpha(G)\le8k or concludes tree⁡-α(G)>k\operatorname{tree}\text{-}\alpha(G)>k. Using a structural observation of Yolov [50] one can use this algorithm to obtain analogous results for induced matching treewidth [28].

Interestingly, this approach is essentially optimal (up to improving the constant 88 and the 2O(k2)2^{O(k^2)}-factor). In particular, known reductions [25] exclude an exact algorithm even for k=4k=4, as well as any FPT-approximation algorithm, under standard assumptions in complexity theory.

Classes considered in (Q3) are typically defined by excluding some graphs under one of the standard containment relations: as a subgraph, a topological minor, and a minor, as well as their induced counterparts, see § 2 for formal definitions of these relations. For a relation ⋆\star and a graph HH, we say that a graph GG is HH-⋆\star-free if it does not contain HH with respect to ⋆\star.

Dallard, Milanič, and Štorgel [26] studied tree-independence number in classes defined by forbidding a single graph under the relations mentioned above. For each of the six considered relations, they fully characterized graphs HH whose exclusion bounds tree-independence number, see Table 1. Since then, the classes of small tree-independence number have been a topic of investigation [1, 14, 15, 17].

Relationtree-α\alpha [26]tree-μ\mutree-μ\mu when δ≥2\delta\ge2
Subgraphdisjoint union of subdivided claws
Induced subgraphP3P_3 or edgelessP3P_3 or a matching
Topological minorplanar and subcubic
Minorplanar
Induced topological minorC4C_4, K4−K_4^-, or edgelessC4C_4, K^4−\widehat{K}_4^-, 1-tipi, or a matching
Induced minorK2,qK_{2,q} for some qq, W4W_4, K5−K_5^-, or edgelessK2,qK_{2,q} for some qq, W4W_4, K5−K_5^-, a tipi, or a matchingK2,qK_{2,q} for some qq, W4W_4, K5−K_5^-, or a windmill

Table 1. Maximal (w.r.t. a given containment relation) graphs whose exclusion (w.r.t. that relation) implies boundedness of tree-independence number or induced matching treewidth. In the last column we additionally assume that graphs have no vertices of degree at most 1.

On the other hand, very little is known about which classes have bounded induced matching treewidth. Let us mention that Abrishami, Briański, Czyżewska, McCarty, Rzążewski, and Walczak [2] showed that induced matching treewidth and tree-independence number are functionally equivalent for graphs that exclude some fixed biclique as an induced subgraph. However, for classes that contain arbitrarily large bicliques, we are not aware of any results.

Our results.

In this paper we initiate a systematic study of classes of graphs that have bounded induced matching treewidth, see Table 1. The definitions of the graphs listed throughout this section can be found in § 2.

Dichotomy theorems. First, we show results analogous to ones obtained for tree-independence number by Dallard, Milanič, and Štorgel [26]: for each of the six basic containment relations, we fully characterize which classes defined by excluding a single graph have bounded induced matching treewidth.

For subgraphs, induced subgraphs, minors, and topological minors, the dichotomies almost coincide with the ones for tree-independence number. Note that graphs with no large induced matching have trivially bounded induced matching treewidth, just like graphs with no large independent set have trivially bounded tree-independence number.

Theorem 1.1. Let HH be a graph with at least 22 vertices. The following hold.

(1.) The class of HH-subgraph-free graphs has bounded induced matching treewidth if and only if HH every component of HH is a subcubic tree with at most one vertex of degree $3.

(2.) The class of HH-free graphs has bounded induced matching treewidth if and only if HH is P3P_3 or a graph with maximum degree 1.

(3.) The class of HH-minor-free graphs has bounded induced matching treewidth if and only if HH is planar.

(4.) The class of HH-topological-minor-free graphs has bounded induced matching treewidth if and only if HH is subcubic and planar.

All unbounded cases remain so, even when restricted to 2-connected graphs.

The landscape gets a bit richer when we exclude a graph as an induced topological minor: here we get a new bounded case: 1-tipi, also known as the paw, see Figure 1.

Figure 1. The qq-tipi (left), qq-windmill (middle), and K^4(q)\widehat{K}_4^{(q)} (right).

Theorem 1.2. Let HH be a graph with at least 2 vertices. The class of HH-topological-minor-free graphs has bounded induced matching treewidth if and only if HH is not contained in one of the following graphs: C4C_4, K4−K_4^-, 1-tipi, or a matching as an induced topological minor. All unbounded cases remain so, even when restricted to 2-connected graphs.

For HH-induced-minor-free graphs, we actually get an infinite family of bounded cases: it turns out that excluding any tipi (i.e., the qq-tipi for any qq) bounds the induced matching treewidth.

Theorem 1.3. Let HH be a graph with at least 2 vertices. The class of HH-induced-minor-free graphs has bounded induced matching treewidth if and only if HH is an induced minor of one of the following graphs: K2,qK_{2,q} for some q∈Nq \in\mathbb{N}, W4W_4, K5−K_5^-, a tipi, or a matching.

Restricting to graphs of minimum degree 2. Recall that the motivation to consider induced matching treewidth was that tree-independence number is unbounded in some very simple classes of graphs, like bicliques. Admittedly, induced matching treewidth has similar drawback. Consider for example the graph obtained from the biclique with each part of size nn by adding a private neighbor to every vertex. As noted by Yolov [50] this graph has induced matching treewidth nn.

However, instead of defining a new parameter, we can take another route. If our motivation is algorithmic, perhaps degree-1 vertices do not play a crucial role and can be removed by some preprocessing rule. In general, we can try to apply various (problem-dependent) preprocessing rules to the considered graph and only then ask if the considered parameter is bounded. This idea is not new, but previously it was applied to other (not tree-decomposition-based) graph parameters, like clique-width [24, 35] and mim-width [13].

We investigate this direction for tree-independence number and induced matching treewidth in classes excluding a fixed substructure. First, let us restrict our attention to graphs with minimum degree 2 as for most classic computational problems we can indeed easily handle vertices of degree at most 1. It turns out that for tree-independence number this change in the setting does not alter the dichotomies for any of the six consider containment relations. Similarly, for induced matching treewidth and (induced) subgraph, (induced) topological minors, and minors, the classification remains the same as before.

However, for HH-induced-minor-free graphs, we get new family of bounded cases: if HH is a windmill, i.e., the qq-windmill for any qq; see Figure 1.

Theorem 1.4. Let HH be a graph. The class of HH-induced-minor-free graphs, restricted to graphs with minimum degree at least 2, has bounded induced matching treewidth if and only if HH is an induced minor of one of the following graphs: K2,qK_{2,q} for some q∈Nq \in\mathbb{N}, W4W_4, K5−K_5^{-}, or a windmill.

Graphs that exclude a fixed windmill as an induced minor were considered by Bonnet, Duron, Geniet, Thomassé, and Wesolek [11]; we will get back to this soon.

Restricting to 2-connected graphs. We can further generalize the idea of removing vertices of degree 1: we can assume that the input graph is 2-connected. Indeed, for many problems such an assumption is justified (see e.g. § 10). Note that this setting generalizes the one considered before, as every 2-connected graph has no vertices of degree at most 1. Again, it turns out that for two parameters and six containment relations studied in this paper, only the case of induced matching treewidth of HH-induced-minor-free graphs differs from the basic dichotomies without any further restrictions imposed on the graph.

In this setting, we get one more bounded case: K^4(1)\widehat{K}_4^{(1)}, for simplicity denoted as K^4\widehat{K}_4, see Figure 1.

Theorem 1.5. Let HH be a graph. The class of HH-induced-minor-free graphs, restricted to 2-connected graphs, has bounded induced matching treewidth if HH is an induced minor of one of the following graphs: K2,qK_{2,q} for some qq, W4W_4, K5−K_5^{-}, a windmill, a matching, or K^4\widehat{K}_4. If HH is not one of these graphs, nor K^4(q)\widehat{K}_4^{(q)} for some fixed qq, then 2-connected HH-induced-minor-free graphs have unbounded induced matching treewidth.

Our Theorem 1.5 leaves one family of open cases: H=K^4(q)H = \widehat{K}_4^{(q)} for some q≥2q \ge2. For them, we were not able to prove either boundedness nor unboundedness of induced matching treewidth for 2-connected HH-induced-minor-free graphs. We believe in the former outcome and we state the following conjecture.

Conjecture 1.6. For every fixed q≥1q \ge1, the class of 2-connected K^4(q)\widehat{K}_4^{(q)}-induced-minor-free graphs has bounded induced matching treewidth.

Algorithmic consequences. Now, let us turn our attention to algorithmic implications of our results. We consider two general families of problems: (tw⁡≤r,ψ)(\operatorname{tw} \le r,\psi)-MWIS and Max Induced HH-Colorable Subgraph. The first one asks for a maximum-weight induced subgraph of treewidth at most rr, satisfying given CMSO2_2 formula, while the second one asks for a maximum-weight induced subgraph homomorphic to a fixed simple graph HH; see § 10 for precise definitions. Let us mention that the first family captures, e.g., MWIS, Feedback Vertex Set, and Even Cycle Transversal, while the second family captures, e.g., MWIS (again), Odd Cycle Transversal, and List kk-Coloring for any fixed kk.

We show that for all problems described by the formalisms above, it is indeed enough to solve instances that are 2-connected. Thus, combining this with known algorithms for graphs of bounded induced matching treewidth [8, 50] and our Theorem 1.5, we obtain the following algorithmic corollary. (The first column follows from bounded tree-independence number and thus, it was known before, while the second column contains new results.)

Corollary 1.7. Every problem that can be described as Max Induced HH-Colorable Subgraph for some fixed simple graph HH or (tw⁡≤r,ψ)(\operatorname{tw} \le r,\psi)-MWIS for fixed rr and a formula ψ\psi, can be solved in polynomial time when restricted to graphs from the following classes:

  • K2,qK_{2,q}-induced-minor-free for any fixed qq,

  • W4W_4-induced-minor-free,

  • K5−K_5^{-}-induced-minor-free,

  • qq-windmill-induced-minor-free for any fixed qq,

  • K^4\widehat{K}_4-induced-minor-free.

Let us mention some context of these results. First, as already mentioned, Bonnet, Duron, Geniet, Thomassé, and Wesolek [11] considered graphs that exclude a fixed windmill as an induced minor, and showed that MWIS can be solved in polynomial time in every such class. Our Corollary 1.7 not only heavily generalizes this result, but also shows the underlying reason why this class admits algorithms for classic problems.

Second, our results confirm special cases of the following conjecture of Gartland and Lokshtanov [32].

Conjecture 1.8 (Gartland and Lokshtanov). For any fixed planar graph HH, integer rr, and a formula ψ\psi, (tw⁡≤r,ψ)(\operatorname{tw} \le r,\psi)-MWIS and List 3-Coloring can be solved in polynomial time in HH-induced-minor-free graphs.

Very recently, Conjecture 1.8 was disproved by Bonnet and Chang [51] for HH being the 5×55 \times5 grid. However, the statement was confirmed for some families of simple planar graphs HH [3, 12, 18, 19, 31, 36, 39, 40, 42] and it remains a very interesting open problem to understand for which graphs HH the conjecture actually holds. Even its relaxed variants, asking for quasipolynomial-time algorithms, or at least a quasipolynomial-time approximation scheme (QPTAS) for MWIS, remain very challenging and are shown only in restricted cases [9, 10, 11, 16, 23, 33, 34, 44, 46].

Dominated balanced separators. Finally, we show one more consequence of our results. For a constant tt, a class of graphs is said to admit tt-dominated balanced separator if every graph from the class a set of at most tt vertices, such that removing these vertices along with their neighbors breaks the graph into small pieces; see § 11 for precise definitions. We show that boundedness of induced matching treewidth, even for just 2-connected members of the considered class, yields O(1)O(1)-dominated balanced separators. Thus we obtain the following.

Corollary 1.9. The following classes of graphs admit tt-dominated balanced separators, where tt is a constant depending only on the class.

  • K2,qK_{2,q}-induced-minor-free for any fixed qq,

  • W4W_4-induced-minor-free,

  • K‾5\overline{K}_5-induced-minor-free,

  • qq-windmill-induced-minor-free for any fixed qq,

  • K‾4\overline{K}_4-induced-minor-free.

Corollary 1.9 confirms special cases of another conjecture by Gartland and Lokshtanov [32].

Conjecture 1.10 (Gartland and Lokshtanov). For any fixed planar graph HH there exists tt such that HH-induced-minor-free graphs admit tt-dominated balanced separators.

Conjecture 1.10 is also very challenging and, despite interest in the community, was only confirmed for very restricted graphs HH [5, 16, 20, 23].

Organization of the paper. In § 2 we define main notions used in the paper and show some basic results. In § 3 we construct some families of graphs with unbounded induced matching treewidth. In § 6 we discuss graphs that exclude a tipi as an induced minor. In § 7 we show Theorems 1.1, 1.2 and 1.3, i.e., dichotomy theorems for classes that exclude one fixed graph. In § 8 we dicuss the problem where we additionally assume that th graphs considered have minimum degree 2, and prove Theorem 1.4. In § 9 we restrict ourselves to 2-connected graphs wne show Theorem 1.5. In § 10 we discuss algorithmic consequences of our results and show Corollary 1.7. In § 11 we discuss dominated balanced separators an show Corollary 1.9. Finally, in § 12, we point out some directions for further research.

Definitions and basic tools

For an integer nn, by [n][n] we denote the set {1,2,…,n}\{1,2,\ldots,n\}. For a set XX, by 2X2^{X} we denote the family of all subsets of XX.

Graph theory. All graphs in the paper are undirected and simple, i.e., without loops or parallel edges. Let GG be a graph and consider X⊆V(G)X \subseteq V(G). By G[X]G[X] we denote the subgraph of GG induced by XX and by G−XG-X we denote G[V(G)∖X]G[V(G) \setminus X]. We use N[X]N[X] for the closed neighborhood of XX, i.e., the set consisting of XX and all vertices adjacent to a vertex of XX. If it does not lead to confusion, sometimes we identify induced subgraphs with their vertex sets.

We say that a graph is biconnected if it is 2-connected or isomorphic to K2K_2. A block is an inclusion-wise biconnected (induced) subgraph of a graph. A block-cut tree of a connected graph GG is the bipartite graph whose vertices are blocks and cutvertices of GG, and a cutvertex vv and a block bb are adjacent if and only if v∈bv \in b. It is well-known that the block-cut tree is indeed a tree. Note that all leaves of this tree are blocks. We treat block-cut trees as rooted trees, where the root rr is an arbitrarily chosen leaf and which defines a parent-child relation between adjacent nodes. For a block node b≠rb \ne r, if vbv_b is the cutvertex that is the parent of bb in TT, then the parent of vbv_b in TT is called the parent block. Analogously we define children blocks and leaf blocks.

References

  1. [1]Tara Abrishami, Bogdan Alecu, Maria Chudnovsky, Sepehr Hajebi, Sophie Spirkl, and Kristina Vušković. Three independence number I. (Even hole, diamond, pyramid)-free graphs. Journal of Graph Theory, 106(4):923–943, 2024.DOI
  2. [2]Tara Abrishami, Marcin Briański, Jadwiga Czyżewska, Rose McCarty, Martin Milanič, Pawel Rzążewski, and Bartosz Walczak. Excluding a clique or a biclique in graphs of bounded induced matching treewidth. SIAM J. Discret. Math., 39(2):1189–1200, 2025.arxiv.org/abs/2405.04617
  3. [3]Tara Abrishami, Maria Chudnovsky, Marcin Pilipczuk, Paweł Rzążewski, and Paul D. Seymour. Induced subgraphs of bounded treewidth and the container method. SIAM J. Comput., 53(3):624–647, 2024.
  4. [4]Stefan Arnborg, Derek G. Corneil, and Andrzej Proskurowski. Complexity of finding embeddings in a k-tree. SIAM Journal on Algebraic Discrete Methods, 8(2):277–284, April 1987.DOI
  5. [5]Gábor Bacsó, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Zsolt Tuza, and Erik Jan van Leeuwen. Subexponential-time algorithms for Maximum Independent Set in Pₜ-free and broom-free graphs. Algorithmica, 81(2):421–438, 2019.
  6. [6]Umberto Bertele and Francesco Brioschi. Nonserial dynamic programming. Academic Press, 1972.
  7. [7]Jarosław Błasiok, Marcin Kamiński, Jean-Florent Raymond, and Théophile Trunck. Induced minors and well-quasi-ordering. Journal of Combinatorial Theory, Series B, 134:110–142, 2019.
  8. [8]Hans L. Bodlaender, Fedor V. Fomin, and Tuukka Korhonen. Finding sparse induced subgraphs on graphs of bounded induced matching treewidth. In Kasper Green Larsen and Barna Saha, editors, Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2026, Vancouver, BC, Canada, January 11-14, 2026, pages 2043–2068. SIAM, 2026.arxiv.org/abs/2507.07975
  9. [9]Marthe Bonamy, Édouard Bonnet, Hugues Déprés, Louis Esperet, Colin Geniet, Claire Hilaire, Stéphane Thomassé, and Alexandra Wesolek. Sparse graphs with bounded induced cycle packing number have logarithmic treewidth. J. Comb. Theory B, 167:215–249, 2024.
  10. [10]Édouard Bonnet, Jadwiga Czyżewska, Tomáš Masařík, Marcin Pilipczuk, and Paweł Rzążewski. QPTAS for MWIS and finding large sparse induced subgraphs in graphs with few independent long holes. In Pierre Fraigniaud, editor, 20th Scandinavian Symposium on Algorithm Theory, SWAT 2026, Copenhagen, Denmark, June 17-19, 2026, volume 370 of LIPIcs, pages 9:1–9:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026.
  11. [11]Édouard Bonnet, Julien Duron, Colin Geniet, Stéphan Thomassé, and Alexandra Wesolek. Maximum independent set when excluding an induced minor: K₁ + 2K₂ and tC₃ ⊎ C₄. Algorithmica, 88(1):16, 2026.
  12. [12]Flavia Bonomo, Maria Chudnovsky, Peter Maceli, Oliver Schaudt, Maya Stein, and Mingxian Zhong. Three-coloring and list three-coloring of graphs without induced paths on seven vertices. Comb., 38(4):779–801, 2018.DOI
  13. [13]Nick Brettell, Jake Horsfield, and Daniël Paulusma. Colouring sP₁ + P₅-free graphs: a mim-width perspective. CoRR, abs/2004.05022, 2020.
  14. [14]Maria Chudnovsky, E. S Ajaykrishnan, and Daniel Lokshtanov. (Treewidth, clique)-boundedness and poly-logarithmic tree-independence. arXiv preprint arXiv:2510.15074, 2025.arxiv.org/abs/2510.15074
  15. [15]Maria Chudnovsky, Peter Gartland, Sepehr Hajebi, Daniel Lokshtanov, and Sophie Spirkl. Tree independence number IV. even-hole-free graphs. In Yossi Azar and Debmalyа Panigrahi, editors, Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2025, New Orleans, LA, USA, January 12-15, 2025, pages 4444–4461. SIAM, 2025.arxiv.org/abs/2407.08927
  16. [16]Maria Chudnovsky, J. Pascal Gollin, Matjaž Krnc, and Martin Milanič. Dominated balanced separators in wheel-induced-minor-free graphs. arXiv preprint arXiv:2512.12329, 2025.arxiv.org/abs/2512.12329
  17. [17]Maria Chudnovsky, Sepehr Hajebi, Daniel Lokshtanov, and Sophie Spirkl. Tree independence number II. three-path-configurations. J. Comb. Theory B, 176:74–96, 2026.DOI
  18. [18]Maria Chudnovsky, Shenwei Huang, Sophie Spirkl, and Mingxian Zhong. List 3-coloring graphs with no induced P₆ + rP₃. Algorithmica, 83(1):216–251, 2021.
  19. [19]Maria Chudnovsky, Rose McCarty, Marcin Pilipczuk, Michał Pilipczuk, and Paweł Rzążewski. Sparse induced subgraphs in P₆-free graphs. ACM Trans. Algorithms, 22(2):16:1–16:45, 2026.
  20. [20]Maria Chudnovsky, Marcin Pilipczuk, Michał Pilipczuk, and Stéphan Thomassé. Quasi-polynomial time approximation schemes for the Maximum Weight Independent Set problem in H-free graphs. SIAM Journal on Computing, 53(1):47–86, 2024.
  21. [21]Bruno Courcelle and Joost Engelfriet. Graph Structure and Monadic Second-Order Logic: A Language-Theoretic Approach. Cambridge University Press, Cambridge, 2012.
  22. [22]Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Parameterized algorithms. Springer, Cham, 2015.DOI
  23. [23]Jadwiga Czyżewska, Tomáš Masařík, Marcin Pilipczuk, Amadeus Reinald, and Paweł Rzążewski. Induced Erdős–Pósa property for long holes, long thetas, and beyond. arXiv preprint arXiv:2607.07697, 2026.
  24. [24]Konrad K. Dabrowski, Tomáš Masařík, Jana Novotná, Daniël Paulusma, and Paweł Rzążewski. Clique-width: Harnessing the power of atoms. J. Graph Theory, 104(4):769–810, 2023.
  25. [25]Clément Dallard, Fedor V. Fomin, Petr A. Golovach, Tuukka Korhonen, and Martin Milanič. Computing tree decompositions with small independence number. ACM Trans. Algorithms, 22(1), November 2025.arxiv.org/abs/2207.09993
  26. [26]Clément Dallard, Martin Milanič, and Kenny Štorgel. Treewidth versus clique number. III. Tree-independence number of graphs with a forbidden structure. Journal of Combinatorial Theory, Series B, 167:338–391, 2024.arxiv.org/abs/2206.15092
  27. [27]Clément Dallard, Martin Milanič, and Kenny Štorgel. Treewidth versus clique number. II. Tree-independence number. J. Combin. Theory Ser. B, 164:404–442, 2024.arxiv.org/abs/2111.04543
  28. [28]Paloma Thomé de Lima, Martin Milanič, Peter Muršič, Karolina Okrasa, Paweł Rzążewski, and Kenny Štorgel. Tree decompositions meet induced matchings: beyond Max Weight Independent Set. J. Comput. Syst. Sci., 161:103819, 2026.
  29. [29]Reinhard Diestel. Graph Theory, 6th Edition, volume 173 of Graduate Texts in Mathematics. Springer, 2025.
  30. [30]R. J. Duffin. Topology of series-parallel networks. Journal of Mathematical Analysis and Applications, 10(2):303–318, 1965.DOI
  31. [31]Esther Galby, Paloma T. Lima, Andrea Munaro, and Amir Nikabadi. Maximum list r-colorable induced subgraphs in kp3-free graphs. In Anne Benoit, Haim Kaplan, Sebastian Wild, and Gregorcz Herman, editors, 33rd Annual European Symposium on Algorithms, ESA 2025, Warsaw, Poland, September 15-17, 2025, volume 351 of LIPIcs, pages 40:1–40:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025.DOI
  32. [32]Peter Gartland. Quasi-polynomial time techniques for independent set and beyond in hereditary graph classes. PhD thesis, University of California, Santa Barbara, 2023.
  33. [33]Peter Gartland and Daniel Loksh tanov. Independent set on Pk-free graphs in quasi-polynomial time. In Sandy Irani, editor, 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pages 613–624. IEEE, 2020.DOI
  34. [34]Peter Gartland, Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, and Paweł Rzążewski. Finding large induced sparse subgraphs in C>t-free graphs in quasipolynomial time. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 330–341, 2021.arxiv.org/abs/2007.11402
  35. [35]Serge Gaspers, Shenwei Huang, and Daniël Paulusma. Colouring square-free graphs without long induced paths. J. Comput. Syst. Sci., 106:60–79, 2019.
  36. [36]Andrzej Grzesik, Tereza Klimošová, Marcin Pilipczuk, and Michał Pilipczuk. Polynomial-time algorithm for maximum weight independent set on P6-free graphs. ACM Trans. Algorithms, 18(1):4:1–4:57, 2022.
  37. [37]Michel Habib and Christophe Paul. A survey of the algorithmic aspects of modular decomposition. Computer Science Review, 4(1):41–59, 2010.DOI
  38. [38]Rudolf Halin. S-functions for graphs. Journal of Geometry, 8(1):171–186, 1976.DOI
  39. [39]Chính T. Hoàng, Marcin Kamiński, Vadim V. Lozin, Joe Sawada, and Xiao Shu. Deciding k-colorability of P5-free graphs in polynomial time. Algorithmica, 57(1):74–81, 2010.
  40. [40]Tereza Klimošová, Josef Malík, Tomáš Masařík, Jana Novotná, Daniël Paulusma, and Veronika Slívová. Colouring Pr + Ps-free graphs. Algorithmica, 82(7):1833–1858, 2020.
  41. [41]Daniel Lokshtanov, Michał Pilipczuk, and Paweł Rzążewski. Finding large sparse induced subgraphs in graphs of small (but not very small) tree-independence number. CoRR, abs/2601.15861, 2026.arxiv.org/abs/2601.15861
  42. [42]Daniel Lokshtanov, Martin Vatshelle, and Yngve Villanger. Independent set in P5-free graphs in polynomial time. In Chandra Chekuri, editor, Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pages 570–581. SIAM, 2014.
  43. [43]Martin Milanič and Nevena Pivač. A tame vs. feral dichotomy for graph classes excluding an induced minor or induced topological minor. CoRR, abs/2405.15543, 2024.arxiv.org/abs/2405.15543
  44. [44]Tung Nguyen, Alex D. Scott, and Paul D. Seymour. Induced paths in graphs without anticomplete cycles. J. Comb. Theory B, 164:321–339, 2024.arxiv.org/abs/2212.01089
  45. [45]Amir Nikabadi and Paweł Rzążewski. Induced packing treewidth. arXiv preprint arXiv:2607.07595, 2026.arxiv.org/abs/2607.07595
  46. [46]Marcin Pilipczuk, Michał Pilipczuk, and Paweł Rzążewski. Quasi-polynomial-time algorithm for independent set in P_t-free graphs via shrinking the space of induced paths. In Hung Viet Le and Valerie King, editors, 4th Symposium on Simplicity in Algorithms, SOSA 2021, Virtual Conference, January 11-12, 2021, pages 204–209. SIAM, 2021.
  47. [47]Neil Robertson and Paul D. Seymour. Graph minors. III. Planar tree-width. J. Comb. Theory, Ser. B, 36(1):49–64, 1984.
  48. [48]Neil Robertson and Paul D. Seymour. Graph minors. V. Excluding a planar graph. J. Comb. Theory B, 41(1):92–114, 1986.DOI
  49. [49]Robert E Tarjan. Decomposition by clique separators. Discrete Mathematics, 55(2):221–232, 1985.DOI
  50. [50]Nikola Yolov. Minor-matching hypertree width. In Artur Czumaj, editor, Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 219–233. SIAM, 2018.
  51. [51]Édouard Bonnet and Yeonsu Chang. Max independent set remains NP-hard when excluding a planar induced minor. CoRR, abs/2609.11285, 2026.arxiv.org/abs/2609.11285

Paper details

vlnc:W_effdju67
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 6

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents