Pith. sign in

REVIEW 4 minor 36 references

Counting Small Induced Subgraphs: Scorpions Are Easy but Not Trivial

T0 review · 0 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Scorpion subgraphs are countable in polynomial time, disproving the #IndSub hardness conjecture for all non-meager properties.

desk verdict A genuine counterexample to a published conjecture, with a clean O(n^4) counting algorithm and a plausible revised classification; the math holds, aside from one binomial-index typo. read the letter →

arxiv 2505.22300 v1 pith:DQDLFZWZ submitted 2025-05-28 cs.CC cs.DS

Radu Curticapean , Simon Döring , Daniel Neuen This is my paper
classification cs.CCcs.DS MSC 05C3005C8568Q1768Q27
keywords inducedsubgraphcountingparameterizedcomplexityscorpiongraphs#W[1]-hardnessgraphpropertiesETHandSETHlowerboundsvertexcovernumberalternatingenumerator
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper's central claim is that a well-known hardness conjecture about counting induced subgraphs is false. The conjecture said that every computable graph property that is non-meager—nontrivial on infinitely many pattern sizes k—makes the counting problem #IndSub(Φ) #W[1]-hard. The authors exhibit scorpion graphs, a family introduced in the 1970s in connection with the evasiveness conjecture, and prove that counting induced scorpions on k vertices can be done in O($n^{4}$) time for all k, even though the scorpion property is non-meager. They generalize the construction to ℓ-scorpions with running time O(ℓ $n^{{ℓ+3}}$), prove matching lower bounds under ETH and SETH, and propose a new conjecture based on the vertex-cover number of the subgraph-basis expansion. If correct, the paper overturns the dichotomy that all nontrivial properties are equally hard, replacing it with a spectrum of polynomial complexities.

What carries the argument

The load-bearing mechanism is the uniqueness lemma for the body, tail, and sting of an ℓ-scorpion: the body is the unique vertex of degree k−ℓ−1, the sting is the unique degree-1 vertex among the non-neighbors of the body, and the tail vertices are identified by their distances from the sting. This turns the counting problem into a partition of the solution set into classes X_q indexed by tuples q=(b,t_1,...,t_ℓ,s), where each |X_q| is a binomial coefficient C(|X_G(q)|, k−ℓ−2) with X_G(q) the vertices adjacent to the body and to no tail vertex or sting. The matching lower bounds use an external Hamming-weight theorem: a property that avoids many distinct edge counts on slice k cannot be counted in O($n^{{δ d}}$) under ETH. The updated conjecture is stated in the subgraph basis, where the alternating enumerator bΦ(H) gives the coefficient of H in the expansion of #IndSub(Φ) as a linear combination of ordinary subgraph counts, and the relevant complexity measure is the maximum vertex-cover number τΦ(k) of graphs with nonzero coefficient.

What would settle it

Run the O($n^{4}$) scorpion-counting algorithm against exhaustive enumeration on every graph with up to, say, 12 vertices and every k; a single mismatch would refute Theorem 3.3. More conceptually, find an ℓ-scorpion with two distinct tuples (b,t_1,...,t_ℓ,s) both satisfying Definition 3.1, which would break the uniqueness lemma on which the whole partition argument rests.

Watch

Extended reading notes

Core claim

Scorpions refute Conjecture 1.1. An ℓ-scorpion is a graph with a uniquely identifiable body, a path of ℓ tail vertices, a sting, and arbitrary legs adjacent only to the body; Lemma 3.2 shows these three parts are unique. Because of this uniqueness, every induced ℓ-scorpion in an input graph is classified by a single tuple (b,t_1,...,t_ℓ,s), and for a fixed tuple the number of ways to choose the legs is a binomial coefficient depending only on the common neighborhood of the path. Summing over all tuples gives an O(ℓ $n^{{ℓ+3}}$) algorithm, and for ℓ=1 this is O($n^{4}$). Since scorpions exist in every slice k≥ℓ+4 and not every k-vertex graph is a scorpion, the property is non-meager, so the conjecture that all non-meager computable properties are #W[1]-hard is false. In the subgraph basis, the paper further shows that the nonzero coefficients sit exactly on 'scorpion fossils', whose vertex-cover number is ℓ+2; this explains the tractability and motivates the updated Conjecture 4.2.

Load-bearing premise

The strongest external input is the Hamming-weight lower bound of Theorem 3.4, imported from two prior papers: if that theorem fails or its constants degenerate on the scorpion weight profile, the 'not trivial' half of the paper collapses, although the O($n^{4}$) counterexample to Conjecture 1.1 would still stand.

Editorial extensions

If this is right

  • Conjecture 1.1 is false: there are non-meager computable properties whose induced-subgraph counting problem is solvable in polynomial time, not merely fixed-parameter tractable.
  • For every fixed ℓ≥1, counting induced ℓ-scorpions takes O(ℓ n^{ℓ+3}) time, and under ETH no O(n^{αℓ}) algorithm exists for a fixed α>0, so the exponent ℓ+3 is essentially tight.
  • Letting ℓ grow with k, for instance ℓ≈√k, produces properties whose counting problem has complexity n^{Θ(√k)} under ETH, showing intermediate complexity between FPT and the old hardness picture.
  • Under SETH, for each fixed ℓ≥3 there is no O(n^{ℓ+2−ε}) algorithm for counting ℓ-scorpions, pinning the polynomial degree to within one.
  • The updated Conjecture 4.2 predicts that #IndSub(Φ) is #W[1]-hard exactly when the maximum vertex-cover number τΦ(k) among graphs with nonzero alternating enumerator is unbounded; scorpions have τΨℓ(k)=ℓ+2, consistent with their tractability.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Beyond the paper, the partition-by-unique-signature idea should apply to any property whose satisfying graphs contain a constant-size, uniquely identifiable skeleton with the remaining vertices unconstrained; the directed sink example and scorpions are two instances of one pattern.
  • If Conjecture 4.2 holds, hardness proofs for #IndSub(Φ) would only need to find one graph per k with nonzero alternating enumerator and large vertex-cover number, a weaker requirement than the treewidth-based arguments currently used.
  • The ℓ-scorpion family hints that natural graph properties can have smoothly tunable polynomial exponents, so a definitive classification may need to describe a complexity spectrum rather than a simple FPT-versus-hard dichotomy.
  • A computational check of Lemma 4.3 on small k—verifying that nonzero coefficients occur exactly on scorpion fossils—would give concrete evidence about the scope of the updated conjecture.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

0 major / 4 minor

Summary. This paper studies the parameterized problem #IndSub(Phi) of counting induced k-vertex subgraphs satisfying a fixed graph property Phi. The authors refute the conjecture of Dörfler et al. and Roth et al. that every non-meager computable property yields a #W[1]-hard problem. After a directed-graph warm-up with sink vertices, they define ell-scorpions, prove a uniqueness lemma for the body, tail, and sting, and partition the family of induced ell-scorpions into O(n^{ell+2}) classes whose sizes are explicit binomial coefficients. This yields an O(ell n^{ell+3}) algorithm, in particular O(n^4) for ordinary scorpions. They combine this with an external Hamming-weight lower bound to derive ETH-based lower bounds and a SETH-based lower bound for fixed ell, and they formulate a refined conjecture (Conjecture 4.2) that hardness is governed by unbounded vertex-cover number in the subgraph basis. The main new contribution is the first non-meager property proven to have polynomial-time induced-subgraph counting, contradicting the previous conjecture.

Significance. The central claim is significant: it disproves a published conjecture and shows that the tractability frontier for #IndSub is richer than previously believed. The main algorithm is self-contained, parameter-free, and based on a clean uniqueness-and-partition argument that is easy to verify. The lower-bound half relies on two external theorems that are cited with explicit hypotheses, and the paper additionally proves the supporting computation tau_{Psi_ell}(k)=ell+2, which positions the scorpion properties correctly with respect to the new conjecture. The historical connection to the evasiveness conjecture is a nice feature. The main caveat is that Conjecture 4.2 is new and unproven, and the SETH lower bound is only sketched, but neither affects the correctness of the refutation of Conjecture 1.1.

minor comments (4)
  1. [Section 3.2, Eq. (3)] The displayed formula for |X_q| has a typesetting error: the lower index of the binomial coefficient is printed as k-ell+2, but the accompanying proof text and the count of k-ell-2 additional leg vertices show that the intended lower index is k-ell-2. Please fix this display.
  2. [Proposition 4.5] The proof is presented as a sketch and delegates the core reduction to [3, Theorem 24.1] and [8, Lemma A.3] without stating the exact statements. Since this SETH lower bound is one of the paper's advertised 'not trivial' results, please expand the argument or explicitly restate the external lemmas and the padding reduction so that the proof is checkable without consulting the full-version arXiv papers.
  3. [Section 4.2, Prop. 4.7 and Section 4.1, Prop. 4.5] There are two small reference errors: in the last line of the proof of Proposition 4.5, 'Theorem 4.3' should be 'Lemma 4.3', and in the last line of the proof of Proposition 4.7, 'Theorem 4.2' should be 'Conjecture 4.2'.
  4. [Remark 3.6] The remark says the bound in Theorem 3.4 is 'essentially tight' because the upper bound is O(n^{ell+3}); it may help to spell out that the lower bound has exponent linear in ell with a small constant, so the tightness is up to constant factors. This is not a correctness issue.

Circularity Check

0 steps flagged · score 1.0 of 10

No material circularity: the scorpion-counting algorithm is self-contained and the refutation of Conjecture 1.1 does not reduce to a fit or to the cited lower-bound theorems.

full rationale

The paper's central claim—that scorpions refute Conjecture 1.1—rests on Theorem 3.3, which is derived entirely from the definition of an ℓ-scorpion (Definition 3.1). The proof partitions the target family of induced k-vertex subgraphs by the tuple (b, t1, ..., tℓ, s) using the in-paper uniqueness lemma (Lemma 3.2, proven by degree and distance arguments), and each class is counted by a binomial expression involving NG(b) minus the neighborhoods of tail and sting. No parameter is fitted to data, and no step presupposes the truth of the conjecture being refuted; the O(n^4) algorithm for ordinary scorpions (ℓ=1) therefore stands on its own. The lower-bound half (Corollary 3.5, Corollary 3.7, Proposition 4.5) does cite external theorems from [9, Lemma 5.1], [6, Theorem 7.1], and [8, Lemma A.3], which involve overlapping authors, so self-citation is present. However, these theorems are general-purpose hardness results whose assumptions (Hamming-weight gaps on slices, vertex-cover support of the alternating enumerator, colorful-subgraph reductions) do not mention scorpions; the paper itself supplies only the computation of the weight profile of Ψℓ, plugging that profile into a published theorem. These citations qualify as independent support under the review rules, and even if the lower bounds failed, the upper bound and the refutation of Conjecture 1.1 would survive unchanged. The only textual blemish is a typesetting slip in displayed equation (3), where the lower binomial index appears as k−ℓ+2 while the surrounding proof text and the counting argument require k−ℓ−2; this does not affect any derivation since the proof text uses the correct value. No enumerated circularity pattern can be exhibited with the required quote-and-reduction evidence, so the score is 1, reflecting non-load-bearing self-citation rather than circularity.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

The central counterexample is self-contained: no fitted parameters and no hidden explanatory entities. The lower bounds rest on cited independent work and standard complexity hypotheses. Conjecture 4.2 is explicitly conjectural and is not used as an axiom for the main theorems.

assumptions (6)
  • domain assumption Exponential-Time Hypothesis (ETH): 3-SAT requires 2^(Omega(n)) time.
    Used in Corollary 3.5 and Corollary 3.7 to rule out O(n^(alpha*ell)) algorithms for ell-scorpions; a standard unproved complexity hypothesis.
  • domain assumption Strong Exponential-Time Hypothesis (SETH): k-SAT requires essentially 2^n time for large k.
    Used in Proposition 4.5 for the n^(ell+2-epsilon) lower bound on ell-scorpion counting.
  • standard math Theorem 3.4 ([9, Lemma 5.1] and [6, Theorem 7.1]): avoiding many Hamming weights on a slice forces an ETH-based lower bound for #IndSub.
    External published lower-bound machinery, accepted without proof. Load-bearing for the claims that scorpion counting is not trivial and has tuned complexity.
  • standard math Lemma A.3 of [8]: colorful subgraph decision problems reduce to #IndSub with an oracle.
    Used in Proposition 4.5 to transfer SETH lower bounds for augmented bicliques to scorpion counting.
  • standard math Theorem 1.1 of [5]: counting H-subgraphs takes O(n^(tau(H)+1)) time.
    Used for Theorem 4.1 and for the fixed-parameter tractability side of the new conjecture.
  • standard math Rosenfeld's independence bound for regular graphs [31]: alpha(H) <= k/2 + 1.
    Used in Proposition 4.7 to bound vertex-cover number below; this proposition is hypothetical under Conjecture 4.2.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Counting Small Induced Subgraphs: Scorpions Are Easy but Not Trivial." pith.science (2026). https://pith.science/paper/DQDLFZWZ

@misc{pith2026250522300,
  author       = {Pith},
  title        = {Pith review of: Counting Small Induced Subgraphs: Scorpions Are Easy but Not Trivial},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/DQDLFZWZ}},
  note         = {Machine review of arXiv:2505.22300}
}
abstract

We consider the parameterized problem $\#$IndSub$(\Phi)$ for fixed graph properties $\Phi$: Given a graph $G$ and an integer $k$, this problem asks to count the number of induced $k$-vertex subgraphs satisfying $\Phi$. D\"orfler et al. [Algorithmica 2022] and Roth et al. [SICOMP 2024] conjectured that $\#$IndSub$(\Phi)$ is $\#$W[1]-hard for all non-meager properties $\Phi$, i.e., properties that are nontrivial for infinitely many $k$. This conjecture has been confirmed for several restricted types of properties, including all hereditary properties [STOC 2022] and all edge-monotone properties [STOC 2024]. In this work, we refute this conjecture by showing that scorpion graphs, certain $k$-vertex graphs which were introduced more than 50 years ago in the context of the evasiveness conjecture, can be counted in time $O(n^4)$ for all $k$. A simple variant of this construction results in graph properties that achieve arbitrary intermediate complexity assuming ETH. We formulate an updated conjecture on the complexity of $\#$IndSub$(\Phi)$ that correctly captures the complexity status of scorpions and related constructions.

Figures

Figures reproduced from arXiv: 2505.22300 by the authors.

Figure 1
Figure 1. A graph H is an ℓ-scorpion if it has the above form: Dashed edges may be present in H or not, solid edges must be present, and non-drawn edges must not be present. Graph Theory. We follow standard textbooks [11] for graph-theoretic notation. Unless stated otherwise, graphs are simple (i.e., without multiedges or self-loops) and undirected. We write V (G) and E(G) for the vertex and edge set of G, respectively, and w… view at source ↗

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

36 extracted references · 14 canonical work pages

  1. [9]

    Counting small induced subgraphs: Hardness via Fourier analysis

    Radu Curticapean and Daniel Neuen. Counting small induced subgraphs: Hardness via Fourier analysis. In Yossi Azar and Debmalya Panigrahi, editors,Proceedings of the 2025 ACM-SIAM Symposium on Discrete Algorithms, SODA 2025, New Orleans, LA, USA, January 12-15, 2025, pages 3677–3695. SIAM, 2025.doi:10.1137/1.9781611978322.122

    doi:10.1137/1.9781611978322.122 2025

  2. [6]

    Radu Curticapean, Simon Döring, Daniel Neuen, and Jiaheng Wang. Can you link up with treewidth? InOlafBeyersdorff, MichalPilipczuk, ElainePimentel, andKimThangNguyen, editors,42nd International Symposium on Theoretical Aspects of Computer Science, STACS 2025, March 4-7, 2025, Jena, Germany, volume 327 ofLIPIcs, pages 28:1–28:24. Schloss Dagstuhl - Leibniz...

    doi:10.4230/lipics.stacs.2025.28 2025

  3. [1]

    More asymmetry yields faster matrix multiplication

    Josh Alman, Ran Duan, Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu, and Renfei Zhou. More asymmetry yields faster matrix multiplication. In Yossi Azar and Debmalya Panigrahi, editors,Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2025, New Orleans, LA, USA, January 12-15, 2025, pages 2005–2039. SIAM, 2025.doi:10.113...

    doi:10.1137/1.9781611978322.63 2025

  4. [2]

    Current algorithms for detecting subgraphs of bounded treewidth are probably optimal

    Karl Bringmann and Jasper Slusallek. Current algorithms for detecting subgraphs of bounded treewidth are probably optimal. In Nikhil Bansal, Emanuela Merelli, and James Worrell, editors,48th International Colloquium on Automata, Languages, and Program- ming, ICALP 2021, July 12-16, 2021, Glasgow, Scotland (Virtual Conference), volume 198 ofLIPIcs, pages 4...

    doi:10.4230/lipics.icalp.2021.40 2021

  5. [3]

    Current Algorithms for Detecting Subgraphs of Bounded Treewidth are Probably Optimal

    Karl Bringmann and Jasper Slusallek. Current algorithms for detecting subgraphs of boundedtreewidthareprobablyoptimal.CoRR,abs/2105.05062, 2021.arXiv:2105.05062

    work page Pith review arXiv 2021

  6. [4]

    Kanj, and Ge Xia

    Jianer Chen, Xiuzhen Huang, Iyad A. Kanj, and Ge Xia. Strong computational lower bounds via parameterized complexity.J. Comput. Syst. Sci., 72(8):1346–1367, 2006.doi: 10.1016/J.JCSS.2006.04.007

    doi:10.1016/j.jcss.2006.04.007 2006

  7. [5]

    Homomorphisms are a good basis for counting small subgraphs

    Radu Curticapean, Holger Dell, and Dániel Marx. Homomorphisms are a good basis for counting small subgraphs. In Hamed Hatami, Pierre McKenzie, and Valerie King, editors, Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 210–223. ACM, 2017.doi:10.1145/ 3055399.3055502

    work page arXiv 2017

  8. [7]

    Complexity of counting subgraphs: Only the bounded- ness of the vertex-cover number counts

    Radu Curticapean and Dániel Marx. Complexity of counting subgraphs: Only the bounded- ness of the vertex-cover number counts. In55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014, pages 130–139. IEEE Computer Society, 2014.doi:10.1109/FOCS.2014.22

    doi:10.1109/focs.2014.22 2014

Show all 36 references
  1. [8]

    Counting small induced subgraphs: Hardness via fourier analysis.CoRR, abs/2407.07051, 2024.arXiv:2407.07051

    Radu Curticapean and Daniel Neuen. Counting small induced subgraphs: Hardness via fourier analysis.CoRR, abs/2407.07051, 2024.arXiv:2407.07051

    2024

  2. [10]

    Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh.Parameterized Algorithms

    Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh.Parameterized Algorithms. Springer, 2015. doi:10.1007/978-3-319-21275-3. 13

    2015 doi

  3. [11]

    Springer Berlin, 5 edition, 2017.doi:10.1007/ 978-3-662-53622-3

    Reinhard Diestel.Graph Theory. Springer Berlin, 5 edition, 2017.doi:10.1007/ 978-3-662-53622-3

    2017

  4. [12]

    Counting induced sub- graphs: An algebraic approach to #W[1]-hardness.Algorithmica, 84(2):379–404, 2022

    Julian Dörfler, Marc Roth, Johannes Schmitt, and Philip Wellnitz. Counting induced sub- graphs: An algebraic approach to #W[1]-hardness.Algorithmica, 84(2):379–404, 2022. doi:10.1007/S00453-021-00894-9

    2022 doi

  5. [13]

    Counting small induced subgraphs with edge-monotone properties

    Simon Döring, Dániel Marx, and Philip Wellnitz. Counting small induced subgraphs with edge-monotone properties. In Bojan Mohar, Igor Shinkar, and Ryan O’Donnell, editors, Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, Vancouver, BC, Canada, Jun...

    2024

  6. [14]

    From graph properties to graph param- eters: Tight bounds for counting on small subgraphs

    Simon Döring, Dániel Marx, and Philip Wellnitz. From graph properties to graph param- eters: Tight bounds for counting on small subgraphs. In Yossi Azar and Debmalya Pan- igrahi, editors,Proceedings of the 2025 ACM-SIAM Symposium on Discrete Algorithms, SODA 2025, New Orleans,...

    2025 doi

  7. [15]

    Texts in Theoretical Computer Science

    Jörg Flum and Martin Grohe.Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series. Springer, 2006.doi:10.1007/3-540-29953-X

    2006 doi

  8. [16]

    Counting small induced subgraphs with hereditary properties

    Jacob Focke and Marc Roth. Counting small induced subgraphs with hereditary properties. SIAM J. Comput., 53(2):189–220, 2024.doi:10.1137/22M1512211

    2024 doi

  9. [17]

    Parameterised and fine-grained subgraph counting, modulo 2.Algorithmica, 86(4):944–1005, 2024.doi:10.1007/S00453-023-01178-0

    Leslie Ann Goldberg and Marc Roth. Parameterised and fine-grained subgraph counting, modulo 2.Algorithmica, 86(4):944–1005, 2024.doi:10.1007/S00453-023-01178-0

    2024 doi

  10. [18]

    Whenistheevaluationofconjunctive queries tractable? In Jeffrey Scott Vitter, Paul G

    MartinGrohe, ThomasSchwentick, andLucSegoufin. Whenistheevaluationofconjunctive queries tractable? In Jeffrey Scott Vitter, Paul G. Spirakis, and Mihalis Yannakakis, editors,Proceedings on 33rd Annual ACM Symposium on Theory of Computing, July 6-8, 2001, Heraklion, Crete, Gree...

    2001

  11. [19]

    On the complexity of k-SAT.J

    Russell Impagliazzo and Ramamohan Paturi. On the complexity of k-SAT.J. Comput. Syst. Sci., 62(2):367–375, 2001.doi:10.1006/JCSS.2000.1727

    2001

  12. [20]

    Which problems have strongly exponential complexity?J

    Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity?J. Comput. Syst. Sci., 63(4):512–530, 2001.doi:10.1006/JCSS. 2001.1774

    2001

  13. [21]

    Finding a minimum circuit in a graph.SIAM J

    Alon Itai and Michael Rodeh. Finding a minimum circuit in a graph.SIAM J. Comput., 7(4):413–423, 1978.doi:10.1137/0207033

    1978 doi

  14. [22]

    The parameterised complexity of counting connected sub- graphs and graph motifs.J

    Mark Jerrum and Kitty Meeks. The parameterised complexity of counting connected sub- graphs and graph motifs.J. Comput. Syst. Sci., 81(4):702–716, 2015.doi:10.1016/J. JCSS.2014.11.015

    2015 doi

  15. [23]

    Some hard families of parameterized counting problems

    Mark Jerrum and Kitty Meeks. Some hard families of parameterized counting problems. ACM Trans. Comput. Theory, 7(3):11:1–11:18, 2015.doi:10.1145/2786017

    2015 doi

  16. [24]

    Bronstein, İsmail İlkan Ceylan, and Matthias Lanzinger

    Emily Jin, Michael M. Bronstein, İsmail İlkan Ceylan, and Matthias Lanzinger. Homomor- phism counts for graph neural networks: All about that basis. InForty-first International Conference on Machine Learning, ICML 2024, Vienna, Austria, July 21-27, 2024. Open- Review.net, 2024...

    2024

  17. [25]

    Kozlov.Combinatorial Algebraic Topology, volume 21 ofAlgorithms and compu- tation in mathematics

    Dmitry N. Kozlov.Combinatorial Algebraic Topology, volume 21 ofAlgorithms and compu- tation in mathematics. Springer, 2008.doi:10.1007/978-3-540-71962-5. 14

    2008 doi

  18. [26]

    Best, and Peter van Emde Boas

    Hendrik Lenstra, Marc R. Best, and Peter van Emde Boas. A sharpened version of the Aanderaa-Rosenberg conjecture.Report 30/74, Mathematisch Centrum Amsterdam (1974), pages 1–20, 1974. URL:https://hdl.handle.net/1887/3792

    1974

  19. [27]

    Network motifs: Simple building blocks of complex networks.Science, 298(5594):824– 827, 2002.doi:10.1126/science.298.5594.824

    RonMilo, ShaiS.Shen-Orr, ShalevItzkovitz, NadavKashtan, DmitriB.Chklovskii, andUri Alon. Network motifs: Simple building blocks of complex networks.Science, 298(5594):824– 827, 2002.doi:10.1126/science.298.5594.824

    2002 doi

  20. [28]

    Peter M. Neumann. Transitive permutation groups of prime degree. InProceedings of the Second International Conference on the Theory of Groups, volume Vol. 372 ofLec- ture Notes in Math., pages 520–535. Springer Berlin Heidelberg, 1974.doi:10.1007/ 978-3-662-21571-5\_55

    1974

  21. [29]

    On the complexity of the subgraph problem.Com- ment

    Jaroslav Nešetřil and Svatopluk Poljak. On the complexity of the subgraph problem.Com- ment. Math. Univ. Carolin., 26(2):415–419, 1985. URL:http://dml.cz/dmlcz/106381

    1985

  22. [30]

    Rosenberg

    Arnold L. Rosenberg. On the time required to recognize properties of graphs: a problem. SIGACT News, 5(4):15–16, 1973.doi:10.1145/1008299.1008302

    1973

  23. [31]

    Independent sets in regular graphs.Israel J

    Moshe Rosenfeld. Independent sets in regular graphs.Israel J. Math., 2:262–272, 1964. doi:10.1007/BF02759743

    1964 doi

  24. [32]

    Counting induced subgraphs: A topological approach to #W[1]-hardness.Algorithmica, 82(8):2267–2291, 2020.doi:10.1007/ S00453-020-00676-9

    Marc Roth and Johannes Schmitt. Counting induced subgraphs: A topological approach to #W[1]-hardness.Algorithmica, 82(8):2267–2291, 2020.doi:10.1007/ S00453-020-00676-9

    2020

  25. [33]

    Detecting and counting small sub- graphs, and evaluating a parameterized tutte polynomial: Lower bounds via toroidal grids and cayley graph expanders

    Marc Roth, Johannes Schmitt, and Philip Wellnitz. Detecting and counting small sub- graphs, and evaluating a parameterized tutte polynomial: Lower bounds via toroidal grids and cayley graph expanders. In Nikhil Bansal, Emanuela Merelli, and James Wor- rell, editors,48th Intern...

    2021

  26. [34]

    Counting small induced subgraphs sat- isfying monotone properties.SIAM J

    Marc Roth, Johannes Schmitt, and Philip Wellnitz. Counting small induced subgraphs sat- isfying monotone properties.SIAM J. Comput., 53(6):FOCS20–139––FOCS20–174, 2024. doi:10.1137/20M1365624

    2024 doi

  27. [35]

    StreaM - A stream- based algorithm for counting motifs in dynamic graphs

    Benjamin Schiller, Sven Jager, Kay Hamacher, and Thorsten Strufe. StreaM - A stream- based algorithm for counting motifs in dynamic graphs. In Adrian-Horia Dediu, Fran- cisco Hernández Quiroz, Carlos Martín-Vide, and David A. Rosenblueth, editors,Algo- rithms for Computational...

    2015 doi

  28. [36]

    Frequency concepts and pattern detection for the analysis of motifs in networks.Trans

    Falk Schreiber and Henning Schwöbbermeyer. Frequency concepts and pattern detection for the analysis of motifs in networks.Trans. Comp. Sys. Biology, 3:89–104, 2005.doi: 10.1007/11599128\_7. 15

    2005 doi

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.