Coarse Balanced Separators in Fat-Minor-Free Graphs

Source: arXiv:2604.11318 · Published 2026-04-13 · By Édouard Bonnet, Hung Le, Marcin Pilipczuk, Michał Pilipczuk

TL;DR

This paper addresses the metric structure of graphs excluding a fixed graph H as a fat minor, a coarse analogue of the classic minor exclusion in graph theory. Fat minors strengthen the notion of minors by requiring the subgraphs modeling vertices and edges of H in G to be at distance at least d rather than just disjoint. The main contribution is a structural result showing that any n-vertex weighted graph excluding H as a d-fat minor admits a balanced separator that is "coverable" by approximately O(n^{1/2+\epsilon}) balls of bounded radius. This generalizes the classic sqrt(n)-sized balanced separators known for H-minor-free graphs to the fat minor setting but with a mild loss of n^\epsilon factor. Moreover, the authors provide a randomized polynomial-time algorithm to either find such a separator or certify the presence of a d-fat minor of H. Two side results treat induced-minor-free graphs, proving similar separator covering results with different exponent regimes. Overall, the work introduces new techniques blending metric clustering (via Filtser’s algorithm), duality between concurrent flows and vertex separators (Leighton-Rao type arguments), and probabilistic constructions to realize fat minor models or separators, addressing a core open problem in coarse graph theory. This is the first general non-trivial separator theorem for fat-minor-free graphs, connecting geometric, combinatorial, and algorithmic insights.

Key findings

• For every graph H, integer d ≥ 1, and real ε > 0, every n-vertex weighted graph excluding H as a d-fat minor admits a balanced separator coverable by O(|H|^2 · n^{1/2 + ε}) balls of radius O(d/ε) (Theorem 2).
• The algorithm is randomized polynomial-time, outputting either such a balanced separator or a d-fat model of H in G.
• The balanced separator generalizes the classical O(√n) separator theorem for classic H-minor-free graphs but incurs a multiplicative n^ε overhead in the number of covering balls.
• The algorithmic construction uses a randomized metric clustering yielding clusters of strong diameter O(1/ε) with bounded overlap of O(n^ε), allowing reduction to a quotient graph.
• Applying the Leighton-Rao type concurrent flow vs. separator duality in the quotient graph yields either a sparse balanced separator lifted back to G or a concurrent flow witnessing a fat minor model.
• For graphs excluding H as an induced minor, balanced separators coverable by O(n^{2/3} log^{4/3} n) balls of radius 1 exist (Theorem 3).
• For K_{t,t}-induced-minor-free graphs, improved separators coverable by O_t(n^{1/2} log n) balls of radius 4 exist (Theorem 4).
• The paper proves a constructive probabilistic lemma showing the existence of crude fat minor models with positive constant probability via random sampling of flow paths (proof of Theorem 2).

Threat model

Adversaries are hypothetical graphs containing a d-fat model of H inside G, i.e., graphs violating the fat-minor-freeness condition. The algorithm tries to certify absence of such fat minors or find balanced separators. The adversary cannot hide such d-fat minors if they exist, as the algorithm either finds them or produces a separator obstructing them. The adversary has full knowledge of graph topology and weights but cannot violate underlying graph structural assumptions.

Methodology — deep read

The paper studies the metric and combinatorial structure of graphs excluding a fixed graph H as a fat minor, with parameter d controlling "fatness" (minimum distance between modeling subgraphs). The adversary is any graph containing a d-fat model of H; the goal is to characterize structural properties of graphs that exclude such fat minors.

Data consists of arbitrary n-vertex weighted graphs G, with vertex weights used only to measure balance of separators. No external datasets are needed.

The core concept is a d-fat minor model: connected subgraphs modeling vertices and edges of H with pairwise distances at least d except where vertices and edges intersect. The main technical tool is a randomized metric clustering (from Filtser 2017) that partitions G into connected clusters of strong diameter O(1/ε), while restricting overlaps of radius-2 balls to O(n^ε) clusters. This yields a quotient graph bG = G/X by contracting clusters.

The Leighton-Rao duality between multicommodity flows and balanced separators is adapted to vertex-capacitated flows on weighted, undirected graphs. Via a standard reduction (splitting vertices into two to simulate vertex capacities), a polynomial-time randomized algorithm either finds a concurrent flow with congestion γ or a small separator with sparsity O(log n/γ).

An iterative procedure (Lemma 4) repeatedly finds either a balanced separator of size O(W^2 log n/γ) or isolates a large induced subgraph admitting a concurrent flow with congestion γ, where W is total vertex weight.

Applying the clustering yields the quotient graph bG of size O(n). The algorithm is applied to bG with an appropriate congestion parameter γ = W^2 / (32 h c n^{1+ε})^{1/2} (h = size parameter depending on H) to yield either a small separator lifted to G or a concurrent flow in bG indicating presence of a fat minor.

The fat minor model is constructed probabilistically by sampling vertex images φ(u) from a vertex-weighted distribution and sampling paths π(e) using the concurrent flow distribution, then verifying with positive constant probability that the sampled collections satisfy fat minor distance constraints. The crude fat model on the subdivided graph ¨H is converted to a fat minor model of H.

Side results for induced minors use simpler connected partitions dominated by a single vertex, contract to sparse graphs, then apply previously known balanced separator theorems for induced-minor-free graphs.

All algorithms are randomized polynomial time, with correctness probability boosted by repetition. The approach essentially reduces separator finding in fat-minor-free graphs to separator finding in a quotient graph combined with probabilistic fat minor detection via flows.

Reproducibility is plausible given explicit polynomial-time randomized algorithms and known clustering and flow routines. The authors note that the crude fat minor construction can be made algorithmic as well. The paper refers extensively to prior works for technical building blocks but provides self-contained main proofs. A single example of sampling fat minor models from concurrent flows is detailed in the construction in Section 3.

Technical innovations

• Adaptation of Leighton-Rao product multicommodity flow vs balanced separator duality to vertex-capacitated weighted graphs via vertex splitting trick.
• Use of Filtser’s random metric clustering to produce connected partitions with bounded cluster overlap, enabling reduction to quotient graphs that preserve balance and allow separator lifting.
• Probabilistic construction of crude d-fat minor models via random sampling of vertices and paths from a concurrent flow with bounded congestion.
• Extension of balanced separator theory for classical minors to coarse notion of fat minors, showing sublinear separator covers exist despite quasi-isometry conjecture failure.
• A simple method to transform crude fat minor models of 2-subdivisions of H into actual fat minor models of H algorithmically.

Baselines vs proposed

• Classic H-minor-free graphs: Balanced separator size O(√n) (Lipton-Tarjan / Alon-Seymour-Thomas) vs Fat-minor-free graphs: Balanced separator coverable by O(|H|^2 · n^{1/2+ε}) balls of radius O(d/ε) (this work).
• Korhonen and Lokshtanov [11] result: H-induced-minor-free graph separator size O(√m log m) vs This work Theorem 3: n-vertex H-induced-minor-free graphs admit separators coverable by O(n^{2/3} log^{4/3} n) balls of radius 1.
• Chudnovsky et al. clustering + separator approach for K_{t,t}-induced-minor-free graphs: separator coverable by O_t(n^{1/2} log n) balls of radius 4 (Theorem 4).

Figures from the paper

Figures are reproduced from the source paper for academic discussion. Original copyright: the paper authors. See arXiv:2604.11318.

Fig 1 (page 1).

Fig 2 (page 1).

Limitations

• The main balanced separator bound includes an extra n^{ε} factor overhead compared to classical O(√n) separators; tightness of this factor is unknown.
• The probability of success of the randomized algorithm is only constant (≥ 1/8) per run; multiple repetitions required.
• No explicit evaluation of the constants hidden in big-O notation or practical efficiency of the algorithms.
• The proof depends on heavy algebraic and probabilistic tools requiring known structural properties; applicability to more general graph classes is undetermined.
• No adversarial robustness analysis or stability of separators under perturbations is discussed.
• Quasi-isometry conjecture failure means classical metric embedding techniques cannot fully extend; this work partially compensates but leaves the broader metric structure question open.

Open questions / follow-ons

• Can the n^{ε} multiplicative factor overhead in the number of balls covering balanced separators be removed to recover an optimal O(√n) analogue for fat-minor-free graphs?
• Is it possible to derandomize the algorithms or achieve higher success probability without repetitions?
• What are the implications of these fat-minor separator results for approximate distance or embedding properties of such graphs in metric spaces?
• Can the separator theorems be extended or refined to handle other coarse graph notions or more general forbidden substructures?

Why it matters for bot defense

From a bot-defense or CAPTCHA engineering perspective, this work offers a fundamentally new understanding of how certain classes of graphs (with complex, coarse forbidden minor structures) can be efficiently decomposed by small yet well-distributed separators. Such decompositions can motivate novel graph-based challenge constructions, where complexity and distance constraints ensure hardness for automated bots trying to traverse or connect components. The randomized polynomial-time algorithms for detecting separators or structured subgraphs provide potential practical tools for generating obfuscation schemes. However, the work is primarily theoretical and does not directly offer ready-to-use algorithms for bot detection. Instead, it enriches the mathematical toolkit for reasoning about network or interaction graphs with metric constraints, which chatbot or client behavior graphs might exhibit. Understanding balanced separators that cover nodes by bounded-radius balls can help design puzzle structures where connectivity queries become subtly constrained, leveraging fat minors as a complexity barrier. The coarse metric perspective may inspire CAPTCHAs leveraging spatial graph embeddings or network flow obstructions, enhancing defense mechanisms against automated traversal or simulation attacks. In short, the paper provides deep structural insights and algorithmic foundations that CAPTCHA researchers could adapt when designing graph-based bot detection challenges sensitive to metric separation properties.

Cite

@article{arxiv2604_11318,
  title={ Coarse Balanced Separators in Fat-Minor-Free Graphs },
  author={ Édouard Bonnet and Hung Le and Marcin Pilipczuk and Michał Pilipczuk },
  journal={arXiv preprint arXiv:2604.11318},
  year={ 2026 },
  url={https://arxiv.org/abs/2604.11318}
}

Read the full paper

• arXiv:2604.11318 (abstract)
• arXiv:2604.11318 (PDF)