PaperlayerView exact revision on arXiv

Source-linked AI summary

Induced Forest Minor Theorem for Graphs Without an Induced Star

Robert Hickingbotham, Gwenaël Joret

arXiv:2609.10406v1math.COcs.DM

TL;DR

The paper addresses induced-minor analogues of structural results for graph classes, focusing on path and tree independence numbers. It develops α-Menger boundedness and proves boundedness under forest and apex-forest exclusions, with a further consequence for a conjecture about path domination.

  • Problem

    The paper addresses the open question of whether tree independence number admits a grid-like theorem, seeking induced-minor structural results that apply without the additional sparsity constraint associated with treewidth.

    Source: §1 · p. 2

  • Method

    The proof uses α-Menger boundedness to connect separator independence to anti-complete paths, then applies a tree-to-path decomposition argument for forest exclusions.

    Source: §1.1 · p. 6, §7 · p. 31

  • Results

    K1,t-free graphs excluding a forest induced minor have bounded path independence, while those excluding an apex-forest induced minor have bounded tree independence.

    Source: §1 · p. 3

  • Takeaways & Limitations

    For K1,t-free graphs, Theorem 3 supports Conjecture 40 because domination and independence numbers differ by at most a factor of t.

    Source: §8 · p. 36

    The authors make no attempt to optimise the functions in their bounds.

    Source: §7 · p. 31

Abstract

from arXiv · show

Motivated by recent work on tree independence number, we study the path independence number of a graph $G$: the minimum integer $k$ such that there is a path decomposition of $G$ where each bag induces a graph with independence number at most $k$. We show that every graph excluding both an induced forest minor and an induced star has bounded path independence number. This characterises when a graph class that excludes an induced star has bounded path independence number while also partially resolving a conjecture of Dallard, Krnc, Kwon, Milani{\v{c}}, Munaro, \v{S}torgel and Wiederrecht (2024). Furthermore, we show that graphs excluding both an apex-forest induced minor and an induced star have bounded tree independence number. As a consequence, for every fixed apex-forest $H$ and integer $t$, there is a polynomial-time algorithm to test whether a $K_{1,t}$-induced-subgraph-free graph contains $H$ as an induced minor. Moreover, it follows that the Maximum Weight Independent Set problem, as well as several other NP-hard problems, can be solved in polynomial-time on $K_{1,t}$-induced-subgraph-free graphs that exclude $H$ as an induced minor.

1 Introduction

The introduction develops path independence as an induced-minor-friendly parameter and proves boundedness results under induced-star and induced-forest exclusions. It also gives a proof route through α-Menger boundedness and derives structural and algorithmic consequences.

1 Introduction

  • Tree independence number offers a decomposition parameter suited to dense graphs, unlike treewidth, which requires an additional sparsity constraint for boundedness results.Complete graphs have tree independence number 1.Source: §1 · p. 2
  • For every forest H and t, K1,t-free graphs with no H induced minor have bounded path independence number.The paper defines this parameter as the minimum independence number of a bag over all path-decompositions.Source: §1 · p. 3
  • For every apex-forest H and t, K1,t-free graphs with no H induced minor have bounded tree independence number.Source: §1 · p. 3
  • For every fixed apex-forest H and t, induced-minor containment and Maximum Weight Independent Set are polynomial-time solvable on K1,t-free graphs excluding H as an induced minor.Source: Applications · p. 4
  • Every forest has the independence Erdős–Pósa property in K1,t-free graphs.The property concerns either finding many pairwise anti-complete induced-minor copies or a set of bounded independence number whose removal eliminates the excluded induced minor.Source: Applications · p. 5

1.1 Overview of Proof

  • The proof route establishes α-Menger boundedness for apex-forest exclusions, derives bounded tree independence, and converts the tree decomposition to a path decomposition for forests.The conversion uses an Erdős–Pósa-style lemma.Source: §1.1 · p. 6

2 Preliminaries

The preliminaries fix the graph, neighborhood, path, and decomposition notation used in the paper, alongside induced-minor models and independence-based parameters.

2 Preliminaries

  • An induced minor is obtained from an induced subgraph by contracting edges; an induced minor model uses connected branch sets that are pairwise anti-complete for nonedges of the target.Source: §2 · p. 7
  • The independence number is the maximum size of an independent set, and K1,t-freeness implies α(N[v]) ≤ t for every vertex v.Source: §2 · p. 7
  • Tree and path independence numbers do not increase when taking induced minors.The preliminaries also note that this follows for path independence by the same reasoning as for tree independence.Source: §2 · p. 7

3 α-Menger ⇒Tree Independence Number

For α-Menger bounded classes, large tree independence number in K1,t-free graphs forces large grid induced minors. The section connects this result to bounded tree independence when induced grid-like minors are excluded.

3 α-Menger ⇒Tree Independence Number

  • For every α-Menger bounded class, sufficiently large tree independence number in a K1,t-free graph forces a k × k grid as an induced minor.The threshold depends on k, t, and the class's α-Menger binding function.Source: §3 · p. 8
  • Since grids contain every planar graph as an induced minor, the grid result establishes Theorem 9.Source: §3 · p. 8
  • A grid-like minor is a collection of paths whose intersection graph is bipartite and contains a Kℓ minor; its induced version requires induced paths and a bipartite touching graph.The section uses brambles to relate induced grid-like minors to large treewidth.Source: §3 · p. 8
  • An induced grid-like minor of order ℓ in a K1,t-free graph yields an induced subgraph of maximum degree at most 2t and treewidth at least ⌈ℓ/2⌉−1.The proof uses a bramble derived from the touching graph to obtain the treewidth bound.Source: §3 · pp. 8–9
  • In an α-Menger bounded class, excluding induced grid-like minors of sufficiently large order bounds tree independence number.Theorem 13 follows by combining this bound with the implication from Lemma 16.Source: §3 · p. 9

4 Induced Grid-Like Minors

The section adapts Reed and Wood’s approach to construct induced grid-like minors. It derives separated induced paths from large tree independence number, then uses connecting paths to build the required minor.

4 Induced Grid-Like Minors

  • The proof adapts Reed and Wood’s ideas using strong brambles, whose α-order is the minimum independence number of a hitting set.Strong brambles relate tree independence number to induced paths: a strong bramble yields an induced path whose closed neighbourhood intersects every bramble element.Source: §4 · pp. 9–10
  • For k > 2t, tree independence number at least 4ℓ(k + 2t) − 2 guarantees ℓ pairwise anti-complete induced paths with pairwise α-separation at least k between their neighbourhoods.This path-separation lemma is the starting point for constructing an induced grid-like minor.Source: §4 · p. 10
  • If ℓ pairwise anti-complete induced paths have k pairwise anti-complete connecting paths for each pair, then the graph contains an induced grid-like minor of order ℓ.The construction selects a collection of connecting paths whose touching graph, together with the original paths, contains a 1-subdivision of Kℓ.Source: §4 · p. 11
  • In an α-Menger bounded class, excluding induced grid-like minors of order ℓ bounds tree independence number for K1,t-free graphs.The argument obtains separated paths from large tree independence number and uses α-Menger boundedness to supply connecting paths, contradicting exclusion.Source: §4 · pp. 11–12

5 α-Menger and Induced Apex-Forest Minor

This section develops a single-path induced-minor construction and proves an α-Menger-type packing theorem for graphs excluding an induced apex-forest minor and an induced star. The proofs use path extensions, separator strength, and structural lemmas involving complete bipartite induced minors, well-separated path indices, and clone selection.

5 α-Menger and Induced Apex-Forest Minor

  • For every apex-forest H and t, K1,t-free graphs excluding H as an induced minor are α-Menger bounded.The proof iteratively extracts paths while preserving enough separation to obtain pairwise anti-complete paths between the specified neighbourhoods.Source: §5 · p. 12

5.1 Properties about α-separators

  • The separator lemmas bound how much sepα changes when vertices are deleted or terminal sets are reduced, and transfer separator loss to another terminal pair.If α(C) ≤ t, deleting C or removing it from a terminal set reduces the relevant separation by at most t; Lemma 27 provides the transfer under its stated disjointness and loss conditions.Source: §5.1 · p. 13

5.2 Finding complete bipartite graphs as induced minors

  • For planar H, K1,t-free H-induced-minor-free graphs exclude a sufficiently large Kc,c induced minor, and large arrays in K1,t-free graphs force Kr,s induced minors.The array lemma specifies branch sets drawn from the connected subgraphs and their associated neighbourhood sets.Source: §5.2 · p. 14
  • In a Kn,n-free bipartite graph, a sufficiently large side A yields ℓ vertices with a non-neighbour in each part of a partition of the other side into at most ℓ sets.Each partition set must have at least n vertices; the required size of A is bounded by a function of ℓ and n.Source: §5.2 · p. 16

5.3 Extracting a Single Path

  • When sepα(G, A, B) is sufficiently large, Lemma 33 yields a tree-model, a path preserving separation, or a Kc,c induced minor.The lemma applies to K1,t-free G with s > 2t; its tree-model preserves specified separator bounds, while the path outcome leaves sepα(G − NG[P], A, B) at least s.Source: §5.3 · pp. 16–17
  • The induction constructs paths R1,…,RN satisfying properties R1–R13, yielding a preliminary induced-minor model of a tree with cloned leaves.The model combines the branch sets of W* with the constructed paths.Source: §5.3 · p. 24
  • There is a subset S1 of N path indices, of size fN, whose paths have pairwise disjoint neighborhoods outside XN.The auxiliary graph on path indices has no clique of size 2n, since such a clique would give an induced K_{c,c} minor; Ramsey’s Theorem then yields S1.Source: §5.3 · p. 25
  • A further claim selects S2⊆S1 with |S2|=|Lv| and asserts a clone choice for every z∈L\Lv satisfying a neighborhood condition.The supplied passage truncates before stating the neighborhood condition in full.Source: §5.3 · p. 25
  • The constructed branch sets form an induced minor model of T satisfying (W1)–(W4), completing the induction step for the single-path lemma.The leaf branch sets are connected, pairwise anti-complete, and attached as required to the model of T.Source: §5.3 · pp. 26–28

5.4 Proof of Theorem 24

  • Every n-vertex apex-forest is an induced minor of a special apex tree with at most 2n + 1 vertices.The construction adds a root and leaves to connect the forest components and represent the apex neighborhood.Source: §5.4 · p. 28
  • If separator value sepα is at least fH,t(k), every K1,t-free, H-induced-minor-free graph contains k pairwise anti-complete paths between the neighborhoods of any two induced paths.This is Theorem 36’s path-pair packing conclusion.Source: §5.4 · p. 29

6 Erdős–Pósa and Tree Independence Number

Theorem 37 extends an Erdős–Pósa-type alternative for bounded tree independence number by replacing vertex-disjointness with anti-completeness. Under bounded clique number for the connected induced subgraphs, it bounds the size of a neighborhood deletion set when there are not many pairwise anti-complete members.

Motivation

  • The alternative extends the bounded-treewidth Erdős–Pósa property by substituting anti-completeness for vertex-disjointness.The theorem is presented as a key tool for converting a tree-decomposition into a path-decomposition.Source: §6 · p. 30

Theorem 37

  • For α-tw(G) < k and connected induced subgraphs of clique number below w, either there are d pairwise anti-complete members or a bounded neighborhood deletion set removes them all.The set X has size less than (k + R(k, w))(d − 1), and G − NG[X] contains no member of the collection.Source: §6 · p. 30

Proof

  • The proof selects a deepest member in a rooted tree-decomposition, removes a neighborhood around its bag, and applies induction to the remaining graph.The first removal set has size below k + R(k, w); if d − 1 anti-complete members are absent, induction supplies the rest of the deletion set.Source: §6 · pp. 30–31

7 Tree Decomposition to Path Decomposition

Theorem 3 gives bounded path independence number for K1,t-free graphs excluding a forest as an induced minor. Its proof builds path-decompositions inductively from local neighborhood bounds and bounded tree independence number.

Theorem 3

  • Every K1,t-free graph with no forest H as an induced minor has path independence number at most some k.The proof reduces this result to bounded-arity trees, since every forest is an induced minor of some such tree.Source: §7 · p. 31

Lemma 38

  • If α-tw(G) < k, G excludes Th,d, and a root r has bounded neighborhood independence, Lemma 38 constructs a path-decomposition with a first bag containing NG[r].For every other vertex v, the lemma assumes α(NG[v]) ≤ t; the resulting bag independence bound is f(d, h, k, t).Source: §7 · p. 31

Bounds

  • The recursive bounds f and g are not optimized.For h ≥ 2, f is defined using the previous-height bound plus 2g.Source: §7 · p. 31

Base case

  • For height h = 1, distance layers yield bags Vi ∪ Vi+1 with independence number at most 2d.A layer with independence number above d would create T1,d as an induced minor, contradicting the exclusion assumption.Source: §7 · p. 32

Inductive step

  • For h ≥ 2, the proof forms minimal connected subgraphs joining the second neighborhood to a smaller tree model; d anti-complete such subgraphs would yield Th,d.Their clique numbers are bounded by 2(d + 2)(t + 1) + 4, enabling use of the anti-complete packing/deletion alternative.Source: §7 · pp. 32–33
  • Theorem 37 supplies a small deletion set for the minimal subgraphs, after which each component containing a second-neighborhood vertex can use induction on tree height.The resulting component decompositions have bound f((d + 2)(t + 1), h − 1, k, t).Source: §7 · pp. 33–34

Proof of Lemma 38

  • The proof recursively contracts the root neighborhood and selected paths into r′, then concatenates decompositions of the remaining components and the contracted graph.The resulting decomposition has the required path structure and bag independence bound, with its first bag containing NG[r].Source: §7 · pp. 34–35

8 Conclusion

The conclusion conjectures that excluding complete bipartite graphs and complete binary trees bounds path independence number, and that excluding a tree induced minor bounds path domination number. It gives evidence for the latter conjecture in K1,t-free graphs and through a bounded-ball path-decomposition result.

Open problems

  • The authors conjecture that excluding Kt,t and Th induced minors bounds path independence number by a function of t and h.Complete binary trees and Kt,t are identified as examples with large path independence number.Source: §8 · p. 35
  • The conjecture would generalize a bounded-pathwidth result for Kc-free graphs excluding Kt,t and Th induced minors.The analogous tree-independence conjecture with a grid in place of Th is false, as layered wheels exclude a grid and a complete bipartite graph as induced minors while having unbounded tree independence number.Source: §8 · p. 35
  • The authors conjecture that excluding Th as an induced minor bounds path domination number.Path domination number measures whether every path-decomposition bag lies in the union of at most k closed neighborhoods.Source: §8 · pp. 35–36

Evidence

  • For K1,t-free graphs, Theorem 3 supports the path-domination conjecture because domination and independence numbers differ by at most a factor of t.A result of Nguyen et al. [29] also gives path decompositions with bounded numbers of bounded-radius balls per bag; reducing their radius to 1 remains a challenge.Source: §8 · p. 36
Loading 2609.10406v1…