Pith. sign in

REVIEW 4 major objections 4 minor 2 cited by

The Parametrised Complexity of Counting Small Sub-Hypergraphs

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

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

Pith's one-line read Counting small sub-hypergraphs is tractable exactly when a fractional cover number is bounded.

desk verdict Main dichotomies for sub-hypergraph counting are real and the core proofs hold up; two small bugs in secondary statements are easy to patch. read the letter →

arxiv 2506.14081 v3 pith:VTRFISH2 submitted 2025-06-17 cs.CC cs.DS

Marco Bressan , Julian Brinkmann , Holger Dell , Marc Roth , Philip Wellnitz This is my paper · ORCID
classification cs.CCcs.DS MSC 68Q2705C6505C70
keywords hypergraphcountingfractionaledgecoverparameterizedcomplexityfixed-parametertractabilityExponentialTimeHypothesishomomorphismbasisadaptivewidthinducedsubhypergraph
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

This paper gives the first complete complexity classification for the parameterized problem of counting how many times a small hypergraph $H$ appears inside a large hypergraph $G$, in both the ordinary and the induced sense. The dividing line is a single rational parameter: ordinary copies are counted in fixed-parameter time exactly when the fractional co-independent edge-cover number $\sigma^*(\mathcal{H})$ is bounded over the family $\mathcal{H}$, and induced copies exactly when the fractional edge-cover number $\rho^*(\mathcal{H})$ is bounded. Both claims are conditional on the Exponential Time Hypothesis, and both subsume the previously known graph dichotomies as special cases. The proof works by writing copy counts as linear combinations of hypergraph homomorphism counts and then reducing the problem to known tractability and hardness results for homomorphism counting. The paper also shows that the easy cases are not trivial: some easy #Sub families are #P-hard, and the easy #IndSub families run in quasi-polynomial time unless Graph Isomorphism lies in P.

What carries the argument

The load-bearing object is the hypergraph homomorphism basis: every sub-hypergraph count and every induced sub-hypergraph count is expressed as a finite linear combination of homomorphism counts $\#\mathrm{Hom}(F \to G)$, summed over quotients of $H$ and, for induced copies, over quotients of its edge-super-hypergraphs. Because the hypergraph tensor product multiplies homomorphism counts, $\#\mathrm{Hom}(F \to G \otimes H) = \#\mathrm{Hom}(F \to G) \cdot \#\mathrm{Hom}(F \to H)$, the interpolation method of Dedekind can isolate each summand, making the counting problem exactly as hard as the hardest homomorphism in the support. The tractable direction feeds on a known FPT algorithm for $\#\mathrm{Hom}$ on classes of bounded fractional hypertree width; the hardness direction feeds on known ETH-based hardness for classes of unbounded adaptive width. The bridge between the new cover parameters and width is the inequality $\alpha(H) \ge \frac{1}{2} + \frac{\alpha^*(H)}{4\,\mathrm{aw}(H)}$, together with a Ramsey argument that turns a large independent set inside a minimal co-independent set into a quotient graph of large treewidth.

What would settle it

To refute the dichotomy, exhibit a recursively enumerable family $\mathcal{H}$ with $\sigma^*(\mathcal{H})=\infty$ for which $\#\mathrm{Sub}(\mathcal{H})$ is still fixed-parameter tractable, or a family with $\rho^*(\mathcal{H})=\infty$ for which $\#\mathrm{IndSub}(\mathcal{H})$ is still FPT; under ETH the theorems forbid both. A concrete spot to probe is the construction of Lemma 5.8: run it on the family of 4-uniform sunflowers with core size one and check whether the quotients it produces really contain graphs of unbounded treewidth — if the Ramsey step fails to produce such a quotient, the lower-bound chain breaks.

Watch

Extended reading notes

Core claim

The central claim is that two newly isolated invariants govern the entire complexity map. For every recursively enumerable family $\mathcal{H}$ of hypergraphs, assuming ETH, $\#\mathrm{Sub}(\mathcal{H})$, parameterized by $|H|$, is fixed-parameter tractable if and only if $\sigma^*(\mathcal{H}) < \infty$, and $\#\mathrm{IndSub}(\mathcal{H})$ is fixed-parameter tractable if and only if $\rho^*(\mathcal{H}) < \infty$. These are exact dichotomies, not merely upper or lower bounds. Along the way the paper proves that the tractable side is algorithmically delicate: some families with bounded $\sigma^*$ are #P-hard for #Sub, and some with bounded $\rho^*$ require quasi-polynomial time for #IndSub unless Graph Isomorphism is in P. Finally, the paper studies a natural trimmed notion of sub-hypergraph and shows that the homomorphism-basis method, which carries the two dichotomies, provably cannot be adapted to that setting.

Load-bearing premise

The hardness direction rests on an externally supplied inequality claiming that every hypergraph has an independent set at least one half plus a quarter of its fractional independence number divided by its adaptive width; if that inequality fails for any hypergraph family used in the proof, the lower-bound arguments collapse.

Editorial extensions

If this is right

  • For any recursively enumerable family $\mathcal{H}$, $\#\mathrm{Sub}(\mathcal{H})$ is fixed-parameter tractable when $\sigma^*(\mathcal{H}) < \infty$, yet some such families remain #P-hard, so fixed-parameter tractability does not collapse to polynomial time in the hypergraph setting.
  • For any recursively enumerable family $\mathcal{H}$, $\#\mathrm{IndSub}(\mathcal{H})$ is fixed-parameter tractable when $\rho^*(\mathcal{H}) < \infty$, solvable in quasi-polynomial time; a polynomial-time algorithm for every such family would place Graph Isomorphism in P.
  • The classical graph dichotomies are special cases: for graphs, $\sigma^*$ behaves asymptotically like the vertex-cover number and $\rho^*$ like the vertex count, so the two theorems recover the known classifications for subgraph and induced subgraph counting.
  • Unbounded $\sigma^*$ or $\rho^*$ makes the corresponding problem not fixed-parameter tractable unless ETH fails, yielding a hard 'if and only if' statement at the level of parameterized complexity.
  • For trimmed sub-hypergraphs, the usual complexity-monotonicity machinery breaks down: an easy induced trimmed counting problem can have a hard trimmed homomorphism in its expansion, and no fixed-parameter-associative product can serve as the basis for interpolation.

Reading between the lines

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

  • Because the dichotomy is decided by two static rational parameters on the pattern hypergraph, a practical system could compute $\sigma^*$ and $\rho^*$ on query patterns to predict whether a hypergraph counting workload is likely to admit fixed-parameter algorithms.
  • The constant $1/4$ in the integrality-gap inequality is the quantitative hinge of the lower-bound construction; improving it would sharpen the dependence of the hardness results on the pattern size, and a counterexample to it would reopen the lower-bound proofs.
  • The failure of complexity monotonicity for trimmed sub-hypergraphs hints that other hypergraph deletion semantics, such as vertex pruning that keeps residual edges, may each require their own algebraic basis and cannot borrow the homomorphism-basis framework.
  • The dichotomies are asymptotic in the pattern size, so they leave open fine-grained questions about the smallest exponent of the host size for specific families; the quotient construction used in the lower-bound proof could serve as a template for building candidate hard families with controlled pattern rarity.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

4 major / 4 minor

Summary. The paper studies the parameterized complexity of counting small sub-hypergraphs and induced sub-hypergraphs, parameterized by the number of vertices of the pattern. It introduces a new parameter, the fractional co-independent edge-cover number σ*, and proves two dichotomies assuming ETH: #Sub(H) is FPT iff σ* is bounded on H, and #IndSub(H) is FPT iff the fractional edge-cover number ρ* is bounded on H. The technical machinery includes a hypergraph version of the homomorphism basis, a suitable tensor product for Dedekind interpolation, and an analysis of adaptive width of quotients and edge-superhypergraphs. The paper also shows that the FPT cases can be genuinely hard: #Sub can be #P-hard despite being FPT, and #IndSub admits only quasi-polynomial time unless Graph Isomorphism is in P. A final section studies trimmed sub-hypergraphs and shows that the natural trimmed homomorphism basis does not satisfy complexity monotonicity.

Significance. If the main theorems are correct, this is a substantial contribution: it provides the first complete parameterized complexity dichotomies for counting small sub-hypergraphs of unbounded rank, subsuming the known graph classifications as special cases. The lifting of the homomorphism-basis and complexity-monotonicity framework from graphs to unbounded-rank hypergraphs is technically nontrivial and likely to be reused. The paper is also careful to expose the source of hardness: the FPT cases are shown to be nonetheless #P-hard or quasi-polynomial-time, which is an honest and informative separation from the graph setting. The proof structure is largely transparent, and the main reductions are spelled out in detail; the main theorems rest on established external results on hypergraph homomorphism counting and on an integrality-gap lemma of Bressan, Lanzinger, and Roth.

major comments (4)
  1. [§5.1, Eq. (18)] The displayed application of Lemma 3.11 in Eq. (18) writes α(H⟨X⟩) ≥ 1/2 + α*(H⟨X⟩)/aw(H⟨X⟩), omitting the factor 4 that Lemma 3.11 places in the denominator. This inequality is the mechanism by which unbounded σ*(H) is converted into an arbitrarily large independent set, so the lower-bound direction of Main Theorem 1, and the analogous step in Lemma 5.17 for Main Theorem 2, depends on the exact statement. Please correct the constant and confirm that Lemma 3.11 applies at the stated level of generality, in particular to hypergraphs with isolated vertices under Remark 3.5 and to trimmed induced subhypergraphs H⟨X⟩.
  2. [§5.1, Claim 5.9] The hypergraph H⟨R∪I⟩ may contain singleton edges {v}, arising from original hyperedges whose intersection with R∪I is a single vertex. Such a hypergraph is not a bipartite graph in the usual sense, and a matching consisting of singleton edges would not yield the large-treewidth quotient needed in Claim 5.10. The proof should apply König's theorem to the bipartite graph formed by the size-2 edges between R and I, noting that singleton edges play no role in the co-independence argument; as written, the claim and its subsequent use of Lemma 5.7 are not fully justified.
  3. [§5.2, Lemma 5.17] The statement K_{α(H)} ∈ 𝒯(𝒮(H)) is not literally correct as written: if vertices of the independent set I lie in some edge of H, then H′⟨I⟩ also contains singleton edges, so the induced trimmed subhypergraph is not isomorphic to the 2-uniform clique K_{α(H)}. Please either state explicitly that the term 'graph' in Lemma 4.18 means a rank-at-most-2 hypergraph in which singleton edges are allowed, or modify the construction so that a genuine graph of treewidth α(H) appears in 𝒯(𝒮(H)). This is a load-bearing step in the bounded-adaptive-width case of Main Theorem 2.
  4. [§6.1, Lemma 6.8] The formula ∑_t C(n_t,k) overcounts #IndTrimSub(B_k→G) when G has isolated vertices: for t(v)=∅, the trimmed induced subhypergraph G⟨X⟩ has no edges and is not isomorphic to B_k for any k≥1, yet the sum contributes C(n_∅,k). This makes the proof of Theorem 6.5(2) incorrect as stated. The argument is repairable by summing only over non-empty types, so the polynomial-time claim survives, but the lemma as written needs correction.
minor comments (4)
  1. [Theorem 5.19] The notation for the quasi-polynomial running time is inconsistent: the statement says (ln ∥H∥)^{O(1)} while the proof uses (log ∥H∥)^{O(1)}; please use one convention throughout.
  2. [Lemma 5.8] In the first case of the proof, the sentence 'The claim then follows by Lemma 3.9' should cite Marx's hardness theorem for unbounded adaptive width rather than Lemma 3.9, which only records inequalities between width measures.
  3. [Theorem 5.20] For patterns with |F|=2, the added edge V(F) coincides with a possible graph edge of size 2, so the claimed bijection between induced copies and graph isomorphism needs a short separate argument for small patterns.
  4. [Throughout] There are several minor typographical issues, including 'Isomoprhism' in the statement of Theorem 5.20 and a reference to 'Sub(H→G)' in Section 2.5 where '#IndSub(H→G)' is meant.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the dichotomies are derived from external published results, and the author self-citations are independent evidence rather than assumed conclusions.

full rationale

The derivation chain is self-contained against external results. The paper casts #Sub and #IndSub as hypergraph motif parameters, lifts complexity monotonicity from Curticapean--Dell--Marx via Dedekind interpolation, and then reduces the tractability question to known structural results about fractional hypertree width and adaptive width (Grohe--Marx, Marx). The upper bounds follow from fhw bounds on quotients/super-hypergraphs; the lower bounds use the BLR23 integrality gap lemma (Lemma 3.11) to convert unbounded sigma* or rho* into large independent sets and then into large-treewidth graph quotients. The BLR23 results are published STOC 2023 theorems with stated general hypotheses that do not include the hypergraph counting classification, so citing them is independent support under the review rules even though two present authors are co-authors. The parameters sigma* and rho* are mathematical definitions used as tractability criteria, not quantities fitted to data and then renamed as predictions. No equation in the paper defines sigma* in terms of #Sub , nor does the paper fit a parameter to a subset of the counting data. The skeptic's observation about Equation (18) omitting the factor 4 from Lemma 3.11 is a potential correctness or typographical concern about the application of an external lemma, not a circularity: it does not make the theorem equivalent to its input. Therefore no circular step is present, and the appropriate score is 0.

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

The paper introduces a new width parameter σ* but fits no numerical constants to data; all results are mathematical theorems. The main external assumptions are the listed complexity conjectures (ETH, SETH, FPT≠#W[2]) and published theorems used as black boxes. No invented entities are postulated.

assumptions (10)
  • domain assumption ETH (Exponential Time Hypothesis): 3-SAT cannot be solved in time exp(o(n)).
    Used to rule out FPT algorithms for the hard cases in Main Theorems 1 and 2; a standard unproven complexity conjecture.
  • standard math Integrality gap lemma (BLR23, Theorem 17): α(H) ≥ 1/2 + α*(H)/(4·aw(H)) for every hypergraph H.
    Black-box theorem used in Lemmas 5.8 and 5.17 to convert large fractional independence into large independent sets when adaptive width is bounded.
  • standard math Grohe and Marx (GM14): #Hom is FPT on hypergraph families of bounded fractional hypertree width.
    Provides the upper bounds for #Sub and #IndSub via the fractional hypertree width bounds on quotient families.
  • standard math Marx (Mar13): #Hom is not FPT on hypergraph families of unbounded adaptive width unless ETH fails.
    Provides the hardness of #Hom on quotient families in the lower-bound proofs of both main theorems.
  • standard math König's theorem for bipartite graphs.
    Used in Claim 5.9 to obtain a small vertex cover from a small matching in the bipartite graph H⟨R∪I⟩.
  • standard math Ramsey-type lemma (CM14, Lemma 5.2): a large matching implies an induced clique, biclique, or matching.
    Used in Claim 5.10 to extract a large-treewidth graph from a large matching in the quotient construction.
  • domain assumption SETH (Strong Exponential Time Hypothesis).
    Used in Theorem 6.5 to give a fine-grained lower bound for #TrimHom(B).
  • domain assumption FPT ≠ #W[2].
    Used in Theorem 6.10 to rule out an associative trimmed-homomorphism product.
  • standard math LP duality: α*(H) = ρ*(H) for hypergraphs.
    Used to equate fractional independence and edge-cover numbers in Lemmas 5.8 and 5.17.
  • standard math Integrality gap for fractional edge covers: a fractional edge cover of weight r implies an integral cover of size O(r log n).
    Used in Theorem 5.19 to enumerate a small set of edges covering all vertices in the quasi-polynomial algorithm.

how reviews work

0 comments
Cite this review

Pith. "Pith review of The Parametrised Complexity of Counting Small Sub-Hypergraphs." pith.science (2026). https://pith.science/paper/VTRFISH2

@misc{pith2026250614081,
  author       = {Pith},
  title        = {Pith review of: The Parametrised Complexity of Counting Small Sub-Hypergraphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/VTRFISH2}},
  note         = {Machine review of arXiv:2506.14081}
}
abstract

Subgraph counting is a fundamental and well-studied problem whose computational complexity is well understood. Quite surprisingly, the hypergraph version of subgraph counting has been almost ignored. In this work, we address this gap by investigating the most basic sub-hypergraph counting problem: given a (small) hypergraph $H$ and a (large) hypergraph $G$, compute the number of sub-hypergraphs of $G$ isomorphic to $H$. Formally, for a family $\mathcal{H}$ of hypergraphs, let #Sub($\mathcal{H}$) be the restriction of the problem to $H \in \mathcal{H}$; the induced variant #IndSub($\mathcal{H}$) is defined analogously. Our main contribution is a complete classification of the complexity of these problems. Assuming the Exponential Time Hypothesis, we prove that #Sub($\mathcal{H}$) is fixed-parameter tractable if and only if $\mathcal{H}$ has bounded fractional co-independent edge-cover number, a novel graph parameter we introduce. Moreover, #IndSub($\mathcal{H}$) is fixed-parameter tractable if and only if $\mathcal{H}$ has bounded fractional edge-cover number. Both results subsume pre-existing results for graphs as special cases. We also show that the fixed-parameter tractable cases of #Sub($\mathcal{H}$) and #IndSub($\mathcal{H}$) are unlikely to be in polynomial time, unless respectively #P = P and Graph Isomorphism $\in$ P. This shows a separation with the special case of graphs, where the fixed-parameter tractable cases are known to actually be in polynomial time.

Figures

Figures reproduced from arXiv: 2506.14081 by the authors.

Figure 1
Figure 1. Two families of sunflowers, that is, hypergraphs whose edges pairwise intersect in the same set, called core. The example can be easily extended to unbounded rank by taking the families of ℓ-uniform sunflowers with cores of sizes 1 and ℓ − 1, respectively. a A visualization of the hypergraph family from [GM14, Example 4.2]: for an integer 𝑛 > 0, we consider the hyper￾graph with a vertex for each size-𝑛-subset of {1,… view at source ↗
Figure 2
Figure 2. Two families of hypergraphs that fall into either of the two cases of Main Theorem 2. Consult the technical overview (Section 2) for a detailed explanation of the notation2 of Main Theo￾rems 1 and 2, as well as an intuitive overview of the corresponding proofs. Also consult [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗
Figure 3
Figure 3. b (in this case one ham), we obtain a sub￾hypergraph of Figure 3a. d The induced trimmed sub-hypergraph of the pizza slice formed by the black vertices of Figure 3a, parts of the crust and the cheese of the pizza are trimmed and survive [PITH_FULL_IMAGE:figures/full_fig_p006_3.png] view at source ↗

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. The Fine-Grained Complexity of Counting Hypergraph Motifs

    cs.CC 2026-07 accept novelty 7.0 of 10

    Hypergraph motif counting is always FPT-near-quadratic in rank, and FPT-near-linear exactly for the degenerate Venn diagrams, assuming Triangle and Hyperclique Hypotheses.

  2. Counting Patterns in Degenerate Graphs in Constant Space

    cs.DS 2025-11 reject novelty 6.0 of 10

    The paper claims constant-space, DAG-treedepth-based pattern counting in degenerate graphs, but the flagship algorithm's time bound is contradicted by a star-pattern counterexample.

Reference graph

Works this paper leans on

47 extracted references · 13 canonical work pages · cited by 2 Pith papers

  1. [1]

    Agarwal, Jongwoo Lim , L

    S. Agarwal, Jongwoo Lim , L. Zelnik-Manor, P. Perona, D. Kriegman, and S. Belongie. Beyond Pairwise Clustering . In 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition ( CVPR '05) , volume 2, pages 838--845, 2005. https://doi.org/10.1109/CVPR.2005.89 doi:10.1109/CVPR.2005.89

    work page doi:10.1109/cvpr.2005.89 2005

  2. [2]

    Clustering in graphs and hypergraphs with categorical edge labels

    Ilya Amburg, Nate Veldt, and Austin Benson. Clustering in graphs and hypergraphs with categorical edge labels. In Proceedings of The Web Conference 2020 , pages 706--717, April 2020. https://doi.org/10.1145/3366423.3380152 doi:10.1145/3366423.3380152

    arXiv 2020

  3. [3]

    Benson, Rediet Abebe, Michael T

    Austin R. Benson, Rediet Abebe, Michael T. Schaub, Ali Jadbabaie, and Jon Kleinberg. Simplicial closure and higher-order link prediction. Proceedings of the National Academy of Sciences , 115(48), November 2018. https://doi.org/10.1073/pnas.1800683115 doi:10.1073/pnas.1800683115

    doi:10.1073/pnas.1800683115 2018

  4. [4]

    Bera, Lior Gishboliner, Yevgeny Levanzov, C

    Suman K. Bera, Lior Gishboliner, Yevgeny Levanzov, C. Seshadhri, and Asaf Shapira. Counting subgraphs in degenerate graphs. Journal of the ACM , 69(3):23:1--23:21, 2022. https://doi.org/10.1145/3520240 doi:10.1145/3520240

    work page doi:10.1145/3520240 2022

  5. [5]

    Counting Subgraphs in Somewhere Dense Graphs

    Marco Bressan, Leslie Ann Goldberg, Kitty Meeks, and Marc Roth. Counting Subgraphs in Somewhere Dense Graphs . SIAM Journal on Computing , 53(5):1409--1438, October 2024. https://doi.org/10.1137/22M1535668 doi:10.1137/22M1535668

    work page doi:10.1137/22m1535668 2024

  6. [6]

    The complexity of pattern counting in directed graphs, parameterised by the outdegree

    Marco Bressan, Matthias Lanzinger, and Marc Roth. The complexity of pattern counting in directed graphs, parameterised by the outdegree. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, Orlando, FL, USA, June 20-23, 2023 , pages 542--552, 2023. Full version available at . https://doi.org/10.1145/3564246.3585204 doi:10.114...

    arXiv 2023

  7. [7]

    Exact and Approximate Pattern Counting in Degenerate Graphs: New Algorithms, Hardness Results, and Complexity Dichotomies

    Marco Bressan and Marc Roth. Exact and approximate pattern counting in degenerate graphs: New algorithms, hardness results, and complexity dichotomies. CoRR , abs/2103.05588, 2021. https://arxiv.org/abs/2103.05588 arXiv:2103.05588 , https://doi.org/10.48550/arxiv.2103.05588 doi:10.48550/arxiv.2103.05588

    work page Pith review arXiv doi:10.48550/arxiv.2103.05588 2021

  8. [8]

    Homomorphisms are a good basis for counting small subgraphs

    Radu Curticapean, Holger Dell, and D \' a niel Marx. Homomorphisms are a good basis for counting small subgraphs. In Proc.\ of ACM STOC , pages 210--223, 2017. https://doi.org/10.1145/3055399.3055502 doi:10.1145/3055399.3055502

    arXiv 2017

Show all 47 references
  1. [9]

    Fomin, Lukasz Kowalik, Daniel Lokshtanov, D \' a niel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh

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

    2015 doi

  2. [10]

    The C omplexity of S atisfiability of S mall D epth C ircuits

    Chris Calabro, Russell Impagliazzo, and Ramamohan Paturi. The C omplexity of S atisfiability of S mall D epth C ircuits. In Parameterized and Exact Computation, 4th International Workshop, IWPEC 2009, Copenhagen, Denmark, September 10-11, 2009, Revised Selected Papers , pages ...

    2009 doi

  3. [11]

    Complexity of C ounting S ubgraphs: O nly the B oundedness of the V ertex- C over N umber C ounts

    Radu Curticapean and D \' a niel Marx. Complexity of C ounting S ubgraphs: O nly the B oundedness of the V ertex- C over N umber C ounts. In Proc.\ of IEEE FOCS , pages 130--139, 2014. Full version available at . https://doi.org/10.1109/FOCS.2014.22 doi:10.1109/FOCS.2014.22

    2014 doi

  4. [12]

    A T richotomy in the C omplexity of C ounting A nswers to C onjunctive Q ueries

    Hubie Chen and Stefan Mengel. A T richotomy in the C omplexity of C ounting A nswers to C onjunctive Q ueries. In Proc.\ of ICDT , pages 110--126, 2015. https://doi.org/10.4230/LIPIcs.ICDT.2015.110 doi:10.4230/LIPIcs.ICDT.2015.110

    2015 doi

  5. [13]

    Counting A nswers to E xistential P ositive Q ueries: A C omplexity C lassification

    Hubie Chen and Stefan Mengel. Counting A nswers to E xistential P ositive Q ueries: A C omplexity C lassification. In Proc.\ of ACM PODS , pages 315--326, 2016. https://doi.org/10.1145/2902251.2902279 doi:10.1145/2902251.2902279

    2016

  6. [14]

    Counting small induced subgraphs: Hardness via fourier analysis

    Radu Curticapean and Daniel Neuen. Counting small induced subgraphs: Hardness via fourier analysis. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2025, New Orleans, LA, USA, January 12-15, 2025 , pages 3677--3695, 2025. https://doi.org/10.11...

    2025 doi

  7. [15]

    Understanding the C omplexity of I nduced S ubgraph I somorphisms

    Yijia Chen, Marc Thurley, and Mark Weyer. Understanding the C omplexity of I nduced S ubgraph I somorphisms. In Proc.\ of ICALP , pages 587--596, 2008. https://doi.org/10.1007/978-3-540-70575-8_48 doi:10.1007/978-3-540-70575-8_48

    2008 doi

  8. [16]

    Downey and Michael R

    Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity . Texts in Computer Science. 2013. https://doi.org/10.1007/978-1-4471-5559-1 doi:10.1007/978-1-4471-5559-1

    2013 doi

  9. [17]

    The complexity of counting homomorphisms seen from the other side

    V \' ctor Dalmau and Peter Jonsson. The complexity of counting homomorphisms seen from the other side. Theoretical Computer Science , 329(1-3):315--323, 2004. https://doi.org/10.1016/j.tcs.2004.08.008 doi:10.1016/j.tcs.2004.08.008

    2004 doi

  10. [18]

    Structural T ractability of C ounting of S olutions to C onjunctive Q ueries

    Arnaud Durand and Stefan Mengel. Structural T ractability of C ounting of S olutions to C onjunctive Q ueries. Theory Comput.\ Syst. , 57(4):1202--1249, 2015. https://doi.org/10.1007/s00224-014-9543-y doi:10.1007/s00224-014-9543-y

    2015 doi

  11. [19]

    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 Proceedings of the 56th Annual ACM Symposium on Theory of Computing , pages 1517--1525, June 2024. https://doi.org/10.1145/3618260.3649644 doi:10.1145/3618260.3649644

    2024

  12. [20]

    From graph properties to graph parameters: Tight bounds for counting on small subgraphs

    Simon D \" o ring, D \' a niel Marx, and Philip Wellnitz. From graph properties to graph parameters: Tight bounds for counting on small subgraphs. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2025, New Orleans, LA, USA, January 12-15, 2025 ...

    2025 doi

  13. [21]

    Counting Answers to Existential Questions

    Holger Dell, Marc Roth, and Philip Wellnitz. Counting Answers to Existential Questions . In Proc.\ of ICALP , volume 132 of Leibniz International Proceedings in Informatics (LIPIcs) , pages 113:1--113:15, 2019. https://doi.org/10.4230/LIPIcs.ICALP.2019.113 doi:10.4230/LIPIcs.I...

    2019 doi

  14. [22]

    Fixed- P arameter T ractability, D efinability, and M odel- C hecking

    J \" o rg Flum and Martin Grohe. Fixed- P arameter T ractability, D efinability, and M odel- C hecking. SIAM Journal on Computing , 31(1):113--145, 2001. https://doi.org/10.1137/S0097539799360768 doi:10.1137/S0097539799360768

    2001 doi

  15. [23]

    Parameterized Complexity Theory

    J \" o rg Flum and Martin Grohe. Parameterized Complexity Theory . Texts in Theoretical Computer Science. An EATCS Series. 2006. https://doi.org/10.1007/3-540-29953-X doi:10.1007/3-540-29953-X

    2006 doi

  16. [24]

    Counting small induced subgraphs with hereditary properties

    Jacob Focke and Marc Roth. Counting small induced subgraphs with hereditary properties. In STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 - 24, 2022 , pages 1543--1551, 2022. https://doi.org/10.1145/3519935.3520008 doi:10.1145/3519935.3520008

    2022

  17. [25]

    Hypertree decompositions and tractable queries

    Georg Gottlob, Nicola Leone, and Francesco Scarcello. Hypertree decompositions and tractable queries. Journal of Computer and System Sciences , 64(3):579--627, 2002. https://doi.org/10.1006/JCSS.2001.1809 doi:10.1006/JCSS.2001.1809

    2002

  18. [26]

    On tree width, bramble size, and expansion

    Martin Grohe and Dániel Marx. On tree width, bramble size, and expansion. J.\ Comb.\ Theory, Ser.\ B , 99(1):218--228, January 2009. https://doi.org/10.1016/j.jctb.2008.06.004 doi:10.1016/j.jctb.2008.06.004

    2009 doi

  19. [27]

    Constraint solving via fractional edge covers

    Martin Grohe and D \' a niel Marx. Constraint solving via fractional edge covers. ACM Transactions on Algorithms , 11(1):4:1--4:20, 2014. https://doi.org/10.1145/2636918 doi:10.1145/2636918

    2014 doi

  20. [28]

    AHP : Learning to Negative Sample for Hyperedge Prediction , April 2022

    Hyunjin Hwang, Seungwoo Lee, Chanyoung Park, and Kijung Shin. AHP : Learning to Negative Sample for Hyperedge Prediction , April 2022. https://arxiv.org/abs/2204.06353 arXiv:2204.06353 , https://doi.org/10.48550/arXiv.2204.06353 doi:10.48550/arXiv.2204.06353

    2022 doi arXiv

  21. [29]

    Yuchi Huang, Qingshan Liu, Shaoting Zhang, and Dimitris N. Metaxas. Image retrieval via probabilistic hypergraph ranking. In 2010 IEEE Computer Society Conference on Computer Vision and Pattern Recognition , pages 3376--3383, June 2010. https://doi.org/10.1109/CVPR.2010.554001...

    2010

  22. [30]

    Learning on Weighted Hypergraphs to Integrate Protein Interactions and Gene Expressions for Cancer Outcome Prediction

    TaeHyun Hwang, Ze Tian, Rui Kuangy, and Jean-Pierre Kocher. Learning on Weighted Hypergraphs to Integrate Protein Interactions and Gene Expressions for Cancer Outcome Prediction . In 2008 Eighth IEEE International Conference on Data Mining , pages 293--302, December 2008. http...

    2008 doi

  23. [31]

    On the C omplexity of k- S A T

    Russell Impagliazzo and Ramamohan Paturi. On the C omplexity of k- S A T . Journal of Computer and System Sciences , 62(2):367--375, 2001. https://doi.org/10.1006/jcss.2000.1727 doi:10.1006/jcss.2000.1727

    2001

  24. [32]

    Which P roblems H ave S trongly E xponential C omplexity? Journal of Computer and System Sciences , 63(4):512--530, 2001

    Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which P roblems H ave S trongly E xponential C omplexity? Journal of Computer and System Sciences , 63(4):512--530, 2001. https://doi.org/10.1006/jcss.2001.1774 doi:10.1006/jcss.2001.1774

    2001

  25. [33]

    Adaptive Hypergraph Learning and its Application in Image Classification

    Jun Yu , Dacheng Tao , and Meng Wang . Adaptive Hypergraph Learning and its Application in Image Classification . IEEE Transactions on Image Processing , 21(7):3262--3272, July 2012. https://doi.org/10.1109/TIP.2012.2190083 doi:10.1109/TIP.2012.2190083

    2012

  26. [34]

    The parameterised complexity of counting connected subgraphs and graph motifs

    Mark Jerrum and Kitty Meeks. The parameterised complexity of counting connected subgraphs and graph motifs. Journal of Computer and System Sciences , 81(4):702--716, 2015. https://doi.org/10.1016/j.jcss.2014.11.015 doi:10.1016/j.jcss.2014.11.015

    2015 doi

  27. [35]

    Lov \'a sz

    L. Lov \'a sz. Operations with structures. Acta Mathematica Academiae Scientiarum Hungarica , 18(3):321--328, 1967. https://doi.org/10.1007/BF02280291 doi:10.1007/BF02280291

    1967 doi

  28. [36]

    Large Networks and Graph Limits , volume 60 of Colloquium Publications

    L \' a szl \' o Lov \' a sz. Large Networks and Graph Limits , volume 60 of Colloquium Publications . 2012

    2012

  29. [37]

    Link prediction in social networks based on hypergraph

    Dong Li, Zhiming Xu, Sheng Li, and Xin Sun. Link prediction in social networks based on hypergraph. In Proceedings of the 22nd International Conference on World Wide Web , pages 41--42, May 2013. https://doi.org/10.1145/2487788.2487802 doi:10.1145/2487788.2487802

    2013

  30. [38]

    Can Y ou B eat T reewidth? Theory of Computing

    D \' a niel Marx. Can Y ou B eat T reewidth? Theory of Computing. An Open Access Journal , 6(1):85--112, 2010. https://doi.org/10.4086/toc.2010.v006a005 doi:10.4086/toc.2010.v006a005

    2010 doi

  31. [39]

    Tractable Hypergraph Properties for Constraint Satisfaction and Conjunctive Queries

    D \' a niel Marx. Tractable Hypergraph Properties for Constraint Satisfaction and Conjunctive Queries . Journal of the ACM , 60(6):42:1--42:51, 2013. https://doi.org/10.1145/2535926 doi:10.1145/2535926

    2013 doi

  32. [40]

    A short note on the counting complexity of conjunctive queries

    Stefan Mengel. A short note on the counting complexity of conjunctive queries. CoRR , abs/2112.01108, 2021. https://arxiv.org/abs/2112.01108 arXiv:2112.01108 , https://doi.org/10.48550/arxiv.2112.01108 doi:10.48550/arxiv.2112.01108

    2021 doi arXiv

  33. [41]

    Hypergraph isomorphism for groups with restricted composition factors

    Daniel Neuen. Hypergraph isomorphism for groups with restricted composition factors. ACM Transactions on Algorithms , 18(3):27:1--27:50, 2022. https://doi.org/10.1145/3527667 doi:10.1145/3527667

    2022 doi

  34. [42]

    Counting R estricted H omomorphisms via M \" o bius I nversion over M atroid L attices

    Marc Roth. Counting R estricted H omomorphisms via M \" o bius I nversion over M atroid L attices. In 25th Annual European Symposium on Algorithms, ESA 2017, September 4-6, 2017, Vienna, Austria , pages 63:1--63:14, 2017. https://doi.org/10.4230/LIPIcs.ESA.2017.63 doi:10.4230/...

    2017 doi

  35. [43]

    Counting induced subgraphs: A topological approach to \# w[1]-hardness

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

    2020 doi

  36. [44]

    Counting small induced subgraphs satisfying monotone properties

    Marc Roth, Johannes Schmitt, and Philip Wellnitz. Counting small induced subgraphs satisfying monotone properties. In Proc.\ of IEEE FOCS , pages 1356--1367, 2020. https://doi.org/10.1109/FOCS46700.2020.00128 doi:10.1109/FOCS46700.2020.00128

    2020

  37. [45]

    Fractional Graph Theory: A Rational Approach to the Theory of Graphs

    Edward Scheinerman and Daniel Ullman. Fractional Graph Theory: A Rational Approach to the Theory of Graphs . 2011

    2011

  38. [46]

    Vazirani

    Vijay V. Vazirani. Approximation algorithms . 2001

    2001

  39. [47]

    Learning with hypergraphs: Clustering, classification, and embedding

    Dengyong Zhou, Jiayuan Huang, and Bernhard Sch \" o lkopf. Learning with hypergraphs: Clustering, classification, and embedding. In Advances in Neural Information Processing Systems 19, Proceedings of the Twentieth Annual Conference on Neural Information Processing Systems, Va...

    2006

Pith tools

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