PaperlayerView exact revision on arXiv

Source-linked AI summary

An Erd\H{o}s-P\'osa theorem for induced packings of even cycles

Jungho Ahn, Lars Jaffke, O-joung Kwon, Paloma T. de Lima, Hyemi Park

arXiv:2610.22967v1math.COcs.DM

TL;DR

The paper asks whether induced-packing Erdős–Pósa results extend beyond cycles to even cycles. It proves such a theorem by recursively building and controlling bipartite structures, and obtains an explicit hitting-set bound alongside a polynomial-time algorithm. The result also bounds tree-independence number for K1,t-free graphs without the specified even-cycle packing.

  • Problem

    The paper investigates extending induced-packing Erdős–Pósa results beyond cycles to other graph families, including even cycles.

    Source: §1 · p. 2

  • Method

    The proof peels shortest even cycles, recursively builds bipartite subgraphs, and controls parity-breaking paths through path-matching graphs.

    Source: §1 · pp. 3–4

  • Results

    O(k^2 log k) vertices suffice for a closed neighborhood meeting every even cycle when no induced packing of k exists, and a polynomial-time algorithm outputs either outcome.

    Source: §1 · p. 2

  • Takeaways & Limitations

    K1,t-free graphs without an induced packing of k even cycles have tree-independence number O(tk^2 log k), with a polynomial-time computable witnessing decomposition.

    Source: §1 · p. 2

    The authors believe refined analysis could likely improve the bound to O(k log k), but present the cleaner, more transparent current argument.

    Source: §1 · p. 2

Abstract

from arXiv · show

We show that for every graph $G$ and every positive integer $k$, $G$ contains either $k$ vertex-disjoint even cycles with no edges between distinct cycles, or a set of $O(k^2\log k)$ vertices whose closed neighborhood meets every even cycle of $G$. Moreover, we give a polynomial-time algorithm that outputs one of the two outcomes. As an application, we show that every $K_{1,t}$-free graph containing no induced packing of $k$ even cycles has tree-independence number $O(tk^2\log k)$, with a corresponding decomposition computable in polynomial time.

1 Introduction

The introduction establishes an induced-packing Erdős–Pósa theorem for even cycles, with a polynomial-time algorithm, and applies it to bound tree-independence number in certain graphs. It outlines a proof that controls chords through bipartite structures and path-matching graphs.

1 Introduction

  • For every graph and positive integer k, either k even cycles form an induced packing or O(k^2 log k) vertices have a closed neighborhood meeting every even cycle; a polynomial-time algorithm finds either outcome.The running time is polynomial in |V(G)| and k.Source: §1 · p. 2
  • K1,t-free graphs with no induced packing of k even cycles have tree-independence number O(tk^2 log k), with a witnessing tree decomposition computable in polynomial time.The tree-independence number is a tree-decomposition parameter with applications to independent-set algorithms.Source: §1 · p. 2
  • Repeatedly removing the closed neighborhood of a shortest even cycle either finds k induced-packed cycles or reduces the proof to a graph with no even cycle outside one such neighborhood.In the restricted setting, the goal is an induced packing of k even cycles or an O(k log k)-vertex set whose closed neighborhood meets every even cycle.Source: §1 · p. 3
  • The proof recursively extends bipartite subgraphs with parity-preserving paths, controls the resulting chords using constant-size vertex covers, and uses skeletons with matching chords.Skeletons are bipartite subgraphs with degrees from 2 to 4 and parity-breaking chords forming a matching; the proof structures may be of independent interest.Source: §1 · pp. 3–4
  • In path-matching graphs, more than 11m + 23gθ(k) links with no consecutive serial pair force k vertex-disjoint cycles, each containing an even number of links.The paths model components of the chord-free subgraph, while links represent parity-breaking paths; this bound helps terminate that construction after O(k log k) steps.Source: §1 · p. 4
  • The proof is made algorithmic using polynomial-time shortest even-cycle and prescribed-parity path routines, recursive skeleton reductions, and a greedy final step.The shortest-cycle and prescribed-parity path routines each run in O(|V(G)|^2) time.Source: §1 · p. 5

2 Preliminaries

The preliminaries establish graph notation and define bipartite extendability through parity. They also record a logarithmic bound on the length of a cycle in graphs of minimum degree at least 3.

2 Preliminaries

  • The paper uses standard notation for vertex and edge sets, induced subgraphs, deletion, neighborhoods, paths, corridors, matchings, vertex covers, bridges, and chords.All logarithms are base 2, and graphs have neither loops nor multiple edges.Source: §2 · pp. 5–6
  • For a bipartite subgraph H of G, an H-path P is H-extendable, or parity-preserving, exactly when H ∪ P is bipartite; otherwise it is parity-breaking.A chord e of H in G is parity-preserving when (V(H), E(H) ∪ {e}) is bipartite, and parity-breaking otherwise.Source: §2 · p. 6
  • An H-path is H-extendable exactly when its length parity matches the bipartition-indicator values at its endpoints.An H-extendable path preserves bipartiteness when added to H.Source: §2 · p. 6
  • In a graph with minimum degree at least 3, some cycle has length at most 2 log|V(G)|.This is cited as Corollary 1.3.5 in.Source: §2 · p. 6

3 Extendable paths and chords

Under the proposition’s stated shortest-cycle and extendable-path conditions in a C4-subgraph-free graph, the section uses parity and structural restrictions on chords to bound the size of a vertex cover of the new chords. In particular, it constructs a vertex cover of J of size at most 10 that contains every vertex of degree at least 2 and every vertex in Z.

3 Extendable paths and chords

  • The new-chord graph J has a vertex cover of size at most 10, and every vertex of degree at least 2 has two chord-neighbors on P with the vertex outside the subpath between them.These conclusions apply under Proposition 3.1’s stated conditions on G, C, H, S, and the shortest H-extendable path P.Source: §3 · p. 7

3.1 Chords in a shortest even cycle

  • A chord of a shortest even cycle joins vertices whose cycle-path distances are even, and a shortest even cycle of length at least 6 has at most one chord.The first claim is Lemma 3.2; the second is Lemma 3.3.Source: §3.1 · p. 7

3.2 Chords whose endpoints are in an H-extendable path

  • On a shortest H-extendable path, any chord with both ends on P spans an even-length subpath, and two such chords cannot span internally disjoint subpaths or the specified interleaving configuration.The restrictions in Lemma 3.5 hold for a C4-subgraph-free graph.Source: §3.2 · p. 8

3.3 Chords whose one endpoint is in an H-extendable path

  • Shortest H-extendable paths have restricted configurations of chords joining H to P; in the stated C4-subgraph-free setting, they cannot contain three pairwise vertex-disjoint chords with all endpoints internal to P.The subsection also rules out specific arrangements of two such chords, including cases with an endpoint of one chord inside the other’s P-subpath.Source: §3.3 · pp. 9–11

3.4 Proof of Proposition 3.1

  • The proof uses nested subpaths spanned by chords with both ends on P to show their graph is a forest; for a forest J, |V_{≥2}(J) ∪ Z| ≤ 2k when k is its maximum matching size.The forest conclusion follows from the nesting property, while the bound is Lemma 3.12.Source: §3.4 · p. 12
  • A vertex cover T of J has size at most 10 and contains V_{≥2}(J) ∪ Z, proving (2).The construction combines covers of J_P and the edges in M_H, with sizes at most 6 and 4, respectively.Source: §3.4 · p. 13

4 Skeletons

This section develops skeletons—bipartite subgraphs with controlled chord structure—as a framework for extracting induced packings of even cycles, proving a branching-excess threshold and reducing chord count by modifying corridors. Its induction proceeds by combining a packing in a reduced graph with a separated cycle or by transforming a corridor-heavy skeleton to one with a smaller induction parameter.

4 Skeletons

  • A skeleton is a bipartite p2, 4q-subgraph whose chords form a matching, avoid pairs of branching endpoints and degree-4 vertices, and are all parity-breaking.Source: §4 · p. 13
  • Adding parity-preserving chords to a semi-skeleton preserves its semi-skeleton properties and yields a skeleton completion.Source: §4 · p. 14
  • For a corridor incident with at least 4 F0 chords, the modification ϕ(H, R) is a skeleton with a strictly smaller |F0| + |F1| measure.The construction removes part of the corridor and adds selected chord edges, then absorbs parity-preserving chords to obtain a skeleton.Source: §4 · pp. 15, 17
  • An induced packing of k − 1 even cycles in H2 combines with C to give an induced packing of k, since deleting C and its G-neighbors leaves no edges between C and H2.The induction hypothesis applies because |F0(H2) ∪ F1(H2)| ≤ |F0(H) ∪ F1(H)| and ε(H2) > f(k − 1).Source: §4 · p. 18
  • For a corridor R meeting at least four F0(H) chords, the construction K = ϕ(H, R) is a skeleton with ε(K) ≥ ε(H) and fewer F0/F1 edges, so induction yields k even cycles.The construction’s degree changes offset in ε, parity-preserving chords can only increase it, and |F0(K) ∪ F1(K)| < |F0(H) ∪ F1(H)|.Source: §4 · pp. 18–19

5 Path-matching graphs

The section uses path-matching graphs to control cycles containing an even number of matching links. It proves that sufficiently many links force many disjoint even-link cycles, using theta-minor structure and a bound on links outside a hitting set.

Path-matching graphs

  • A path-matching graph combines disjoint paths with a matching of links; an even-N cycle contains an even number of those links, and the section uses a restriction on consecutive serial links.The section’s goal is to use sufficiently many matching edges under a mild arrangement restriction to obtain disjoint cycles with an even number of links.Source: §5 · p. 19

Proposition 5.3

  • The theta-minor Erdős–Pósa theorem supplies either k disjoint theta-minor models or a vertex set of size at most g_theta(k) whose deletion removes all such models.The theorem also provides a polynomial-time algorithm for finding either outcome.Source: §5 · p. 19

Lemma 5.2

  • If J − Y has no theta-minor model and Y is closed under N, then at most 11q links of N have both endpoints outside Y, where q counts components of F − Y.The proof contracts each component of F − Y; the resulting theta-minor-free cactus structure helps bound the links.Source: §5 · pp. 19–20

Proposition 5.3

  • |N| > 11m + 23g_theta(k) guarantees k pairwise vertex-disjoint even-N cycles in a path-matching graph with the consecutive serial property.Here m is the number of paths; an even-N cycle contains an even number of links from N.Source: §5 · pp. 19–20
  • Two paths between the branch vertices of a theta subdivision with the same parity of N-links form an even-N cycle.Among the subdivision’s three internally vertex-disjoint paths, two necessarily contain the same parity of links.Source: §5 · pp. 20–21
  • A theta-minor hitting set, enlarged to be closed under N, lets Lemma 5.2 bound the remaining links and derive the proposition’s threshold.The proof applies the polynomial-time theta-minor Erdős–Pósa alternative.Source: §5 · pp. 19, 21

6 Reduction, ear decompositions, and the final cover

Section 6 develops reductions, bipartite ear decompositions, and parity-breaking extensions to establish packing-or-cover alternatives for induced even cycles, culminating in an O(k² log k) cover bound. It also gives a polynomial-time algorithm for the theorem’s two outcomes and applies the theorem to bound the tree-independence number of K₁,ₜ-free graphs with no induced packing of k even cycles.

6 Reduction, ear decompositions, and the final cover

  • If C is a shortest even cycle and G − N[C] has no even cycle, Theorem 6.1 gives either k induced-packed even cycles or a cover of size O(k log k).The theorem also provides a polynomial-time algorithm for finding one of these outcomes.Source: §6 · p. 21
  • The reduction gives either k induced-packed even cycles or a closed-neighborhood cover of size O(k^2 log k), with a polynomial-time algorithm for either outcome.The cover is obtained by iterating the shortest-cycle case and combining the resulting sets.Source: §6 · p. 22

6.1 Bipartite ear decompositions

  • In a maximal bipartite ear decomposition, every ear after the initial cycle has length at least 3, and every vertex in Hi − Si is incident with at most one chord of Hi.The construction extends the initial shortest even cycle using shortest available Hi-extensions and designated vertex sets Si.Source: §6.1 · pp. 23–24
  • At least 11k non-matching indices imply an induced packing of k even cycles, using a 10-degenerate auxiliary graph to select k nonadjacent cycle indices.The auxiliary graph joins indices whose cycles intersect or have an edge between them.Source: §6.1 · pp. 24–26
  • After removing the designated vertex covers and recursively deleting vertices of degree at most 1, the resulting semi-skeleton has at least 2(m − 1) − 24|I| branching vertices.Here I is the set of non-matching indices.Source: §6.1 · p. 26
  • If m ≥ 104k log k + 132k + 1, then G contains an induced packing of k even cycles.After deleting selected vertices and pruning low-degree vertices, the construction yields a semi-skeleton with enough branching vertices to apply the skeleton result.Source: §6.1 · pp. 26–27

6.2 Parity-breaking extensions

  • Every H*-path in G* is parity-breaking, and the constructed extension paths are pairwise vertex-disjoint while pH is induced in G.Maximality rules out parity-preserving extensions; the resulting auxiliary path-matching graph satisfies the consecutive serial property.Source: §6.2 · pp. 27–29
  • If q > 11m1 + 23g_theta(k), where m1 is the number of components of H*, then G contains an induced packing of k even cycles.The auxiliary graph’s even-N cycles yield even cycles in G when links are replaced by the corresponding parity-breaking paths.Source: §6.2 · pp. 29–30
  • Otherwise, either G contains an induced packing of k even cycles or there is a set Z of at most 4k vertices eliminating internally disjoint crossing or nested H*-paths.The paths considered lie in G* after removing the constructed extension paths and the closed H*-neighborhood of Z.Source: §6.2 · p. 30
  • The parity-breaking extension procedure produces an induced packing of k even cycles or a set Z of fewer than 4k vertices after which no two H˚-paths cross or nest with respect to F0 − N[Z].The selected pairs yield even cycles by taking symmetric differences of two odd cycles, and cycles from distinct iterations are vertex-disjoint and anticomplete.Source: §6.2 · p. 31

6.3 Bridges

  • Each even cycle lies in one H:-bridge, and the bridge procedure yields either k induced-packed even cycles or W of size at most 2(k − 1) whose closed neighborhood hits every even cycle in G:.Every H:-bridge has at most two attachments in H:; the procedure selects cycles from distinct bridges to obtain an induced packing.Source: §6.3 · pp. 32–33

6.4 Proof of Theorem 6.1

  • |X| = O(k log k) suffices to make G − N[X] even-cycle-free, unless G contains an induced packing of k even cycles.The proof combines a maximal bipartite ear decomposition with parity-breaking extensions and the bridge lemma; the supplied passages also describe polynomial-time construction procedures.Source: §6.4 · p. 34
  • The proof describes polynomial-time construction of the bipartite ear decomposition and procedures for finding an induced packing when the relevant size thresholds are met.The supplied runtime bounds include O(|V(G)|^5) for constructing the maximal bipartite ear decomposition and O(k|V(G)|^2 + k^2) for one packing procedure.Source: §6.4 · p. 35
  • The two outcomes of Theorem 6.1 can be found in polynomial time.If q > 11m1 + 23gθ(k), the proof finds k vertex-disjoint even-N cycles and the corresponding induced packing; otherwise, it greedily packs pairs of crossing or nested paths to construct the packing in polynomial time.Source: §6.4 · pp. 35–36

6.5 Corollary on tree-independence number

  • O(tk^2 log k) bounds the tree-independence number of every K1,t-free graph with no induced packing of k even cycles, with a witnessing decomposition computable in polynomial time.The proof removes the closed neighborhood of a set X of size O(k^2 log k), leaving a cactus of tree-width at most 2, then adds that neighborhood to every bag; K1,t-freeness bounds each bag's independence number by t|X| + 3.Source: §6.5 · p. 36
Loading 2610.22967v1…