PaperlayerView exact revision on arXiv

Source-linked AI summary

Structure Theorem and Isomorphism Test for Graphs with Excluded Topological Subgraphs

Martin Grohe, Dániel Marx

arXiv:1111.1109v2cs.DScs.DMmath.CO

TL;DR

Graphs excluding a fixed H as a topological subgraph are broader than minor-excluding classes, raising the question of whether they admit useful structure and algorithms. The paper proves a decomposition theorem and develops invariant treelike decompositions for its Graph Isomorphism application. It gives polynomial-time Graph Isomorphism for each fixed H, while the running-time exponent depends on H.

  • Problem

    Topological-subgraph exclusion describes a broader class than minor exclusion, so it is unclear whether such graphs admit a comparable structure theorem and useful algorithms.

    Source: §1 · pp. 1–2

  • Method

    The paper decomposes the graphs into almost-embeddable or almost-bounded-degree torsos and uses invariant treelike decompositions with bag canonization for Graph Isomorphism.

    Source: §1 · pp. 2–3, §10 · p. 44

  • Results

    For every fixed H, Graph Isomorphism is solvable in polynomial time on graphs excluding H as a topological subgraph.

    Source: §1 · p. 3

  • Takeaways & Limitations

    The isomorphism result generalizes the known polynomial-time cases for bounded-degree and H-minor-free graphs to topological-subgraph exclusion.

    Source: §10 · p. 44

    The isomorphism algorithm’s running-time exponent depends on H, and improving it to f(H)·n^O(1) is identified as open.

    Source: §10 · p. 45

Abstract

from arXiv · show

We generalize the structure theorem of Robertson and Seymour for graphs excluding a fixed graph $H$ as a minor to graphs excluding $H$ as a topological subgraph. We prove that for a fixed $H$, every graph excluding $H$ as a topological subgraph has a tree decomposition where each part is either "almost embeddable" to a fixed surface or has bounded degree with the exception of a bounded number of vertices. Furthermore, we prove that such a decomposition is computable by an algorithm that is fixed-parameter tractable with parameter $|H|$. We present two algorithmic applications of our structure theorem. To illustrate the mechanics of a "typical" application of the structure theorem, we show that on graphs excluding $H$ as a topological subgraph, Partial Dominating Set (find $k$ vertices whose closed neighborhood has maximum size) can be solved in time $f(H,k)\cdot n^{O(1)}$ time. More significantly, we show that on graphs excluding $H$ as a topological subgraph, Graph Isomorphism can be solved in time $n^{f(H)}$. This result unifies and generalizes two previously known important polynomial-time solvable cases of Graph Isomorphism: bounded-degree graphs and $H$-minor free graphs. The proof of this result needs a generalization of our structure theorem to the context of invariant treelike decomposition.

1 Introduction

The paper extends graph-structure methods from minor exclusion to topological-subgraph exclusion, a broader setting that includes every 3-regular graph when H is K5. Its decomposition theorem supports algorithmic applications, including Partial Dominating Set and Graph Isomorphism, with the latter requiring invariant treelike decompositions.

1 Introduction

  • Topological-subgraph exclusion is broader than minor exclusion: every 3-regular graph excludes K5 as a topological subgraph, and the paper describes the class as a natural generalization of bounded-degree and minor-excluding classes.The motivation also notes that topological-subgraph-closed classes do not have the finite excluded-minor characterization described for minor-closed classes [34].Source: §1 · pp. 1–3
  • Theorem 1.1 decomposes each graph excluding a fixed H as a topological subgraph into torsos that are almost embeddable or bounded-degree except for a bounded number of vertices.The surface-embeddable branch is stated in the informal theorem; the bounded-degree branch permits boundedly many exceptional vertices.Source: §1 · p. 2
  • The decomposition can be computed in time f(H)·|V(G)|^O(1).Source: §1 · p. 2
  • Partial Dominating Set on graphs excluding H as a topological subgraph is solvable in time f(k,H)·n^O(1).The paper describes a bottom-up dynamic program over the decomposition, using linear-time algorithms on bounded-degree and almost-embeddable graphs.Source: §1 · p. 2
  • Invariant treelike decompositions address the failure of ordinary decompositions to be isomorphic for isomorphic input graphs, enabling the paper’s canonization strategy.The Lifting Lemma combines invariant decompositions with canonization algorithms for the bags.Source: §1 · p. 3
  • Theorem 1.3 gives a polynomial-time Graph Isomorphism algorithm for graphs excluding a fixed H as a topological subgraph.Source: §1 · p. 3

2 Preliminaries

The preliminaries establish graph notation and distinguish minors from topological subgraphs, then state algorithms for detecting each structure.

2 Preliminaries

  • A graph H is a minor of G if it can be obtained by vertex and edge deletions and edge contractions; equivalently, an image uses disjoint connected branch sets that touch for adjacent vertices.Source: §2 · p. 4
  • For fixed H, the stated algorithms find an H-minor image or a subdivision of H in cubic time, if one exists.The minor-testing result is attributed to, and the subdivision-testing result to.Source: §2 · pp. 4–5
  • H is a topological subgraph of G when a subdivision of H is a subgraph of G, equivalently when H can be obtained by deletions and dissolving degree-2 vertices.Source: §2 · p. 4

3 Tree Decompositions

This section defines tree decompositions and the torso representation used to describe the structure of each bag.

3 Tree Decompositions

  • A tree decomposition assigns vertex sets to tree nodes so each graph vertex occurs in a nonempty connected set of bags and every graph edge lies in a bag.Source: §3 · p. 5
  • A tree decomposition can also be represented by separator and component sets at each node, with the stated conditions equivalent to the usual bag-based definition.This triple representation provides the transition to the treelike decompositions used later.Source: §3 · p. 5
  • The torso at a node augments the graph induced by its bag with edges making the separator and child cones into cliques.A decomposition over a graph class has every torso in that class.Source: §3 · p. 6

4 Local and Global Structure Theorems

The section develops local and global structure theorems for graphs excluding a fixed graph as a topological subgraph, using bounded-adhesion decompositions. The decomposition algorithms may instead return a subdivision obstruction, and the local results include an isomorphism-equivariant decomposition procedure.

4 Local and Global Structure Theorems

  • For every fixed H, graphs excluding H as a topological subgraph admit a bounded-adhesion tree decomposition whose torsos include the bounded-high-degree case.An algorithm computes such a decomposition in f(|H|)·n^O(1) time, or finds a subdivision of H.Source: §4 · p. 6
  • The local theorem either finds a Kk subdivision or computes a bounded-adhesion star decomposition of G∪K[S] with S in the center and nested tip apices.The center torso either excludes a Ke(k)-minor or has at most c(k) vertices of degree greater than d(k).Source: §4 · p. 7

4.1 Almost Embeddable Graphs and a Refined Structure Theorem

  • The refined theorem gives each torso either an almost-embeddable structure or at most c vertices of degree greater than d, with an algorithm returning the decomposition or an H subdivision.The first type has an apex set of size at most s and is almost embedded in a surface of bounded Euler genus.Source: §4.1 · p. 9

4.2 The Three Local Decomposition Lemmas

  • The Local Structure Theorem is built by stacking three decomposition lemmas, each yielding a corresponding decomposition case or an obstruction passed to the next lemma.The excluded-minor lemma either finds a Kℓ-minor attached to the unbreakable set or gives a star decomposition whose center torso excludes a Ke*(ℓ,m)-minor.Source: §4.2 · pp. 9, 12
  • The excluded-minor star-decomposition algorithm is invariant under isomorphisms of its graph and designated set.For isomorphic inputs, the resulting star-decomposition trees correspond under an isomorphism that maps each separator and apex set to its counterpart.Source: §4.2 · p. 12
  • In f(k)|V(G)|^O(1) time, the algorithm finds a K_k-subdivision or a star decomposition with adhesion less than |X| and at most c*(k) high-degree vertices in the center torso.The input includes an m-unbreakable set X of size 3m−2 and a K_ℓ-minor image m-attached to X; X lies in the center bag.Source: §4.2 · pp. 12–13
  • For isomorphic inputs mapping X to X′, the algorithm returns decompositions whose tree, bag, and torso mappings correspond under the input isomorphism.The correspondence preserves both σ and α at every mapped tree node.Source: §4.2 · p. 13
  • The final lemma removes high-degree vertices from the center bag via separations; if at least k cannot be removed, their proximity to the clique-minor image yields a clique subdivision.The preceding clique-image search also faces the challenge of avoiding new clique-minor images when shrinking the bag.Source: §4.2 · pp. 12–13
  • The Local Structure Theorem applies the earlier decomposition algorithms in sequence, ending with either a star decomposition or a K_k-subdivision.After the first lemma, it tries the clique-image decomposition lemma, then applies the bounded-degree lemma to the resulting attached clique-minor image.Source: §4.2 · p. 13

5 Tangles

The section develops tangles as a way to describe separations around unbreakable sets, then establishes boundary properties used in later decomposition arguments. It also defines oracle operations and a unique minimum-order set associated with a target set.

5 Tangles

  • A tangle of order m orients every separation of order below m, with its small sides constrained so that three cannot cover the graph.For tangles defined by an m-unbreakable set X of size at least 3m−2, each oriented separation has at most as many vertices of X on its small side as the separator has.Source: §5 · pp. 13–14
  • The paper uses tangles defined by unbreakable sets, for which membership and min-cut queries have implementable oracles.The membership oracle runs in polynomial time, while the min-cut oracle runs in time 2^|X|·|V(G)|^O(1).Source: §5 · pp. 14–15
  • Because a tangle can have exponentially many separations, the section specifies oracle access, including queries for a low-order separation disjoint from forbidden vertices.A min-cut query seeks a separation in the tangle that places specified sets on opposite sides and avoids F at the separator.Source: §5 · p. 14

5.1 Boundaries and separations

  • The separation S_G(X) uses G[N[X]] on one side and the graph outside X on the other, and its order equals the boundary size ∂(X).The boundary inequalities are used for uncrossing arguments in Section 6.Source: §5.1 · pp. 15–16
  • For any target X that a tangle separation removes, W(X) is the unique minimum-boundary set containing X whose associated separation lies in the tangle.Given a min-cut oracle, this set can be found in polynomial time.Source: §5.1 · p. 17
  • Boundary submodularity lets the intersection of two minimum-order sets containing X remain a qualifying set, yielding the minimal W(X).The section also establishes boundary inequalities for set differences separated from the other set’s closed neighborhood.Source: §5.1 · pp. 15–17
  • If G[X] is connected and W(X) is defined, then G[W(X)] is connected.Source: §5.1 · p. 17

6 Proofs of the Local Decomposition Lemmas

This section proves the local decomposition lemmas needed to complete the global structure theorem and establish invariance conditions for later isomorphism and canonization results. It constructs tangle-respecting star decompositions that control adhesion and center structure, including invariant decompositions with only a bounded number of high-degree center vertices or a clique subdivision.

6.1 Using a clique minor

  • If t≥r²+r, the clique-minor crossbar lemma constructs in polynomial time a K_r-minor whose branch sets each contain exactly one vertex of R, under the stated no-small-separation condition.The proof gives t(r)=r²+r, while the cited result [32, (5.3)] provides a better O(r) bound.Source: §6.1 · pp. 18–19

6.2 Star decomposition with clique-minor free center

  • When e>2m, each K_e-minor image removed by a tangle has a unique connected minimum-boundary region W(I), computable in polynomial time given a min-cut oracle.For e>t(m)+m, the associated separation is also generic, and a witness can be found in polynomial time.Source: §6.2 · pp. 19, 21
  • For tangle-removed K_e-minor images, the torso after deleting their associated regions contains exactly the minor images not removed by those regions, with models translatable both ways in polynomial time.The associated regions are W(I_i), and the torso is formed on the graph outside their union.Source: §6.2 · p. 21
  • For every ℓ,m, an f(ℓ,m)·|V(G)|^O(1)-time algorithm computes a T-respecting star decomposition whose center torso excludes a K_e′(ℓ,m)-minor and whose output is invariant under isomorphisms of (G,T).The algorithm is given a min-cut oracle for a tangle of order m.Source: §6.2 · p. 22
  • For Lemma 4.9, the proof uses Lemma 6.10’s tangle-respecting star decomposition, then moves X into the center while preserving adhesion below |X| and excluding a clique minor there.If the algorithm instead returns a K_ℓ-minor image not removed by the tangle defined by X, that image is m-attached to X; the construction also preserves the invariance condition.Source: §6.2 · pp. 23–24

6.3 Star decomposition with a bounded-degree center

  • If at least k high-degree vertices cannot be removed from the tangle by small-order separations, Lemma 6.11 finds a subdivision of K_k in polynomial time.The argument extends k selected vertices into cliques, applies a minor-finding lemma, then converts the resulting disjoint paths back into a subdivision in the original graph.Source: §6.3 · pp. 24–25
  • Lemma 6.12 either finds a subdivision of K_k or computes an isomorphism-invariant T-respecting star decomposition whose center has at most k vertices of degree above d′(k).Under an isomorphism of the graph and tangle, the resulting decompositions correspond with their adhesions and parts mapped by that isomorphism.Source: §6.3 · p. 25
  • Claim 4 bounds |σT(t_i)| by a=O(k^6) for each 1≤i≤p, while Claim 6 gives every vertex v∉Z degree at most d′(k)=O(k^7) in τ(s).Source: §6.3 · p. 27
  • To obtain Lemma 4.10, the proof applies Lemma 6.12 to the tangle defined by X and moves X into the center, yielding adhesion below |X| and at most k + |X| center vertices above the degree bound.If the algorithm finds a K_k-subdivision, it returns that instead; otherwise the resulting decomposition satisfies the required bounds and invariance condition.Source: §6.3 · p. 28

7 Partial Dominating Set

The paper gives a fixed-parameter algorithm for Partial Dominating Set on graphs excluding a fixed H as a topological subgraph. It uses bottom-up dynamic programming on the structure theorem’s decomposition, combining methods for almost-embeddable and almost-bounded-degree torsos.

7 Partial Dominating Set

  • The algorithm lifts techniques for almost-embeddable and bounded-degree graphs to the larger class by using the new structure theorem.The authors describe the algorithmic techniques as standard; the structure theorem makes them applicable to this class.Source: §7 · p. 29
  • The dynamic program summarizes each subgraph with a k-profile recording its best weighted neighborhood value for each budget and boundary assignment.The profile extends the problem with binary cost and value functions, allowing boundary vertices to be free or excluded from the objective.Source: §7 · p. 29
  • For almost-embeddable torsos, a layering argument reduces profile computation to bounded-treewidth instances using bounded local treewidth.The treewidth bound grows with the number of distance layers considered.Source: §7 · pp. 29, 31
  • For almost-bounded-degree torsos, random coloring isolates regions so profile computation can use bounded-treewidth methods.The coloring procedure can be repeated to reduce error, and the authors state it can be derandomized.Source: §7 · pp. 29, 31, 32
  • Theorem 1.2 gives an f(k,H)·n^O(1)-time algorithm for Partial Dominating Set on graphs excluding H as a topological subgraph.The algorithm computes k-profiles bottom-up over the decomposition to obtain the optimum.Source: §7 · pp. 28, 32
  • Bounded degeneracy alone does not yield this tractability: the paper notes Partial Dominating Set is W[1]-hard parameterized by k and d on d-degenerate graphs.An algorithm for that broader class would imply an f(k)-time-parameterized algorithm for Maximum Independent Set, even though the reduction produces a 2-degenerate graph.Source: §7 · p. 32

8 Invariant Treelike Decompositions

The section introduces treelike decompositions to obtain decompositions compatible with graph isomorphisms, which ordinary tree decompositions need not provide. It proves an invariant, polynomial-time computable decomposition theorem for graphs excluding a fixed topological subgraph.

8 Invariant Treelike Decompositions

  • A treelike decomposition uses a directed acyclic graph rather than a rooted tree, and its invariance requires isomorphic input graphs to have isomorphic decompositions respecting separators and components.The decomposition mapping is required to carry the separator and component sets along each graph isomorphism.Source: §8 · pp. 32–34
  • A width-2 tree decomposition of C5 cannot be invariant under its automorphisms, while the treelike example contains all its automorphic images.The example illustrates why a treelike decomposition can supply multiple tree decompositions where a single invariant tree decomposition is unavailable.Source: Figure 8.1 · p. 33, §8 · p. 34
  • The Invariant Decomposition Theorem gives a polynomial-time computable invariant treelike decomposition of bounded adhesion for graphs excluding H as a topological subgraph.The theorem states that every torso meets one of three conditions, including a condition with at most c vertices of degree greater than d.Source: §8 · p. 34
  • The construction organizes nodes into bounded, bounded-degree, and excluded-minor types before assembling the decomposition.The proof then establishes that the resulting mapping is polynomial-time computable and invariant.Source: §8 · p. 35
  • The proof establishes invariance by extending each graph isomorphism to the decomposition nodes and preserving their separators and components.The induced correspondence also preserves the decomposition’s child relation.Source: §8 · p. 37

9 Canonization

The section develops polynomial-time strong canonisation tools for graph classes, including a lifting lemma for transferring canonisation from decomposition parts to whole graphs. It applies these tools to graphs excluding a fixed topological subgraph, using invariant treelike decompositions.

Strong canonisation for bounded-degree graphs

  • Graphs of maximum degree at most d admit polynomial-time strong canonisation, via a gadget reduction from weighted structures to bounded-degree graphs.The constructed graph H_A has maximum degree at most max{ k_i + 5, ∑_{i∈[m]}(d + 1)^{k_i} }, where k_i is the arity of relation R_i.Source: §9 · pp. 38–40

Strong canonisation for excluded topological subgraphs

  • For every graph H, graphs excluding H as a topological subgraph admit polynomial-time strong canonisation.The proof reduces to H = K_k for k ≥ 4, using the minor-free canonisation result and a gadget construction.Source: §9 · p. 40

Strong canonisation with few high-degree vertices

  • Graphs with at most c vertices of degree greater than d admit polynomial-time strong canonisation for all c,d ∈ N.This follows by treating such graphs as enlargements of bounded-degree graphs.Source: §9 · p. 41

Strong canonisation for enlargements

  • For any polynomial-time decidable class C with polynomial-time strong canonisation, its k-enlargements admit polynomial-time strong canonisation for every k.The proof establishes the one-vertex enlargement case and extends it to all k by induction.Source: §9 · p. 41

Lifting Lemma

  • If A admits polynomial-time strong canonisation and C has polynomial-time computable invariant treelike decompositions over A of bounded adhesion, then C admits polynomial-time strong canonisation.The Lifting Lemma is the section’s general mechanism for extending canonisation from decomposition parts to the whole graph.Source: §9 · p. 41

9 Canonization

  • The canonical copy is isomorphism-invariant and polynomial-time computable because the decomposition mapping is polynomial-time computable.It is selected as the lexicographically minimal structure among isomorphic structures associated with nodes whose boundary is empty and whose region is the whole graph.Source: §9 · pp. 43–44
  • Graphs excluding any fixed H as a topological subgraph admit polynomial-time strong canonisation.The proof applies the lifting lemma to polynomial-time invariant treelike decompositions over a canonisable class.Source: §9 · p. 44
  • The invariant decomposition theorem and lifting lemma yield strong canonisation for graphs excluding H as a topological subgraph.The decompositions are over a class of adhesion a, and are computable in polynomial time.Source: §9 · p. 44

10 Conclusions

The paper gives structure and algorithmic results for graphs excluding a fixed topological subgraph, including a polynomial-time isomorphism test. It also identifies limits on extending the test and on its parameter dependence.

10 Conclusions

  • Graphs excluding a fixed topological subgraph decompose into torsos with excluded minors and torsos where all but a bounded number of vertices have bounded degree.The theorem’s proof is self-contained and avoids enormous hidden constants, although its algorithmic version depends on a minor test with astronomical constant factors.Source: §10 · p. 44
  • The Partial Dominating Set problem is fixed-parameter tractable on graph classes excluding a fixed topological subgraph.Source: §10 · p. 44
  • The paper proves a polynomial-time isomorphism test for graph classes excluding a fixed topological subgraph, using invariant treelike decompositions.Source: §10 · p. 44
  • A generic machinery derives global invariant structure from local structure lemmas, then lifts canonisation algorithms from torsos to whole graphs.The machinery could apply to richer graph classes if their local structure admits polynomial-time canonisation.Source: §10 · p. 45
  • The isomorphism test is unlikely to extend to all bounded-expansion classes, where isomorphism can be as hard as on general graphs.Subdividing each edge of two n-vertex graphs with n new vertices yields bounded-expansion graphs whose isomorphism is equivalent to that of the originals.Source: §10 · p. 45
  • The isomorphism test’s running-time exponent depends on the excluded graph H; improving this to f(H)·n^O(1) remains an open question.The paper notes that even this improvement for maximum-degree k graphs is a significant open question.Source: §10 · p. 45
Loading 1111.1109v2…