Marc Roth

TCS Journal 2024 Journal Article

Parameterised approximation of the fixation probability of the dominant mutation in the multi-type Moran process

• Leslie Ann Goldberg
• Marc Roth
• Tassilo Schwarz

The multi-type Moran process is an evolutionary process on a connected graph G in which each vertex has one of k types and, in each step, a vertex v is chosen to reproduce its type to one of its neighbours. The probability of a vertex v being chosen for reproduction is proportional to the fitness of the type of v. So far, the literature was almost solely concerned with the 2-type Moran process in which each vertex is either healthy (type 0) or a mutant (type 1), and the main problem of interest has been the (approximate) computation of the so-called fixation probability, i. e. , the probability that eventually all vertices are mutants. In this work we initiate the study of approximating fixation probabilities in the multi-type Moran process on general graphs. Our main result is an FPTRAS (fixed-parameter tractable randomised approximation scheme) for computing the fixation probability of the dominant mutation; the parameter is the number of types and their fitnesses. In the course of our studies we also provide novel upper bounds on the expected absorption time, i. e. , the time that it takes the multi-type Moran process to reach a state in which each vertex has the same type.

STOC Conference 2023 Conference Paper

The Complexity of Pattern Counting in Directed Graphs, Parameterised by the Outdegree

• Marco Bressan 0002
• Matthias Lanzinger
• Marc Roth

We study the fixed-parameter tractability of the following fundamental problem: given two directed graphs H → and G → , count the number of copies of H → in G → . The standard setting, where the tractability is well understood, uses only | H → | as a parameter. In this paper we adopt as a parameter | H → |+ d ( G → ), where d ( G → ) is the maximum outdegree of | G → |. Under this parameterisation, we completely characterize the fixed-parameter tractability of the problem in both its non-induced and induced versions through two novel structural parameters, the fractional cover number ρ * and the source number α s . On the one hand we give algorithms with running time f (| H → |, d ( G → )) · | G → | ρ * ( H → )+ O (1) and f (| H → |, d ( G → )) · | G → | α s ( H → )+ O (1) for counting respectively the copies and induced copies of H → in G → ; on the other hand we show that, unless the Exponential Time Hypothesis fails, for any class C → of directed graphs the restriction of the problem to patterns in C → is fixed-parameter tractable if and only if ρ * ( C → ) is bounded (α s ( C → ) for the induced version). These results explain how the orientation of the pattern can make counting easy or hard, and prove that a classic algorithm by Chiba and Nishizeki and its extensions (Chiba and Nishizeki, SICOMP ’85; Bressan, Algorithmica ’21) are optimal unless ETH fails. Our proofs consist of several layers of parameterised reductions that preserve the outdegree of the host graph. To start with, we establish a tight connection between counting homomorphisms from H → to G → to #CSP, the problem of counting solutions of constraint satisfactions problems, for special classes of patterns that we call canonical DAGs. To lift these results from canonical DAGs to arbitrary directed graphs, we exploit a combination of several ingredients: existing results for #CSPs (Marx JACM 13; Grohe, Marx TALG 14), an extension of graph motif parameters (Curticapean, Dell, Marx STOC 17) to our setting, the introduction of what we call monotone reversible minors, and a careful analysis of quotients of directed graphs in order to relate their adaptive width and fractional hypertreewidth to our novel parameters. Along the route we establish a novel bound of the integrality gap for the fractional independence number of hypergraphs based on adaptive width, which might be of independent interest.

STOC Conference 2022 Conference Paper

Counting small induced subgraphs with hereditary properties

• Jacob Focke
• Marc Roth

We study the computational complexity of the problem #IndSub(Φ) of counting k -vertex induced subgraphs of a graph G that satisfy a graph property Φ. Our main result establishes an exhaustive and explicit classification for all hereditary properties, including tight conditional lower bounds under the Exponential Time Hypothesis (ETH): If a hereditary property Φ is true for all graphs, or if it is true only for finitely many graphs, then #IndSub(Φ) is solvable in polynomial time. Otherwise, #IndSub(Φ) is # W [1]-complete when parameterised by k , and, assuming ETH, it cannot be solved in time f ( k )· | G | o ( k ) for any function f . This classification features a wide range of properties for which the corresponding detection problem (as classified by Khot and Raman [TCS 02]) is tractable but counting is hard. Moreover, even for properties which are already intractable in their decision version, our results yield significantly stronger lower bounds for the counting problem. As additional result, we also present an exhaustive and explicit parameterised complexity classification for all properties that are invariant under homomorphic equivalence. By covering one of the most natural and general notions of closure, namely, closure under vertex-deletion (hereditary), we generalise some of the earlier results on this problem. For instance, our results fully subsume and strengthen the existing classification of #IndSub(Φ) for monotone (subgraph-closed) properties due to Roth, Schmitt, and Wellnitz [FOCS 20]. A full version of our paper, containing all proofs, is available at https://arxiv.org/abs/2111.02277 .

SODA Conference 2021 Conference Paper

Counting Homomorphisms to K 4 -minor-free Graphs, modulo 2

• Jacob Focke
• Leslie Ann Goldberg
• Marc Roth
• Stanislav Zivný

We study the problem of computing the parity of the number of homomorphisms from an input graph G to a fixed graph H. Faben and Jerrum [ToC'15] introduced an explicit criterion on the graph H and conjectured that, if satisfied, the problem is solvable in polynomial time and, otherwise, the problem is complete for the complexity class ⊕P of parity problems. We verify their conjecture for all graphs H that exclude the complete graph on 4 vertices as a minor. Further, we rule out the existence of a subexponential-time algorithm for the ⊕P-complete cases, assuming the randomised Exponential Time Hypothesis. Our proofs introduce a novel method of deriving hardness from globally defined substructures of the fixed graph H. Using this, we subsume all prior progress towards resolving the conjecture (Faben and Jerrum [ToC'15]; Göbel, Goldberg and Richerby [ToCT'14, '16]). As special cases, our machinery also yields a proof of the conjecture for graphs with maximum degree at most 3, as well as a full classification for the problem of counting list homomorphisms, modulo 2. A full version of our paper, containing all proofs, is available at https: //arxiv. org/abs/2006. 16632v2. Here we number key lemmas to match the numbering in the full version.

FOCS Conference 2021 Conference Paper

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

• Marco Bressan 0002
• Marc Roth

We study the problems of counting the homomorphisms, the copies, and the induced copies of a $k$ -vertex graph $H$ in a $d$ -degenerate $n$ -vertex graph $G$. By leveraging a new family of graph-minor obstructions called F-gadgets, we establish explicit and exhaustive complexity classifications for counting copies and induced copies. For instance. , we show that the copies of $H$ in $G$ can be counted in time $f(k, d)n^{\max(1, \mathsf{imn}(H))} \log n$, where $f$ is some computable function and $\mathsf{imn} (H)$ is the size of the largest induced matching of $H$; and that whenever the class of allowed patterns has arbitrarily large induced matchings, no algorithm runs in time $f(k, d)n^{o(\mathsf{imn}(H)/\log \mathsf{imn}(H))}$ for any function $f$, unless the Exponential Time Hypothesis fails. A similar result holds for counting induced copies, with the independence number $\alpha(H)$ in place of $\mathsf{imn}(H)$. These results imply complexity dichotomies, into fixed-parameter tractable versus #W[1]-hard cases, which parallel the well-known dichotomies when $d$ is not a parameter. Our results also imply the #W[1]-hardness of counting several patterns, such as $k$ -matchings and $k$ -trees, in $d$ - degenerate graphs. We also give new hardness results and approximation algorithms for generalized pattern counting (i. e. , counting patterns with a given property) in degenerate graphs.

MFCS Conference 2021 Conference Paper

Parameterized (Modular) Counting and Cayley Graph Expanders

• Norbert Peyerimhoff
• Marc Roth
• Johannes Schmitt 0002
• Jakob Stix
• Alina Vdovina

We study the problem #EdgeSub(Φ) of counting k-edge subgraphs satisfying a given graph property Φ in a large host graph G. Building upon the breakthrough result of Curticapean, Dell and Marx (STOC 17), we express the number of such subgraphs as a finite linear combination of graph homomorphism counts and derive the complexity of computing this number by studying its coefficients. Our approach relies on novel constructions of low-degree Cayley graph expanders of p-groups, which might be of independent interest. The properties of those expanders allow us to analyse the coefficients in the aforementioned linear combinations over the field 𝔽_p which gives us significantly more control over the cancellation behaviour of the coefficients. Our main result is an exhaustive and fine-grained complexity classification of #EdgeSub(Φ) for minor-closed properties Φ, closing the missing gap in previous work by Roth, Schmitt and Wellnitz (ICALP 21). Additionally, we observe that our methods also apply to modular counting. Among others, we obtain novel intractability results for the problems of counting k-forests and matroid bases modulo a prime p. Furthermore, from an algorithmic point of view, we construct algorithms for the problems of counting k-paths and k-cycles modulo 2 that outperform the best known algorithms for their non-modular counterparts. In the course of our investigations we also provide an exhaustive parameterized complexity classification for the problem of counting graph homomorphisms modulo a prime p.

SODA Conference 2020 Conference Paper

Counting and Finding Homomorphisms is Universal for Parameterized Complexity Theory

• Marc Roth
• Philip Wellnitz

FOCS Conference 2020 Conference Paper

Counting Small Induced Subgraphs Satisfying Monotone Properties

• Marc Roth
• Johannes Schmitt 0002
• Philip Wellnitz

Given a graph property Φ, we study the problem #INDSUB(Φ) which asks, on input a graph G and a positive integer k, to compute the number # IndSub(Φ, k→ G) of induced subgraphs of size k in G that satisfy Φ. The search for explicit criteria on Φ ensuring that # INDSUB(Φ) is hard was initiated by Jerrum and Meeks [J. Comput. Syst. Sci. 15] and is part of the major line of research on counting small patterns in graphs. However, apart from an implicit result due to Curticapean, Dell and Marx [STOC 17] proving that a full classification into “easy” and “hard” properties is possible and some partial results on edge-monotone properties due to Meeks [Discret. Appl. Math. 16] and Dörfler et al. [MFCS 19], not much is known. In this work, we fully answer and explicitly classify the case of monotone, that is subgraph-closed, properties: We show that for any non-trivial monotone property Φ, the problem #INDSUB(Φ) cannot be solved in time f(k). |V(G)| o(k/log1/2 (k)) for any function f, unless the Exponential Time Hypothesis fails. By this, we establish that any significant improvement over the brute-force approach is unlikely; in the language of parameterized complexity, we also obtain a #W[1] - completeness result.

MFCS Conference 2019 Conference Paper

Counting Induced Subgraphs: An Algebraic Approach to #W[1]-hardness

• Julian Dörfler
• Marc Roth
• Johannes Schmitt 0002
• Philip Wellnitz

We study the problem #IndSub(Phi) of counting all induced subgraphs of size k in a graph G that satisfy the property Phi. This problem was introduced by Jerrum and Meeks and shown to be #W[1]-hard when parameterized by k for some families of properties Phi including, among others, connectivity [JCSS 15] and even- or oddness of the number of edges [Combinatorica 17]. Very recently [IPEC 18], two of the authors introduced a novel technique for the complexity analysis of #IndSub(Phi), inspired by the "topological approach to evasiveness" of Kahn, Saks and Sturtevant [FOCS 83] and the framework of graph motif parameters due to Curticapean, Dell and Marx [STOC 17], allowing them to prove hardness of a wide range of properties Phi. In this work, we refine this technique for graph properties that are non-trivial on edge-transitive graphs with a prime power number of edges. In particular, we fully classify the case of monotone bipartite graph properties: It is shown that, given any graph property Phi that is closed under the removal of vertices and edges, and that is non-trivial for bipartite graphs, the problem #IndSub(Phi) is #W[1]-hard and cannot be solved in time f(k)* n^{o(k)} for any computable function f, unless the Exponential Time Hypothesis fails. This holds true even if the input graph is restricted to be bipartite and counting is done modulo a fixed prime. A similar result is shown for properties that are closed under the removal of edges only.