pith. sign in

arxiv: 2605.19702 · v1 · pith:CBDYKGXJnew · submitted 2026-05-19 · 💻 cs.CC

A Hierarchy of Tinhofer Graphs: Separations and Membership Testing

Sutanay Bhattacharjee , Ameya Panse , Jayalal Sarma This is my paper

Pith reviewed 2026-05-20 01:43 UTC · model grok-4.3

classification 💻 cs.CC
keywords graph isomorphismcolor refinementTinhofer graphsindividualizationP-hardnessfixed-parameter tractabilitygraph hierarchy
0
0 comments X

The pith

A hierarchy inside Tinhofer graphs places each successive refinement level strictly above the last, with level-to-level membership P-hard and isomorphism testing FPT when a graph is within k of the top class.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper defines a graph as k-Tinhofer when k rounds of individualization followed by color refinement produce isomorphic colored graphs against every isomorphic copy, regardless of the vertices chosen at each step. These classes nest strictly inside one another, beginning with the refinable graphs at the first level and approaching the full Tinhofer class only at higher levels. Explicit constructions show that for every fixed k there are graphs that reach level k but fail at level k+1. The decision problem of whether a given k-Tinhofer graph belongs to the next level is P-hard under uniform AC^0 reductions. When the input is an (n-k)-Tinhofer graph, meaning it satisfies the Tinhofer property except for a parameter-k number of vertices, isomorphism testing against an arbitrary graph becomes fixed-parameter tractable.

Core claim

A graph G is k-Tinhofer if after any k rounds of individualization and refinement the resulting colored graphs remain isomorphic for every graph H isomorphic to G, irrespective of the individualization choices. The k-Tinhofer graphs therefore form a hierarchy lying between arbitrary graphs and Tinhofer graphs, with refinable graphs coinciding with the base level. For every fixed integer k there exist vertex-colored graphs that are k-Tinhofer but not (k+1)-Tinhofer. For every fixed k the problem of deciding whether a given k-Tinhofer graph is (k+1)-Tinhofer is P-hard under uniform AC^0 many-one reductions. Testing isomorphism between an (n-k)-Tinhofer graph G and an arbitrary graph H is fixed

What carries the argument

The k-Tinhofer property, which requires that the individualization-refinement process yields isomorphic colored graphs after exactly k steps for every choice sequence and every isomorphic copy, characterized both algebraically via orbit partitions of pointwise stabilizers and combinatorially via individualization-refinement trees and quotient graphs.

If this is right

  • For each fixed k there exist graphs whose full resolution under color refinement requires strictly more than k individualization rounds.
  • Ascent from the k-Tinhofer class to the (k+1)-Tinhofer class cannot be decided in polynomial time under the given reductions.
  • Isomorphism testing between a graph that differs from a Tinhofer graph in at most k vertices and any other graph can be solved in time f(k) times a polynomial in the input size.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The algebraic view through orbit partitions may connect the hierarchy to questions about computing stabilizers in permutation groups.
  • Parameterized algorithms for graph isomorphism could exploit the distance-to-Tinhofer parameter even when the exact level is unknown.
  • Practical color-refinement implementations might use the hierarchy to predict how many individualization steps are typically required on particular graph families.

Load-bearing premise

The property that the colored graphs remain isomorphic after k rounds must hold uniformly for every possible sequence of individualization choices and every isomorphic copy of the graph.

What would settle it

A polynomial-time algorithm that, for some fixed k, correctly decides whether an arbitrary k-Tinhofer graph is also (k+1)-Tinhofer would falsify the P-hardness result.

Figures

Figures reproduced from arXiv: 2605.19702 by Ameya Panse, Jayalal Sarma, Sutanay Bhattacharjee.

Figure 1
Figure 1. Figure 1: Containment of Tinhofer Hierarchy the stable coloring of the graph obtained after those individualizations. Such a stable coloring can also be represented by a quotient graph, which records the adjacency relations between the color classes in the stable coloring (see Section 2 for details). Let π and ρ denote the stable colorings of graphs G and H, respectively. Further, let πγ and ρµ denote the stable col… view at source ↗
Figure 2
Figure 2. Figure 2: Illustration of the CFI gadgets X3, X4 and IMP gadget Y3 3 k-Tinhofer graphs - Basic Properties and Characterization Let G and H be graphs. We run Tinhofer’s algorithm on G and H, starting with an initial round of color refinement. Subsequently, each step consists of selecting vertices in the two graphs from the same color class, individualizing them, and applying color refinement. Let G(k) and H(k) denote… view at source ↗
Figure 3
Figure 3. Figure 3: An illustration of graph H separating 2-Tinhofer from 3-Tinhofer. The left side and right side of the graph H contain a combination of the CFI graphs X3 and X4 in such a way that they share the input pairs {P1, P2} (for k = 2). Lemma 4.1. The vertex pair P0 is flipped if and only if the vertex pairs P3, P4, . . . , Pk+2 are flipped an odd number of times in H. Proof. Since X3 is a CFI gadget, flipping P0 f… view at source ↗
Figure 4
Figure 4. Figure 4: An illustration of the gadget ([AKRV17]) to replace gk = gi ∨ gj in our construction Next, we modify the graph G as follows: • Attach each intermediate output pair of AND/OR gate to the IMP gadget Yk+4, where the CFI gadget X3 is replaced by Xk+4. • Connect Pk+3 and Pk+4 to a CFI gadget X3 = (Pk+3, Pk+4, Pm). • Connect Pm to all constant 0 input vertices by two parallel edges. The resulting graph is N. An … view at source ↗
Figure 5
Figure 5. Figure 5: An illustration of the gadget that forms the foundation for constructing the graph that [PITH_FULL_IMAGE:figures/full_fig_p015_5.png] view at source ↗
read the original abstract

Color refinement is an important technique that works very well in practice for the graph isomorphism problem. Tinhofer graphs are the class of graphs for which refinement together with individualization correctly tests graph isomorphism against every other graph, irrespective of the choices of vertices made during individualization. Motivated by the fact that Tinhofer graphs form a natural boundary for efficient graph isomorphism tests based on color refinement, in this paper, we introduce a hierarchy of graph classes within the class of Tinhofer graphs. We call a graph $G$ $k$-Tinhofer if, after $k$ rounds of individualization and refinement, the resulting colored graphs remain isomorphic for every graph $H \cong G$, irrespective of the choices of vertices made during individualization. Arvind et al. (2017) studied a hierarchy of graph classes motivated by color refinement - discrete, amenable, Tinhofer, and refinable graphs. We show that the $k$-Tinhofer hierarchy lies between the class of all graphs and Tinhofer graphs, with refinable graphs coinciding with the first level of the hierarchy. We obtain two characterizations of $k$-Tinhofer graphs: an algebraic characterization in terms of orbit partitions induced by pointwise stabilizers of automorphism groups, and a combinatorial characterization in terms of individualization-refinement trees and quotient graphs. For every fixed integer $k \ge 0$, there exist vertex-colored graphs that are $k$-Tinhofer but not $(k + 1)$-Tinhofer. For every fixed integer $k \ge 0$, the problem of deciding whether a given $k$-Tinhofer graph is ($k + 1$)-Tinhofer is $P$-hard under uniform $\mathsf{AC^0}$ many-one reductions. We show that testing isomorphism between an $(n - k)$-Tinhofer graph $G$ and an arbitrary graph $H$ is fixed-parameter tractable with respect to the parameter $k$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 3 minor

Summary. The paper introduces the class of k-Tinhofer graphs for k ≥ 0: a graph G is k-Tinhofer if, after any sequence of k individualization-and-refinement steps, the resulting colored graphs are isomorphic to those obtained from every H ≅ G, irrespective of the individualization choices. It places this hierarchy strictly between the class of all graphs and the Tinhofer graphs (with refinable graphs coinciding with the k=0 level), supplies an algebraic characterization via orbit partitions of pointwise stabilizers and a combinatorial one via IR trees and quotient graphs, proves explicit separations showing graphs that are k-Tinhofer but not (k+1)-Tinhofer for each fixed k, establishes P-hardness of deciding (k+1)-membership for k-Tinhofer graphs under uniform AC⁰ many-one reductions, and shows that isomorphism testing between an (n-k)-Tinhofer graph G and an arbitrary H is FPT in the parameter k.

Significance. If the characterizations, separations, and complexity results hold, the work supplies a natural, fine-grained parameterization of the power of color refinement plus individualization for graph isomorphism. The algebraic and combinatorial characterizations, the uniform AC⁰ hardness, and the FPT isomorphism algorithm constitute concrete, falsifiable contributions that refine the boundary between tractable and intractable instances for practical isomorphism heuristics.

major comments (2)
  1. §3 (Algebraic characterization): the claim that the orbit-partition condition is equivalent to the k-Tinhofer property appears to rest on the pointwise stabilizer acting uniformly on all isomorphic copies; a short proof sketch or reference to the precise group-theoretic fact used would strengthen the equivalence.
  2. Theorem 5.2 (P-hardness): the uniform AC⁰ reduction from a known P-complete problem is stated at a high level; verifying that the constructed graphs remain k-Tinhofer for the chosen k requires checking that no shorter individualization sequence distinguishes them, which is only sketched.
minor comments (3)
  1. The definition of k-Tinhofer graphs in the abstract and §2 should explicitly quantify over all possible sequences of k individualizations and all isomorphic copies H to avoid ambiguity with the weaker “some sequence” reading.
  2. Notation for the IR tree and quotient graph in §4 is introduced without a small running example; adding one would improve readability for readers unfamiliar with the Arvind et al. (2017) framework.
  3. The FPT algorithm in §6 is described at the level of “dynamic programming over the IR tree of depth k”; a brief statement of the running-time bound in terms of n and k would make the result easier to cite.

Simulated Author's Rebuttal

2 responses · 0 unresolved

Thank you for the referee's thorough review and positive recommendation for minor revision. We respond to the major comments point by point below.

read point-by-point responses

  1. Referee: §3 (Algebraic characterization): the claim that the orbit-partition condition is equivalent to the k-Tinhofer property appears to rest on the pointwise stabilizer acting uniformly on all isomorphic copies; a short proof sketch or reference to the precise group-theoretic fact used would strengthen the equivalence.

    Authors: We appreciate the referee's suggestion to strengthen the algebraic characterization. The equivalence between the orbit-partition condition and the k-Tinhofer property is based on the pointwise stabilizer of k vertices in the automorphism group acting uniformly across all isomorphic copies, which follows directly from the definition of graph isomorphism and the group action. We will add a concise proof sketch in Section 3, including a reference to the relevant fact from permutation group theory (e.g., that stabilizers preserve orbits in the natural action). This revision will clarify the group-theoretic foundation without changing the main result. revision: yes

  2. Referee: Theorem 5.2 (P-hardness): the uniform AC⁰ reduction from a known P-complete problem is stated at a high level; verifying that the constructed graphs remain k-Tinhofer for the chosen k requires checking that no shorter individualization sequence distinguishes them, which is only sketched.

    Authors: We thank the referee for highlighting the need for more detail in the hardness proof. The reduction is designed such that the base graphs from the P-complete problem ensure that shorter individualization sequences cannot distinguish due to preserved symmetries. We will expand the verification in the proof of Theorem 5.2 to explicitly show that any sequence of length ≤ k fails to distinguish the constructed graphs, using the properties of the AC⁰ reduction. This will make the argument more self-contained. revision: yes

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper introduces the k-Tinhofer hierarchy via a new definition and derives its position relative to all graphs and Tinhofer graphs, along with algebraic/combinatorial characterizations, explicit separations, P-hardness under AC^0 reductions, and FPT isomorphism testing. These rest on the stated definition (requiring the isomorphism property after exactly k rounds for every individualization sequence and every isomorphic copy H), standard facts about automorphism groups, orbit partitions, IR trees, and quotient graphs, plus explicit constructions. No derivation reduces by construction to fitted inputs, self-citations that close the loop on the main claims, or renamings of prior results; the central results are internally consistent and self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper introduces new definitions for the k-Tinhofer hierarchy and relies on standard mathematical background from group theory and graph algorithms; no free parameters or invented physical entities are introduced.

axioms (2)
  • standard math Standard properties of automorphism groups, pointwise stabilizers, and orbit partitions hold for finite graphs.
    Invoked in the algebraic characterization of k-Tinhofer graphs.
  • standard math Individualization-refinement trees and quotient graphs behave according to established combinatorial rules for colored graphs.
    Used in the combinatorial characterization.

pith-pipeline@v0.9.0 · 5905 in / 1552 out tokens · 69047 ms · 2026-05-20T01:43:20.153431+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

41 extracted references · 41 canonical work pages · 2 internal anchors

  1. [1]

    Combinatorica , volume=

    An optimal lower bound on the number of variables for graph identifications , author=. Combinatorica , volume=

    work page

  2. [2]

    Computational Complexity , volume=

    Graph isomorphism, color refinement, and compactness , author=. Computational Complexity , volume=

    work page

  3. [3]

    Acta Mathematica Sinica , pages=

    Equitable partitions and orbit partitions , author=. Acta Mathematica Sinica , pages=

    work page

  4. [4]

    Canadian Journal of Mathematics , volume=

    Graphs of degree three with a given abstract group , author=. Canadian Journal of Mathematics , volume=

    work page

  5. [5]

    2017 , institution=

    Pushing the Boundaries of Combinatorial Graph Isomorphism Algorithms , author=. 2017 , institution=

    work page 2017

  6. [6]

    2016 , institution=

    Color Refinement and Graph Isomorphism Problem , author=. 2016 , institution=

    work page 2016

  7. [7]

    ACM Transactions on Computational Logic (TOCL) , volume=

    Graphs identified by logics with counting , author=. ACM Transactions on Computational Logic (TOCL) , volume=. 2021 , publisher=

    work page 2021

  8. [8]

    ACM Transactions on Computation Theory (TOCT) , volume=

    Graph isomorphism is not AC0-reducible to group isomorphism , author=. ACM Transactions on Computation Theory (TOCT) , volume=

    work page

  9. [9]

    Proceedings of the 48th Annual ACM Symposium on Theory of Computing (STOC) , pages=

    Graph isomorphism in quasi-polynomial time , author=. Proceedings of the 48th Annual ACM Symposium on Theory of Computing (STOC) , pages=

    work page

  10. [10]

    Proceedings of the tenth annual ACM symposium on Theory of computing , pages=

    On the n log n isomorphism technique (A Preliminary Report) , author=. Proceedings of the tenth annual ACM symposium on Theory of computing , pages=

    work page

  11. [11]

    Dell, Holger and Grohe, Martin and Rattan, Gaurav , journal=. Lov

    work page

  12. [12]

    Journal of computer and system sciences , volume=

    Isomorphism of graphs of bounded valence can be tested in polynomial time , author=. Journal of computer and system sciences , volume=

    work page

  13. [13]

    Proceedings of the ninth annual ACM symposium on Theory of computing , pages=

    Graph isomorphism, general remarks , author=. Proceedings of the ninth annual ACM symposium on Theory of computing , pages=

    work page

  14. [14]

    Pacific Journal of Mathematics , volume=

    Simple separable graphs , author=. Pacific Journal of Mathematics , volume=

    work page

  15. [15]

    The $k$-Dimensional Weisfeiler-Leman Algorithm

    The k -Dimensional Weisfeiler-Leman Algorithm , author=. arXiv preprint arXiv:1907.09582 , year=

    work page internal anchor Pith review Pith/arXiv arXiv 1907

  16. [16]

    Nauchno-Technicheskaya Informatsia (NTI) Series , volume=

    The reduction of a graph to canonical form and the algebra which appears therein , author=. Nauchno-Technicheskaya Informatsia (NTI) Series , volume=

    work page

  17. [17]

    Proceedings of the 22th Annual European Symposium on Algorithms (ESA) , pages=

    Dimension reduction via colour refinement , author=. Proceedings of the 22th Annual European Symposium on Algorithms (ESA) , pages=

    work page

  18. [18]

    Proceedings of the 28th AAAI Conference on Artificial Intelligence (AAAI) , pages=

    Power iterated color refinement , author=. Proceedings of the 28th AAAI Conference on Artificial Intelligence (AAAI) , pages=

    work page

  19. [19]

    Proceedings of the 14th Annual ACM Symposium on Theory of Computing (STOC) , pages=

    Isomorphism of graphs with bounded eigenvalue multiplicity , author=. Proceedings of the 14th Annual ACM Symposium on Theory of Computing (STOC) , pages=

    work page

  20. [20]

    Proceedings of the 6th Annual ACM Symposium on Theory of Computing (STOC) , pages=

    Linear time algorithm for isomorphism of planar graphs (preliminary report) , author=. Proceedings of the 6th Annual ACM Symposium on Theory of Computing (STOC) , pages=

    work page

  21. [21]

    Journal of Algorithms , volume=

    Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees , author=. Journal of Algorithms , volume=

    work page

  22. [22]

    North-Holland Mathematics Studies , volume=

    Distinguishing vertices of random graphs , author=. North-Holland Mathematics Studies , volume=

    work page

  23. [23]

    Discrete Applied Mathematics , volume=

    A note on compact graphs , author=. Discrete Applied Mathematics , volume=

    work page

  24. [24]

    The monotone and planar circuit value problems are log space complete for

    Goldschlager, Leslie M , journal=. The monotone and planar circuit value problems are log space complete for

    work page

  25. [25]

    2020 , school=

    Power and limits of the Weisfeiler-Leman algorithm , author=. 2020 , school=

    work page 2020

  26. [26]

    The Power of the

    Kiefer, Sandra and Neuen, Daniel , journal=. The Power of the

    work page

  27. [27]

    An Introduction to Lifted Probabilistic Inference , year=

    Color refinement and its applications , author=. An Introduction to Lifted Probabilistic Inference , year=

    work page

  28. [28]

    1990 , publisher=

    Describing graphs: A first-order approach to graph canonization , author=. 1990 , publisher=

    work page 1990

  29. [29]

    International Colloquium on Automata, Languages, and Programming (ICALP) , pages=

    Limitations of algebraic approaches to graph isomorphism testing , author=. International Colloquium on Automata, Languages, and Programming (ICALP) , pages=

    work page

  30. [30]

    Kiefer, Sandra , journal=. The

    work page

  31. [31]

    Journal of Graph Theory , volume=

    On recognizing graphs by numbers of homomorphisms , author=. Journal of Graph Theory , volume=

    work page

  32. [32]

    30th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) , pages=

    Universal covers, color refinement, and two-variable counting logic: Lower bounds for the depth , author=. 30th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) , pages=

    work page

  33. [33]

    Congressus Numerantium , volume=

    Practical graph isomorphism , author=. Congressus Numerantium , volume=

    work page

  34. [34]

    International Symposium on Mathematical Foundations of Computer Science , pages=

    Graphs identified by logics with counting , author=. International Symposium on Mathematical Foundations of Computer Science , pages=

    work page

  35. [35]

    Weisfeiler and

    Morris, Christopher and Ritzert, Martin and Fey, Matthias and Hamilton, William L and Lenssen, Jan Eric and Rattan, Gaurav and Grohe, Martin , booktitle=. Weisfeiler and

    work page

  36. [36]

    32nd International Symposium on Algorithms and Computation (ISAAC) , pages=

    A Characterization of Individualization-Refinement Trees , author=. 32nd International Symposium on Algorithms and Computation (ISAAC) , pages=

    work page

  37. [37]

    Weisfeiler and

    Morris, Christopher and Lipman, Yaron and Maron, Haggai and Rieck, Bastian and Kriege, Nils M and Grohe, Martin and Fey, Matthias and Borgwardt, Karsten , journal=. Weisfeiler and

    work page

  38. [38]

    ACM Transactions on Computation Theory (TOCT) , volume=

    The parameterized complexity of fixing number and vertex individualization in graphs , author=. ACM Transactions on Computation Theory (TOCT) , volume=

    work page

  39. [39]

    Bounding the

    Kiefer, Sandra and Neuen, Daniel , booktitle=. Bounding the

    work page

  40. [40]

    Graph isomorphisms in quasi-polynomial time

    Graph isomorphisms in quasi-polynomial time , author=. arXiv preprint arXiv:1710.04574 , year=

    work page internal anchor Pith review Pith/arXiv arXiv

  41. [41]

    Fundamenta Informaticae , volume=

    Pebble games with algebraic rules , author=. Fundamenta Informaticae , volume=. 2017 , publisher=

    work page 2017