Graph theory shows limits on even cycle packings and blockers
An Erdős-Pósa theorem for induced packings of even cycles
Discrete Mathematics
Summary
This paper deals with a special problem in graphs: finding multiple separate even loops or stopping all even loops by choosing a small group of points. The authors prove that either you can find many even loops that don't share points or edges, or you can find a relatively small set of points that touch every even loop. They also provide an algorithm that quickly finds one of these outcomes in any graph. Additionally, they show this insight helps understand the structure of certain graphs that avoid specific patterns, with efficient ways to analyze them.
What this means in practice
- •For graph algorithm developers: Use the provided algorithm to find many separate even cycles or a small vertex set intersecting all even cycles efficiently in large graphs.
- •For network reliability engineers: Identify critical nodes intersecting all even feedback loops to improve network robustness in systems modeled by special graph classes.
A theory result. No direct application yet.
Authors
Jungho Ahn, Lars Jaffke, O-joung Kwon, Paloma T. de Lima, Hyemi Park
Abstract
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.