Radu Curticapean

SODA Conference 2025 Conference Paper

Counting Small Induced Subgraphs: Hardness via Fourier Analysis

• Radu Curticapean
• Daniel Neuen

SODA Conference 2025 Conference Paper

Fast Deterministic Chromatic Number under the Asymptotic Rank Conjecture

• Andreas Björklund
• Radu Curticapean
• Thore Husfeldt
• Petteri Kaski
• Kevin Pratt

In this paper we further explore the recently discovered connection by Björklund and Kaski [STOC 2024] and Pratt [STOC 2024] between the asymptotic rank conjecture of Strassen [Progr. Math. 1994] and the three-way partitioning problem. We show that under the asymptotic rank conjecture, the chromatic number of an n -vertex graph can be computed deterministically in O (1. 99982 n ) time, thus giving a conditional answer to a question of Zamir [ICALP 2021], and questioning the optimality of the 2 n poly( n ) time algorithm for chromatic number by Björklund, Husfeldt, and Koivisto [SICOMP 2009]. Viewed in the other direction, if chromatic number indeed requires deterministic algorithms to run in close to 2 n time, we obtain a sequence of explicit tensors of superlinear rank, falsifying the asymptotic rank conjecture. Our technique is a combination of earlier algorithms for detecting k -colorings for small k and enumerating k -colorable subgraphs, with an extension and derandomisation of Pratt’s tensor-based algorithm for balanced three-way partitioning to the unbalanced case.

MFCS Conference 2025 Conference Paper

Monotone Bounded-Depth Complexity of Homomorphism Polynomials

• C. S. Bhargav
• Shiteng Chen
• Radu Curticapean
• Prateek Dwivedi 0001

For every fixed graph H, it is known that homomorphism counts from H and colorful H-subgraph counts can be determined in O(n^{t+1}) time on n-vertex input graphs G, where t is the treewidth of H. On the other hand, a running time of n^{o(t / log t)} would refute the exponential-time hypothesis. Komarath, Pandey, and Rahul (Algorithmica, 2023) studied algebraic variants of these counting problems, i. e. , homomorphism and subgraph polynomials for fixed graphs H. These polynomials are weighted sums over the objects counted above, where each object is weighted by the product of variables corresponding to edges contained in the object. As shown by Komarath et al. , the monotone circuit complexity of the homomorphism polynomial for H is Θ(n^{tw(H)+1}). In this paper, we characterize the power of monotone bounded-depth circuits for homomorphism and colorful subgraph polynomials. This leads us to discover a natural hierarchy of graph parameters tw_Δ(H), for fixed Δ ∈ ℕ, which capture the width of tree-decompositions for H when the underlying tree is required to have depth at most Δ. We prove that monotone circuits of product-depth Δ computing the homomorphism polynomial for H require size Θ(n^{tw_Δ(H^{†})+1}), where H^{†} is the graph obtained from H by removing all degree-1 vertices. This allows us to derive an optimal depth hierarchy theorem for monotone bounded-depth circuits through graph-theoretic arguments.

MFCS Conference 2025 Conference Paper

Which Graph Motif Parameters Count?

• Markus Bläser
• Radu Curticapean
• Julian Dörfler
• Christian Ikenmeyer

For a fixed graph H, the function #Ind(H → ⋆) maps graphs G to the count of induced H-copies in G; this function obviously "counts something" in that it has a combinatorial interpretation. Linear combinations of such functions are called graph motif parameters and have recently received significant attention in counting complexity after a seminal paper by Curticapean, Dell and Marx (STOC'17). We show that, among linear combinations of functions #Ind(H → ⋆) involving only graphs H without isolated vertices, precisely those with positive integer coefficients maintain a combinatorial interpretation. It is important to note that graph motif parameters can be nonnegative for all inputs G, even when some coefficients are negative. Formally, we show that evaluating any graph motif parameter with a negative coefficient is impossible in an oracle variant of #P, where an implicit graph is accessed by oracle queries. Our proof follows the classification of the relativizing closure properties of #P by Hertrampf, Vollmer, and Wagner (SCT'95) and the framework developed by Ikenmeyer and Pak (STOC'22), but our application of the required Ramsey theorem turns out to be more subtle, as graphs do not have the required Ramsey property. Our techniques generalize from graphs to relational structures, including colored graphs. Vastly generalizing this, we introduce motif parameters over categories that count occurrences of sub-objects in the category. We then prove a general dichotomy theorem that characterizes which such parameters have a combinatorial interpretation. Using known results in Ramsey theory for categories, we obtain a dichotomy for motif parameters of finite vector spaces as well as parameter sets.

SODA Conference 2024 Conference Paper

Count on CFI graphs for #P-hardness

• Radu Curticapean

STOC Conference 2021 Conference Paper

A full complexity dichotomy for immanant families

• Radu Curticapean

SODA Conference 2018 Conference Paper

A Tight Lower Bound for Counting Hamiltonian Cycles via Matrix Rank

• Radu Curticapean
• Nathan Lindzey
• Jesper Nederlof

For even k ∊ ℕ, the matchings connectivity matrix M k is a binary matrix indexed by perfect matchings on k vertices; the entry at ( M, M ‘) is 1 iff M ∪ M ‘ forms a single cycle. Cygan et al. (STOC 2013) showed that the rank of M k over ℤ is and used this to give an time algorithm for counting Hamiltonian cycles modulo 2 on graphs of pathwidth pw, carrying over to the decision problem via witness isolation. The same authors complemented their algorithm by an essentially tight lower bound under the Strong Exponential Time Hypothesis (SETH). This bound crucially relied on a large permutation submatrix within M k, which enabled a “pattern propagation” commonly used in previous related lower bounds, as initiated by Lokshtanov et al. (SODA 2011). We present a new technique for a similar “pattern propagation” when only a black-box lower bound on the asymptotic rank of M k is given; no stronger structural insights such as the existence of large permutation submatrices in M k are needed. Given appropriate rank bounds, our technique yields lower bounds for counting Hamiltonian cycles (also modulo fixed primes p) parameterized by pathwidth. To apply this technique, we prove that the rank of M k over the rationals is 4 k /poly( k ), using the representation theory of the symmetric group and various insights from algebraic combinatorics. We also show that the rank of M k over ℤ p is Ω(1. 57 k ) for any prime p ≠ 2. Combining our rank bounds with the new pattern propagation technique, we show that Hamiltonian cycles cannot be counted in time O *((6 – ε ) pw ) for any ε > 0 unless SETH fails. This bound is tight due to a O *(6 pw ) time algorithm by Bodlaender et al. (ICALP 2013). Under SETH, we also obtain that Hamiltonian cycles cannot be counted modulo primes p ≠ 2 in time O *(3. 57 pw ), indicating that the modulus can affect the complexity in intricate ways.

STOC Conference 2017 Conference Paper

Homomorphisms are a good basis for counting small subgraphs

• Radu Curticapean
• Holger Dell
• Dániel Marx

SODA Conference 2016 Conference Paper

Tight conditional lower bounds for counting perfect matchings on graphs of bounded treewidth, cliquewidth, and genus

• Radu Curticapean
• Dániel Marx

By now, we have a good understanding of how NP-hard problems become easier on graphs of bounded treewidth and bounded cliquewidth: for various problems, matching upper bounds and conditional lower bounds describe exactly how the running time has to depend on treewidth or cliquewidth. In particular, Fomin et al. (2009, 2010) have shown a significant difference between these two parameters: assuming the Exponential-Time Hypothesis (ETH), the optimal algorithms for problems such as M ax C ut and E dge D ominating S et have running time 2 O ( t ) n O (1) when parameterized by treewidth, but n O ( t ) when parameterized by cliquewidth. In this paper, we show that a similar phenomenon occurs also for counting problems. Specifically, we prove that, assuming the counting version of the Strong Exponential-Time Hypothesis (#SETH), the problem of counting perfect matchings has no (2 – ∊ ) k n O (1) time algorithm for any ∊ > 0 on graphs of treewidth k (but it is known to be solvable in time 2 k n O (1) if a tree decomposition of width k is given), and has no O ( n (1– ∊ ) k ) time algorithm for any ∊ > 0 on graphs of cliquewidth k (but it can be solved in time O ( n k +1 ) if a k -expression is given). A celebrated result of Fisher, Kasteleyn, and Temperley from the 1960s shows that counting perfect matchings in planar graphs is polynomial-time solvable. This was later extended by Gallucio and Loebl (1999), Tesler (2000) and Regge and Zechina (2000) who gave 4 k · n O (1) time algorithms for graphs of genus k. We show that the dependence on the genus k has to be exponential: assuming #ETH, the counting version of ETH, there is no 2 o ( k ) · n O (1) time algorithm for the problem on graphs of genus k.

FOCS Conference 2015 Conference Paper

Parameterizing the Permanent: Genus, Apices, Minors, Evaluation Mod 2k

• Radu Curticapean
• Mingji Xia

We identify and study relevant structural parameters for the problem PerfMatch of counting perfect matchings in a given input graph C. These generalize the well-known tractable planar case, and they include the genus of C, its apex number (the minimum number of vertices whose removal renders C planar), and its Hadwiger number (the size of a largest clique minor). To study these parameters, we first introduce the notion of combined matchgates, a general technique that bridges parameterized counting problems and the theory of so-called Holants and matchgates: Using combined matchgates, we can simulate certain nonexisting gadgets F as linear combinations of L = O(1) existing gadgets. If a graph C features k occurrences of F, we can then reduce C to t k graphs that feature only existing gadgets, thus enabling parameterized reductions. As applications of this technique, we simplify known 4 g n O(1) time algorithms for PerfMatch on graphs of genus g. Orthogonally to this, we show #W[1]-hardness of the permanent on k-apex graphs, implying its ⊕W[1]-hardness under the Hadwiger number. Additionally, we rule out n o(k/ log k) time algorithms under the counting exponential-time hypothesis #ETH. Finally, we use combined matchgates to prove $W[1]-hardness of evaluating the permanent modulo 2k, complementing an O(n 4k-3 ) time algorithm by Valiant and answering an open question of Bjϋrklund. We also obtain a lower bound of n Ω(k/ log k) under the parity version $ETH of the exponential-time hypothesis.

FOCS Conference 2014 Conference Paper

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

• Radu Curticapean
• Dániel Marx

For a class C of graphs, #Sub(C) is the counting problem that, given a graph H from C and an arbitrary graph G, asks for the number of subgraphs of G isomorphic to H. It is known that if C has bounded vertex-cover number (equivalently, the size of the maximum matching in C is bounded), then #Sub(C) is polynomial-time solvable. We complement this result with a corresponding lower bound: if C is any recursively enumerable class of graphs with unbounded vertexcover number, then #Sub(C) is #W[1]-hard parameterized by the size of H and hence not polynomial-time solvable and not even fixed-parameter tractable, unless FPT is equal to #W[1]. As a first step of the proof, we show that counting kmatchings in bipartite graphs is #W[1]-hard. Recently, Curticapean [ICALP 2013] proved the #W[1]-hardness of counting k-matchings in general graphs; our result strengthens this statement to bipartite graphs with a considerably simpler proof and even shows that, assuming the Exponential Time Hypothesis (ETH), there is no f(k)*n^o(k/log(k)) time algorithm for counting k-matchings in bipartite graphs for any computable function f. As a consequence, we obtain an independent and somewhat simpler proof of the classical result of Flum and Grohe [SICOMP 2004] stating that counting paths of length k is #W[1]-hard, as well as a similar almost-tight ETH-based lower bound on the exponent.

MFCS Conference 2011 Conference Paper

The Complexity of the Cover Polynomials for Planar Graphs of Bounded Degree

• Markus Bläser
• Radu Curticapean

Abstract The cover polynomials are bivariate graph polynomials that can be defined as weighted sums over all path-cycle covers of a graph. In [3], a dichotomy result for the cover polynomials was proven, establishing that their evaluation is # P -hard everywhere but at a finite set of points, where evaluation is in FP. In this paper, we show that almost the same dichotomy holds when restricting the evaluation to planar graphs. We even provide hardness results for planar DAGs of bounded degree. For particular subclasses of planar graphs of bounded degree and for variants thereof, we also provide algorithms that allow for polynomial-time evaluation of the cover polynomials at certain new points by utilizing Valiant’s holographic framework.