Graphs without induced stars have bounded path independence number
Induced Forest Minor Theorem for Graphs Without an Induced Star
Discrete Mathematics
Summary
This paper looks at a special way to break down graphs into smaller parts where each part has limited independent points. The authors show that if a graph does not contain certain star-shaped subgraphs or complex tree structures, then this kind of breakdown is always bounded. This helps understand when such decompositions exist and partially confirms a previous guess made by other researchers. The work also leads to new ways to test for specific graph patterns and solve tough problems efficiently on these restricted graphs.
What this means in practice
- •For algorithm developers: Run polynomial-time tests for specific induced minor containment on graphs excluding certain subgraphs and stars.
- •For optimization software engineers: Solve Maximum Weight Independent Set and other NP-hard problems efficiently on graphs without induced stars and forbidden induced minors.
A theory result. No direct application yet.
Authors
Robert Hickingbotham, Gwenaël Joret
Abstract
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{č}, Munaro, Š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.