pith. sign in

arxiv: 2606.31803 · v1 · pith:TC6OZ3NAnew · submitted 2026-06-30 · 💻 cs.CC

Counting Small Induced Subgraphs: Hardness of Symmetry-Based Properties

Radu Curticapean , Mingjun Liu This is my paper

Pith reviewed 2026-07-01 02:10 UTC · model grok-4.3

classification 💻 cs.CC
keywords induced subgraph counting#W[1]-hardnessautomorphism groupsparameterized complexityclique scaffoldsgraph propertiescounting problems
0
0 comments X

The pith

Counting induced k-vertex subgraphs with any fixed finite automorphism group is #W[1]-hard.

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

The paper proves that the counting problem IndSub(Φ) is #W[1]-hard whenever Φ requires the induced subgraph to have automorphism group equal to a fixed finite group Q. This covers the open case of rigid graphs, which have only the identity automorphism. The proof works by reducing from the k-clique problem using specially chosen restrictions of Φ called clique scaffolds. These restrictions ensure that the counted induced subgraphs correspond exactly to cliques while enforcing the desired symmetry condition. The result applies to every finite Q and settles the status for all such symmetry-based properties.

Core claim

We show that counting induced k-vertex graphs without nontrivial automorphisms is #W[1]-hard by constructing ``clique scaffolds'', i.e., problem-specific restrictions of the property that enable a reduction from the k-clique problem. More generally, we show that for every finite group Q, counting k-vertex induced subgraphs with automorphism group Q is #W[1]-hard.

What carries the argument

clique scaffolds: problem-specific restrictions of the target property that enable a direct reduction from the k-clique problem while preserving the exact automorphism group condition on the counted subgraphs.

If this is right

  • The known dichotomy for IndSub(Φ) now classifies every symmetry-based property as #W[1]-hard.
  • No fixed-parameter tractable algorithm exists for counting induced subgraphs with any prescribed automorphism group unless FPT equals W[1].
  • The same hardness holds uniformly for every finite group Q rather than only the trivial group.
  • The reduction technique works for any recursively enumerable property that fixes the automorphism group.

Where Pith is reading between the lines

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

  • The scaffold method may extend to properties defined by other algebraic constraints on subgraphs beyond groups.
  • Similar reductions could separate tractable and hard cases for counting problems on hypergraphs or other combinatorial objects.
  • The result implies that symmetry conditions alone are insufficient to make induced-subgraph counting tractable in the parameterized setting.

Load-bearing premise

The clique-scaffold construction produces a valid parameterized reduction from k-clique to the target counting problem without adding or losing solutions that satisfy the automorphism condition.

What would settle it

An algorithm that counts the induced k-vertex subgraphs with a fixed automorphism group Q in time f(k) n^O(1) for some computable f would falsify the #W[1]-hardness claim.

Figures

Figures reproduced from arXiv: 2606.31803 by Mingjun Liu, Radu Curticapean.

Figure 2
Figure 2. Figure 2: The key gadget of order ℓ. The figure depicts only the first and last segments of the edge families {aiai+1, cici+1 | i ∈ [2ℓ − 1]} ∪ {aibi, bici | i ∈ [2ℓ]}. All remaining non-clique edges are drawn explicitly. The red dashed edges represent the edges of the clique induced by the vertices c2i−1; these edges form K in Lemma 5.4. We are ready to apply the reduction from Section 3 to obtain Theorem 1.1. Proo… view at source ↗
read the original abstract

Jerrum and Meeks (TOCT, JCSS 2015) introduced the counting problems $\text{IndSub}(\Phi)$ for fixed graph properties $\Phi$: Given an input graph $G$ and $k\in\mathbb N$, count the $k$-vertex subsets $S \subseteq V(G)$ such that the induced subgraph $G[S]$ satisfies $\Phi$. For recursively enumerable $\Phi$, it is known that $\text{IndSub}(\Phi)$ is either #W[1]-hard or fixed-parameter tractable. A direct classification depending on $\Phi$ however still remains open. In particular, the status was open for the property of graphs without nontrivial automorphisms, also mentioned in a very recent survey on parameterized counting by Roth (Comput.~Sci.~Rev.~2026). This is a natural property that evades all currently known techniques for proving #W[1]-hardness, including a general toolkit based on Fourier analysis that was very recently introduced by Curticapean and Neuen (SODA~2025). In this paper, we show that counting induced $k$-vertex graphs without nontrivial automorphisms is #W[1]-hard by constructing ``clique scaffolds'', i.e., problem-specific restrictions of the property that enable a reduction from the $k$-clique problem. More generally, we show that for every finite group $Q$, counting $k$-vertex induced subgraphs with automorphism group $Q$ is #W[1]-hard.

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

1 major / 2 minor

Summary. The paper proves that IndSub(Φ) is #W[1]-hard when Φ is the property that a graph has trivial automorphism group (i.e., is rigid), by a reduction from k-Clique that employs a new 'clique scaffold' construction. It further shows that for any fixed finite group Q, IndSub(Φ_Q) is #W[1]-hard where Φ_Q requires the automorphism group to be exactly isomorphic to Q. The result applies to recursively enumerable properties and resolves an open case that evaded prior Fourier-analytic and other hardness techniques.

Significance. If the reduction is correct, the result closes a natural open case in the dichotomy for IndSub(Φ) problems that had been highlighted in recent surveys. The clique-scaffold technique, which tailors restrictions of Φ to the source problem, is a potentially reusable idea for other symmetry-based or automorphism-constrained counting problems and strengthens the toolkit beyond general-purpose methods.

major comments (1)
  1. [Abstract and reduction construction] The central reduction (described in the abstract and presumably detailed in the main technical sections) must establish a parameter-preserving bijection or exact cancellation between the counted rigid induced subgraphs in the constructed instance and the k-cliques in the source graph. The skeptic concern that scaffold vertices/edges could create additional rigid k-subgraphs whose count depends on scaffold parameters rather than solely on the number of k-cliques is load-bearing; an explicit argument ruling this out (e.g., via structural characterization of all rigid induced k-subgraphs in the scaffolded graph) is required for the claim to hold.
minor comments (2)
  1. [Introduction] Notation for the property Φ and the groups Q should be introduced with a short formal definition early in the paper to aid readability.
  2. [Introduction] The paper should include a brief comparison table or paragraph contrasting the new scaffold technique with the Fourier-analytic toolkit of Curticapean and Neuen (SODA 2025) to clarify why the latter does not apply directly.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their thorough review and for recognizing the significance of resolving this open case in the IndSub(Φ) dichotomy. We address the major comment on the reduction construction below.

read point-by-point responses

  1. Referee: [Abstract and reduction construction] The central reduction (described in the abstract and presumably detailed in the main technical sections) must establish a parameter-preserving bijection or exact cancellation between the counted rigid induced subgraphs in the constructed instance and the k-cliques in the source graph. The skeptic concern that scaffold vertices/edges could create additional rigid k-subgraphs whose count depends on scaffold parameters rather than solely on the number of k-cliques is load-bearing; an explicit argument ruling this out (e.g., via structural characterization of all rigid induced k-subgraphs in the scaffolded graph) is required for the claim to hold.

    Authors: We appreciate the referee's focus on ensuring the reduction's correctness. The clique-scaffold technique (detailed in Sections 3–5) is constructed so that the scaffold vertices and edges are fixed and the property Φ is restricted in a problem-specific manner that forces any rigid induced k-subgraph to include a k-clique from the input; the proof shows a bijection between k-cliques and the counted rigid subgraphs, with no additional rigid k-subgraphs possible due to the automorphism constraints enforced by the scaffold. To directly address the concern about potential extraneous structures, we will revise the manuscript by adding an explicit structural characterization lemma (new Lemma 4.3) that enumerates all possible rigid induced k-subgraphs in the scaffolded graph and proves none exist outside those corresponding to input cliques. This makes the argument self-contained without altering the core reduction. revision: yes

Circularity Check

0 steps flagged

No circularity: standard reduction from #W[1]-hard k-Clique via explicit construction

full rationale

The derivation establishes #W[1]-hardness of IndSub(Φ) for Φ = {graphs with trivial automorphism group} (and fixed Aut = Q) by exhibiting a reduction from k-Clique that uses problem-specific 'clique scaffolds'. This is a direct, parameter-preserving reduction whose correctness is claimed to rest on the construction itself rather than on any self-referential definition, fitted parameter, or load-bearing self-citation. The cited prior works (Jerrum-Meeks, Curticapean-Neuen) supply only the general dichotomy framework and the observation that the property evades existing toolkits; they are not invoked to justify the scaffold reduction or to import a uniqueness theorem. No equation or claim reduces to its own input by construction, and the result is externally falsifiable via the standard definition of #W[1]-hardness.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The result rests on the standard assumption that k-clique is #W[1]-hard and on the correctness of the new clique-scaffold reduction; no free parameters or invented entities are mentioned.

axioms (1)
  • domain assumption k-Clique is #W[1]-hard
    Standard background assumption in parameterized counting complexity used as the source problem for the reduction.

pith-pipeline@v0.9.1-grok · 5802 in / 1119 out tokens · 24651 ms · 2026-07-01T02:10:03.597051+00:00 · methodology

discussion (0)

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

Reference graph

Works this paper leans on

70 extracted references · 61 canonical work pages

  1. [1]

    Count on

    Radu Curticapean , editor =. Count on. Proceedings of the 2024. 2024 , url =. doi:10.1137/1.9781611977912.74 , timestamp =

    work page doi:10.1137/1.9781611977912.74 2024

  2. [2]

    Probabilistic algorithms for sparse polynomials , booktitle =

    Richard Zippel , editor =. Probabilistic algorithms for sparse polynomials , booktitle =. 1979 , url =. doi:10.1007/3-540-09519-5\_73 , timestamp =

    work page doi:10.1007/3-540-09519-5 1979

  3. [3]

    DeMillo and Richard J

    Richard A. DeMillo and Richard J. Lipton , title =. Inf. Process. Lett. , volume =. 1978 , url =. doi:10.1016/0020-0190(78)90067-4 , timestamp =

    work page doi:10.1016/0020-0190(78)90067-4 1978

  4. [4]

    Schwartz , title =

    Jacob T. Schwartz , title =. J. 1980 , url =. doi:10.1145/322217.322225 , timestamp =

    work page doi:10.1145/322217.322225 1980

  5. [5]

    2005 , url =

    Michael Mitzenmacher and Eli Upfal , title =. 2005 , url =. doi:10.1017/CBO9780511813603 , isbn =

    work page doi:10.1017/cbo9780511813603 2005

  6. [6]

    Monotone Arithmetic Complexity of Graph Homomorphism Polynomials , booktitle =

    Balagopal Komarath and Anurag Pandey and Chengot Sankaramenon Rahul , editor =. Monotone Arithmetic Complexity of Graph Homomorphism Polynomials , booktitle =. 2022 , url =. doi:10.4230/LIPIcs.ICALP.2022.83 , timestamp =

    work page doi:10.4230/lipics.icalp.2022.83 2022

  7. [7]

    C. S. Bhargav and Shiteng Chen and Radu Curticapean and Prateek Dwivedi , editor =. Monotone Bounded-Depth Complexity of Homomorphism Polynomials , booktitle =. 2025 , url =. doi:10.4230/LIPIcs.MFCS.2025.19 , timestamp =

    work page doi:10.4230/lipics.mfcs.2025.19 2025

  8. [8]

    CoRR , volume =

    Anuj Dawar and Benedikt Pago and Tim Seppelt , title =. CoRR , volume =. 2025 , url =. doi:10.48550/arXiv.2502.06740 , eprinttype =. 2502.06740 , timestamp =

    work page doi:10.48550/arxiv.2502.06740 2025

  9. [9]

    2012 , url =

    Stasys Jukna , title =. 2012 , url =. doi:10.1007/978-3-642-24508-4 , isbn =

    work page doi:10.1007/978-3-642-24508-4 2012

  10. [10]

    Marc Roth , title =. Comput. Sci. Rev. , volume =. 2026 , url =

    2026

  11. [11]

    Counting Small Induced Subgraphs: Scorpions Are Easy but Not Trivial , booktitle =

    Radu Curticapean and Simon D. Counting Small Induced Subgraphs: Scorpions Are Easy but Not Trivial , booktitle =. 2025 , url =. doi:10.4230/LIPIcs.ESA.2025.96 , timestamp =

    work page doi:10.4230/lipics.esa.2025.96 2025

  12. [12]

    Can You Link Up With Treewidth? , booktitle =

    Radu Curticapean and Simon D. Can You Link Up With Treewidth? , booktitle =. 2025 , url =. doi:10.4230/LIPIcs.STACS.2025.28 , timestamp =

    work page doi:10.4230/lipics.stacs.2025.28 2025

  13. [14]

    Counting Small Induced Subgraphs with Edge-Monotone Properties , booktitle =

    Simon D. Counting Small Induced Subgraphs with Edge-Monotone Properties , booktitle =. 2024 , url =. doi:10.1145/3618260.3649644 , timestamp =

    work page doi:10.1145/3618260.3649644 2024

  14. [15]

    2024 , url =

    Jacob Focke and Marc Roth , title =. 2024 , url =. doi:10.1137/22m1512211 , timestamp =

    work page doi:10.1137/22m1512211 2024

  15. [16]

    G\". The. Proc. ACM Manag. Data , volume =. 2024 , url =

    2024

  16. [17]

    Homomorphism-Distinguishing Closedness for Graphs of Bounded Tree-Width , booktitle =

    Daniel Neuen , editor =. Homomorphism-Distinguishing Closedness for Graphs of Bounded Tree-Width , booktitle =. 2024 , url =. doi:10.4230/LIPIcs.STACS.2024.53 , timestamp =

    work page doi:10.4230/lipics.stacs.2024.53 2024

  17. [18]

    2024 , url =

    Marc Roth and Johannes Schmitt and Philip Wellnitz , title =. 2024 , url =. doi:10.1137/20m1365624 , timestamp =

    work page doi:10.1137/20m1365624 2024

  18. [19]

    On the Power of the

    Matthias Lanzinger and Pablo Barcel. On the Power of the. CoRR , volume =. 2023 , url =. doi:10.48550/arXiv.2309.17053 , eprinttype =. 2309.17053 , timestamp =

    work page doi:10.48550/arxiv.2309.17053 2023

  19. [20]

    Vikraman Arvind and Frank Fuhlbr. On the. Inf. Comput. , volume =. 2022 , url =. doi:10.1016/j.ic.2021.104803 , timestamp =

    work page doi:10.1016/j.ic.2021.104803 2022

  20. [21]

    Counting Induced Subgraphs: An Algebraic Approach to

    Julian D. Counting Induced Subgraphs: An Algebraic Approach to. Algorithmica , volume =. 2022 , url =. doi:10.1007/s00453-021-00894-9 , timestamp =

    work page doi:10.1007/s00453-021-00894-9 2022

  21. [22]

    Recent advances on the graph isomorphism problem , booktitle =

    Martin Grohe and Daniel Neuen , editor =. Recent advances on the graph isomorphism problem , booktitle =. 2021 , url =. doi:10.1017/9781009036214.006 , timestamp =

    work page doi:10.1017/9781009036214.006 2021

  22. [23]

    Detecting and Counting Small Subgraphs, and Evaluating a Parameterized Tutte Polynomial: Lower Bounds via Toroidal Grids and Cayley Graph Expanders , booktitle =

    Marc Roth and Johannes Schmitt and Philip Wellnitz , editor =. Detecting and Counting Small Subgraphs, and Evaluating a Parameterized Tutte Polynomial: Lower Bounds via Toroidal Grids and Cayley Graph Expanders , booktitle =. 2021 , url =. doi:10.4230/LIPIcs.ICALP.2021.108 , timestamp =

    work page doi:10.4230/lipics.icalp.2021.108 2021

  23. [24]

    Vikraman Arvind and Frank Fuhlbr. On. J. Comput. Syst. Sci. , volume =. 2020 , url =. doi:10.1016/j.jcss.2020.04.003 , timestamp =

    work page doi:10.1016/j.jcss.2020.04.003 2020

  24. [25]

    2020 , url =

    Sandra Kiefer , title =. 2020 , url =. doi:10.1145/3436980.3436982 , timestamp =

    work page doi:10.1145/3436980.3436982 2020

  25. [26]

    Mančinska and D

    Marc Roth and Johannes Schmitt and Philip Wellnitz , editor =. Counting Small Induced Subgraphs Satisfying Monotone Properties , booktitle =. 2020 , url =. doi:10.1109/FOCS46700.2020.00128 , timestamp =

    work page doi:10.1109/focs46700.2020.00128 2020

  26. [27]

    Algorithmica , volume =

    Marc Roth and Johannes Schmitt , title =. Algorithmica , volume =. 2020 , url =. doi:10.1007/s00453-020-00676-9 , timestamp =

    work page doi:10.1007/s00453-020-00676-9 2020

  27. [28]

    2019 , url =

    Marc Roth , title =. 2019 , url =. doi:10.22028/D291-28348 , timestamp =

    work page doi:10.22028/d291-28348 2019

  28. [29]

    Homomorphisms are a good basis for counting small subgraphs , booktitle =

    Radu Curticapean and Holger Dell and D. Homomorphisms are a good basis for counting small subgraphs , booktitle =. 2017 , url =. doi:10.1145/3055399.3055502 , timestamp =

    work page doi:10.1145/3055399.3055502 2017

  29. [30]

    On the Combinatorial Power of the

    Martin F. On the Combinatorial Power of the. Algorithms and Complexity - 10th International Conference,. 2017 , url =. doi:10.1007/978-3-319-57586-5\_22 , timestamp =

    work page doi:10.1007/978-3-319-57586-5 2017

  30. [31]

    2017 , url =

    Martin Grohe , title =. 2017 , url =. doi:10.1017/9781139028868 , isbn =

    work page doi:10.1017/9781139028868 2017

  31. [32]

    Mark Jerrum and Kitty Meeks , title =. Comb. , volume =. 2017 , url =. doi:10.1007/s00493-016-3338-5 , timestamp =

    work page doi:10.1007/s00493-016-3338-5 2017

  32. [33]

    Chandra Chekuri and Julia Chuzhoy , title =. J. 2016 , url =. doi:10.1145/2820609 , timestamp =

    work page doi:10.1145/2820609 2016

  33. [34]

    The Parity of Set Systems Under Random Restrictions with Applications to Exponential Time Problems , booktitle =

    Andreas Bj. The Parity of Set Systems Under Random Restrictions with Applications to Exponential Time Problems , booktitle =. 2015 , url =. doi:10.1007/978-3-662-47672-7\_19 , timestamp =

    work page doi:10.1007/978-3-662-47672-7 2015

  34. [35]

    2015 , url =

    Radu Curticapean , title =. 2015 , url =. doi:10.22028/D291-26612 , timestamp =

    work page doi:10.22028/d291-26612 2015

  35. [36]

    12 Fedor V

    Marek Cygan and Fedor V. Fomin and Lukasz Kowalik and Daniel Lokshtanov and D. Parameterized Algorithms , publisher =. 2015 , url =. doi:10.1007/978-3-319-21275-3 , isbn =

    work page doi:10.1007/978-3-319-21275-3 2015

  36. [37]

    Mark Jerrum and Kitty Meeks , title =. J. Comput. Syst. Sci. , volume =. 2015 , url =. doi:10.1016/j.jcss.2014.11.015 , timestamp =

    work page doi:10.1016/j.jcss.2014.11.015 2015

  37. [38]

    2015 , url =

    Mark Jerrum and Kitty Meeks , title =. 2015 , url =. doi:10.1145/2786017 , timestamp =

    work page doi:10.1145/2786017 2015

  38. [39]

    Wang and Richard Ryan Williams and Huacheng Yu , editor =

    Virginia Vassilevska Williams and Joshua R. Wang and Richard Ryan Williams and Huacheng Yu , editor =. Finding Four-Node Subgraphs in Triangle Time , booktitle =. 2015 , url =. doi:10.1137/1.9781611973730.111 , timestamp =

    work page doi:10.1137/1.9781611973730.111 2015

  39. [40]

    Complexity of Counting Subgraphs: Only the Boundedness of the Vertex-Cover Number Counts , booktitle =

    Radu Curticapean and D. Complexity of Counting Subgraphs: Only the Boundedness of the Vertex-Cover Number Counts , booktitle =. 2014 , url =. doi:10.1109/FOCS.2014.22 , timestamp =

    work page doi:10.1109/focs.2014.22 2014

  40. [41]

    Fomin and Saket Saurabh , title =

    Omid Amini and Fedor V. Fomin and Saket Saurabh , title =. 2012 , url =. doi:10.1137/100789403 , timestamp =

    work page doi:10.1137/100789403 2012

  41. [42]

    On recognizing graphs by numbers of homomorphisms , journal =

    Zdenek Dvor. On recognizing graphs by numbers of homomorphisms , journal =. 2010 , url =. doi:10.1002/jgt.20461 , timestamp =

    work page doi:10.1002/jgt.20461 2010

  42. [43]

    Can You Beat Treewidth? , journal =

    D. Can You Beat Treewidth? , journal =. 2010 , url =. doi:10.4086/toc.2010.v006a005 , timestamp =

    work page doi:10.4086/toc.2010.v006a005 2010

  43. [44]

    Automata, Languages and Programming, 35th International Colloquium,

    Yijia Chen and Marc Thurley and Mark Weyer , editor =. Understanding the Complexity of Induced Subgraph Isomorphisms , booktitle =. 2008 , url =. doi:10.1007/978-3-540-70575-8\_48 , timestamp =

    work page doi:10.1007/978-3-540-70575-8 2008

  44. [45]

    Parameterized Complexity Theory , series =

    J. Parameterized Complexity Theory , series =. 2006 , url =. doi:10.1007/3-540-29953-X , isbn =

    work page doi:10.1007/3-540-29953-x 2006

  45. [46]

    Juedes and Iyad A

    Jianer Chen and Benny Chor and Mike Fellows and Xiuzhen Huang and David W. Juedes and Iyad A. Kanj and Ge Xia , title =. Inf. Comput. , volume =. 2005 , url =. doi:10.1016/j.ic.2005.05.001 , timestamp =

    work page doi:10.1016/j.ic.2005.05.001 2005

  46. [47]

    Russell Impagliazzo and Ramamohan Paturi and Francis Zane , title =. J. Comput. Syst. Sci. , volume =. 2001 , url =. doi:10.1006/jcss.2001.1774 , timestamp =

    work page doi:10.1006/jcss.2001.1774 2001

  47. [48]

    Space Time Tradeoffs for Graph Properties , booktitle =

    Yevgeniy Dodis and Sanjeev Khanna , editor =. Space Time Tradeoffs for Graph Properties , booktitle =. 1999 , url =. doi:10.1007/3-540-48523-6\_26 , timestamp =

    work page doi:10.1007/3-540-48523-6 1999

  48. [49]

    Roche , title =

    Joachim von zur Gathen and James R. Roche , title =. Comb. , volume =. 1997 , url =. doi:10.1007/BF01215917 , timestamp =

    work page doi:10.1007/bf01215917 1997

  49. [50]

    Noam Nisan and Mario Szegedy , title =. Comput. Complex. , volume =. 1994 , url =. doi:10.1007/BF01263419 , timestamp =

    work page doi:10.1007/bf01263419 1994

  50. [51]

    1987 , url =

    Marvin Minsky and Seymour Papert , title =. 1987 , url =. doi:10.7551/mitpress/11301.001.0001 , isbn =

    work page doi:10.7551/mitpress/11301.001.0001 1987

  51. [52]

    Seymour , title =

    Neil Robertson and Paul D. Seymour , title =. J. Comb. Theory. 1986 , url =. doi:10.1016/0095-8956(86)90030-4 , timestamp =

    work page doi:10.1016/0095-8956(86)90030-4 1986

  52. [53]

    Kostochka , title =

    Alexandr V. Kostochka , title =. Comb. , volume =. 1984 , url =. doi:10.1007/BF02579141 , timestamp =

    work page doi:10.1007/bf02579141 1984

  53. [54]

    Valiant , title =

    Leslie G. Valiant , title =. Theor. Comput. Sci. , volume =. 1979 , url =. doi:10.1016/0304-3975(79)90044-6 , timestamp =

    work page doi:10.1016/0304-3975(79)90044-6 1979

  54. [55]

    Rivest and Jean Vuillemin , title =

    Ronald L. Rivest and Jean Vuillemin , title =. Theor. Comput. Sci. , volume =. 1976 , url =. doi:10.1016/0304-3975(76)90053-0 , timestamp =

    work page doi:10.1016/0304-3975(76)90053-0 1976

  55. [56]

    and Grohe, Martin and Fey, Matthias and Borgwardt, Karsten , TITLE =

    Morris, Christopher and Lipman, Yaron and Maron, Haggai and Rieck, Bastian and Kriege, Nils M. and Grohe, Martin and Fey, Matthias and Borgwardt, Karsten , TITLE =. J. Mach. Learn. Res. , FJOURNAL =. 2023 , NUMBER =

    2023

  56. [57]

    2014 , PAGES =

    O'Donnell, Ryan , TITLE =. 2014 , PAGES =. doi:10.1017/CBO9781139814782 , URL =

    work page doi:10.1017/cbo9781139814782 2014

  57. [58]

    Lovász.Large networks and graph limits, volume 60 ofColloq

    Lov\'asz, L\'aszl\'o , TITLE =. 2012 , PAGES =. doi:10.1090/coll/060 , URL =

    work page doi:10.1090/coll/060 2012

  58. [59]

    International

    Agrawal, Manindra , TITLE =. International. 2006 , ISBN =. doi:10.4171/022-3/48 , URL =

    work page doi:10.4171/022-3/48 2006

  59. [60]

    and Harman, Glyn and Pintz, J\'anos , TITLE =

    Baker, Roger C. and Harman, Glyn and Pintz, J\'anos , TITLE =. Proc. London Math. Soc. (3) , FJOURNAL =. 2001 , NUMBER =. doi:10.1112/plms/83.3.532 , URL =

    work page doi:10.1112/plms/83.3.532 2001

  60. [61]

    Hans J. Pr. Excluding induced subgraphs. Random Structures Algorithms , FJOURNAL =. 1992 , NUMBER =. doi:10.1002/rsa.3240030104 , URL =

    work page doi:10.1002/rsa.3240030104 1992

  61. [62]

    Asymptotic enumeration of

    Erd. Asymptotic enumeration of. Colloquio

  62. [63]

    Shen-Orr and Shalev Itzkovitz and Nadav Kashtan and Dmitri B

    Ron Milo and Shai S. Shen-Orr and Shalev Itzkovitz and Nadav Kashtan and Dmitri B. Chklovskii and Uri Alon , title =. Science , volume =. 2002 , url =

    2002

  63. [64]

    Herstellung von

    Frucht, Robert , journal=. Herstellung von

  64. [65]

    1994 , publisher=

    Automorphism groups, isomorphism, reconstruction , author=. 1994 , publisher=

    1994

  65. [66]

    Counting Small Induced Subgraphs: Hardness via Fourier Analysis , booktitle =

    Radu Curticapean and Daniel Neuen , editor =. Counting Small Induced Subgraphs: Hardness via Fourier Analysis , booktitle =. 2025 , url =. doi:10.1137/1.9781611978322.122 , timestamp =

    work page doi:10.1137/1.9781611978322.122 2025

  66. [67]

    More Asymmetry Yields Faster Matrix Multiplication , booktitle =

    Josh Alman and Ran Duan and Virginia. More Asymmetry Yields Faster Matrix Multiplication , booktitle =. 2025 , url =. doi:10.1137/1.9781611978322.63 , timestamp =

    work page doi:10.1137/1.9781611978322.63 2025

  67. [68]

    1978 , url =

    Alon Itai and Michael Rodeh , title =. 1978 , url =. doi:10.1137/0207033 , timestamp =

    work page doi:10.1137/0207033 1978

  68. [69]

    1985 , url=

    On the complexity of the subgraph problem , author=. 1985 , url=

    1985

  69. [70]

    Acta Math

    Asymmetric graphs , author=. Acta Math. Acad. Sci. Hungar , volume=

  70. [71]

    Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , chapter =

    Simon Döring and Dániel Marx and Philip Wellnitz , title =. Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , chapter =. doi:10.1137/1.9781611978322.121 , URL =

    work page doi:10.1137/1.9781611978322.121 2025