Marc Roth
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Marc Roth has a total of 22 co-authors. Here are the top co-authors by number of shared publications:
- Philip Wellnitz
National Institute of Informatics, and The Graduate University for Advanced Studies, SOKENDAI, Tokyo, Japan
7 shared publications - Jacob Focke
CISPA Helmholtz Center for Information Security, Saarbrücken, Germany
6 shared publications - Leslie Ann Goldberg
Department of Computer Science, University of Oxford, Oxford, UK
5 shared publications - Johannes Schmitt
Department of Mathematics, ETH Zürich, Zürich, Switzerland
4 shared publications - Stanislav Živný
University of Oxford, Oxford, United Kingdom
4 shared publications - Marco Bressan
University of Milan, Milan, Italy
3 shared publications
Latest Publications
- Open Access
- 16 January 2026
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Computational Logic
- Vol. 27 (1) , 1-36
Counting Answers to Unions of Conjunctive Queries: Natural Tractability Criteria and Meta-Complexity
We study the problem of counting answers to unions of conjunctive queries (UCQs) under structural restrictions on the input query. Concretely, given a class \( C \) of UCQs, the problem \(\#\text{UCQ} (C)\) provides as input a UCQ \(\Psi\in C\) and a database \(\mathcal{D}\) and the problem is to compute the number of answers of \(\Psi\) in \(\mathcal{D}\) . Chen and Mengel [PODS ’16] have shown that for any recursively enumerable class \( C \) , the problem \(\#\text{UCQ} (C)\) is either fixed-parameter tractable or hard for one of the parameterised complexity classes \(\mathrm{W}[1]\) or \(\#\mathrm{W}[1]\) . However, their tractability criterion is unwieldy in the sense that, given any concrete class \( C \) of UCQs, it is not easy to determine how hard it is to count answers to queries in \( C \) . Moreover, given a single specific UCQ \(\Psi\) , it is not easy to determine how hard it is to count answers to \(\Psi\) . In this work, we address the question of finding a natural tractability criterion: The combined conjunctive query of a UCQ \(\Psi=\varphi_{1}\vee\dots\vee\varphi_{\ell}\) is the conjunctive query \(\boldsymbol{\wedge}\left(\Psi\right)=\varphi_{1}\wedge\dots\wedge\varphi_{\ell}\) . We show that under natural closure properties of \( C \) , the problem \(\#\text{UCQ} (C)\) is FPT if and only if the combined conjunctive queries of UCQs in \( C \) , and their contracts, have bounded treewidth. A contract of a conjunctive query is an augmented structure, taking into account how the quantified variables are connected to the free variables—if all variables are free, then a conjunctive query is equal to its contract; in this special case the criterion for fixed-parameter tractability of \(\#\text{UCQ} (C)\) thus simplifies to the combined queries having bounded treewidth. Finally, we give evidence that a closure property on \( C \) is necessary for obtaining a natural tractability criterion: We show that even for a single UCQ \(\Psi\) , the meta problem of deciding whether \(\#\text{UCQ} (\{\Psi\})\) can be solved in time \(O(|\mathcal{D}|^{d})\) is \(\mathrm{NP}\) -hard for any fixed \(d\geq 1\) . Moreover, we prove that a known exponential-time algorithm for solving the meta problem is optimal under assumptions from fine-grained complexity theory. As a corollary of our reduction, we also establish that approximating the Weisfeiler-Leman-Dimension of a UCQ is \(\mathrm{NP}\) -hard.- 16 January 2026
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Computational Logic
- Vol. 27 (1) , 1-36
Open AccessCounting Answers to Unions of Conjunctive Queries: Natural Tractability Criteria and Meta-Complexity
We study the problem of counting answers to unions of conjunctive queries (UCQs) under structural restrictions on the input query. Concretely, given a class \( C \) of UCQs, the problem \(\#\text{UCQ} (C)\) provides as input a UCQ \(\Psi\in C\) and a database \(\mathcal{D}\) and the problem is to compute the number of answers of \(\Psi\) in \(\mathcal{D}\) . Chen and Mengel [PODS ’16] have shown that for any recursively enumerable class \( C \) , the problem \(\#\text{UCQ} (C)\) is either fixed-parameter tractable or hard for one of the parameterised complexity classes \(\mathrm{W}[1]\) or \(\#\mathrm{W}[1]\) . However, their tractability criterion is unwieldy in the sense that, given any concrete class \( C \) of UCQs, it is not easy to determine how hard it is to count answers to queries in \( C \) . Moreover, given a single specific UCQ \(\Psi\) , it is not easy to determine how hard it is to count answers to \(\Psi\) . In this work, we address the question of finding a natural tractability criterion: The combined conjunctive query of a UCQ \(\Psi=\varphi_{1}\vee\dots\vee\varphi_{\ell}\) is the conjunctive query \(\boldsymbol{\wedge}\left(\Psi\right)=\varphi_{1}\wedge\dots\wedge\varphi_{\ell}\) . We show that under natural closure properties of \( C \) , the problem \(\#\text{UCQ} (C)\) is FPT if and only if the combined conjunctive queries of UCQs in \( C \) , and their contracts, have bounded treewidth. A contract of a conjunctive query is an augmented structure, taking into account how the quantified variables are connected to the free variables—if all variables are free, then a conjunctive query is equal to its contract; in this special case the criterion for fixed-parameter tractability of \(\#\text{UCQ} (C)\) thus simplifies to the combined queries having bounded treewidth. Finally, we give evidence that a closure property on \( C \) is necessary for obtaining a natural tractability criterion: We show that even for a single UCQ \(\Psi\) , the meta problem of deciding whether \(\#\text{UCQ} (\{\Psi\})\) can be solved in time \(O(|\mathcal{D}|^{d})\) is \(\mathrm{NP}\) -hard for any fixed \(d\geq 1\) . Moreover, we prove that a known exponential-time algorithm for solving the meta problem is optimal under assumptions from fine-grained complexity theory. As a corollary of our reduction, we also establish that approximating the Weisfeiler-Leman-Dimension of a UCQ is \(\mathrm{NP}\) -hard. - Open Access
- 4 October 2025
- Published by Elsevier in Computer Science Review
- Vol. 59
Parameterised counting complexity theory
- 4 October 2025
- Published by Elsevier in Computer Science Review
- Vol. 59
Open AccessParameterised counting complexity theory
- Open Access
- 30 November 2024
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
- Vol. 21 (1) , 1-29
Approximately Counting Answers to Conjunctive Queries with Disequalities and Negations
We study the complexity of approximating the number of answers to a small query \(\varphi\) in a large database \(\mathcal{D}\) . We establish an exhaustive classification into tractable and intractable cases if \(\varphi\) is a conjunctive query possibly including disequalities and negations: — If there is a constant bound on the arity of \(\varphi\) , and if the randomised Exponential Time Hypothesis (rETH) holds, then the problem has a fixed-parameter tractable approximation scheme (FPTRAS) if and only if the treewidth of \(\varphi\) is bounded. — If the arity is unbounded and \(\varphi\) does not have negations, then the problem has an FPTRAS if and only if the adaptive width of \(\varphi\) (a width measure strictly more general than treewidth) is bounded; the lower bound relies on the rETH as well. Additionally we show that our results cannot be strengthened to achieve a fully polynomial randomised approximation scheme (FPRAS): We observe that, unless \(\mathrm{NP}=\mathrm{RP}\) , there is no FPRAS even if the treewidth (and the adaptive width) is \(1\) . However, if there are neither disequalities nor negations, we prove the existence of an FPRAS for queries of bounded fractional hypertreewidth, strictly generalising the recently established FPRAS for conjunctive queries with bounded hypertreewidth due to Arenas, Croquevielle, Jayaram and Riveros (STOC 2021).- 30 November 2024
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
- Vol. 21 (1) , 1-29
Open AccessApproximately Counting Answers to Conjunctive Queries with Disequalities and Negations
We study the complexity of approximating the number of answers to a small query \(\varphi\) in a large database \(\mathcal{D}\) . We establish an exhaustive classification into tractable and intractable cases if \(\varphi\) is a conjunctive query possibly including disequalities and negations: — If there is a constant bound on the arity of \(\varphi\) , and if the randomised Exponential Time Hypothesis (rETH) holds, then the problem has a fixed-parameter tractable approximation scheme (FPTRAS) if and only if the treewidth of \(\varphi\) is bounded. — If the arity is unbounded and \(\varphi\) does not have negations, then the problem has an FPTRAS if and only if the adaptive width of \(\varphi\) (a width measure strictly more general than treewidth) is bounded; the lower bound relies on the rETH as well. Additionally we show that our results cannot be strengthened to achieve a fully polynomial randomised approximation scheme (FPRAS): We observe that, unless \(\mathrm{NP}=\mathrm{RP}\) , there is no FPRAS even if the treewidth (and the adaptive width) is \(1\) . However, if there are neither disequalities nor negations, we prove the existence of an FPRAS for queries of bounded fractional hypertreewidth, strictly generalising the recently established FPRAS for conjunctive queries with bounded hypertreewidth due to Arenas, Croquevielle, Jayaram and Riveros (STOC 2021). - 27 September 2024
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 53 (5) , 1409-1438
Counting Subgraphs in Somewhere Dense Graphs
We study the problems of counting copies and induced copies of a small pattern graph [Formula: see text] in a large host graph [Formula: see text]. Recent work fully classified the complexity of those problems according to structural restrictions on the patterns [Formula: see text]. In this work, we address the more challenging task of analyzing the complexity for restricted patterns and restricted hosts. Specifically, we ask which families of allowed patterns and hosts imply fixed-parameter tractability, i.e., the existence of an algorithm running in time [Formula: see text] for some computable function [Formula: see text]. Our main results present exhaustive and explicit complexity classifications for families that satisfy natural closure properties. Among others, we identify the problems of counting small matchings and independent sets in subgraph-closed graph classes [Formula: see text] as our central objects of study and establish the following crisp dichotomies as consequences of the exponential time hypothesis: (1) Counting [Formula: see text]-matchings in a graph [Formula: see text] is fixed-parameter tractable if and only if [Formula: see text] is nowhere dense. (2) Counting [Formula: see text]-independent sets in a graph [Formula: see text] is fixed-parameter tractable if and only if [Formula: see text] is nowhere dense. Moreover, we obtain almost tight conditional lower bounds if [Formula: see text] is somewhere dense, i.e., not nowhere dense. These base cases of our classifications subsume a wide variety of previous results on the matching and independent set problem, such as counting [Formula: see text]-matchings in bipartite graphs (Curticapean, Marx; FOCS 14), in [Formula: see text]-colorable graphs (Roth, Wellnitz; SODA 20), and in degenerate graphs (Bressan, Roth; FOCS 21), as well as counting [Formula: see text]-independent sets in bipartite graphs (Curticapean et al.; Algorithmica 19). At the same time, our proofs are much simpler: using structural characterizations of somewhere dense graphs, we show that a colorful version of a recent breakthrough technique for analyzing pattern counting problems (Curticapean, Dell, Marx; STOC 17) applies to any subgraph-closed somewhere dense class of graphs, yielding a unified view of our current understanding of the complexity of subgraph counting.
- 27 September 2024
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 53 (5) , 1409-1438
Counting Subgraphs in Somewhere Dense Graphs
We study the problems of counting copies and induced copies of a small pattern graph [Formula: see text] in a large host graph [Formula: see text]. Recent work fully classified the complexity of those problems according to structural restrictions on the patterns [Formula: see text]. In this work, we address the more challenging task of analyzing the complexity for restricted patterns and restricted hosts. Specifically, we ask which families of allowed patterns and hosts imply fixed-parameter tractability, i.e., the existence of an algorithm running in time [Formula: see text] for some computable function [Formula: see text]. Our main results present exhaustive and explicit complexity classifications for families that satisfy natural closure properties. Among others, we identify the problems of counting small matchings and independent sets in subgraph-closed graph classes [Formula: see text] as our central objects of study and establish the following crisp dichotomies as consequences of the exponential time hypothesis: (1) Counting [Formula: see text]-matchings in a graph [Formula: see text] is fixed-parameter tractable if and only if [Formula: see text] is nowhere dense. (2) Counting [Formula: see text]-independent sets in a graph [Formula: see text] is fixed-parameter tractable if and only if [Formula: see text] is nowhere dense. Moreover, we obtain almost tight conditional lower bounds if [Formula: see text] is somewhere dense, i.e., not nowhere dense. These base cases of our classifications subsume a wide variety of previous results on the matching and independent set problem, such as counting [Formula: see text]-matchings in bipartite graphs (Curticapean, Marx; FOCS 14), in [Formula: see text]-colorable graphs (Roth, Wellnitz; SODA 20), and in degenerate graphs (Bressan, Roth; FOCS 21), as well as counting [Formula: see text]-independent sets in bipartite graphs (Curticapean et al.; Algorithmica 19). At the same time, our proofs are much simpler: using structural characterizations of somewhere dense graphs, we show that a colorful version of a recent breakthrough technique for analyzing pattern counting problems (Curticapean, Dell, Marx; STOC 17) applies to any subgraph-closed somewhere dense class of graphs, yielding a unified view of our current understanding of the complexity of subgraph counting.
- 22 August 2024
- Published by Elsevier in Theoretical Computer Science
- Vol. 1016
Parameterised approximation of the fixation probability of the dominant mutation in the multi-type Moran process
- 22 August 2024
- Published by Elsevier in Theoretical Computer Science
- Vol. 1016
Parameterised approximation of the fixation probability of the dominant mutation in the multi-type Moran process
- Open Access
- 10 May 2024
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Management of Data
- Vol. 2 (2) , 1-17
The Weisfeiler-Leman Dimension of Conjunctive Queries
A graph parameter is a function f on graphs with the property that, for any pair of isomorphic graphs G 1 and G 2 , f(G 1 )=f(G 2 ). The Weisfeiler--Leman (WL) dimension of f is the minimum k such that, if G 1 and G 2 are indistinguishable by the k-dimensional WL-algorithm then f(G 1 )=f(G 2 ). The WL-dimension of f is ∞ if no such k exists. We study the WL-dimension of graph parameters characterised by the number of answers from a fixed conjunctive query to the graph. Given a conjunctive query φ, we quantify the WL-dimension of the function that maps every graph G to the number of answers of φ in G. The works of Dvorak (J. Graph Theory 2010), Dell, Grohe, and Rattan (ICALP 2018), and Neuen (ArXiv 2023) have answered this question for full conjunctive queries, which are conjunctive queries without existentially quantified variables. For such queries φ, the WL-dimension is equal to the treewidth of the Gaifman graph of φ. In this work, we give a characterisation that applies to all conjunctive queries. Given any conjunctive query φ, we prove that its WL-dimension is equal to the semantic extension width sew(φ), a novel width measure that can be thought of as a combination of the treewidth of φ and its quantified star size, an invariant introduced by Durand and Mengel (ICDT 2013) describing how the existentially quantified variables of φ are connected with the free variables. Using the recently established equivalence between the WL-algorithm and higher-order Graph Neural Networks (GNNs) due to Morris et al. (AAAI 2019), we obtain as a consequence that the function counting answers to a conjunctive query φ cannot be computed by GNNs of order smaller than sew(φ). The majority of the paper is concerned with establishing a lower bound of the WL-dimension of a query. Given any conjunctive query φ with semantic extension width k, we consider a graph F of treewidth k obtained from the Gaifman graph of φ by repeatedly cloning the vertices corresponding to existentially quantified variables. Using a modification due to Furer (ICALP 2001) of the Cai-Fürer-Immerman construction (Combinatorica 1992), we then obtain a pair of graphs χ(F) and ^χ(F) that are indistinguishable by the (k-1)-dimensional WL-algorithm since F has treewidth k. Finally, in the technical heart of the paper, we show that φ has a different number of answers in χ(F) and ^χ(F). Thus, φ can distinguish two graphs that cannot be distinguished by the (k-1)-dimensional WL-algorithm, so the WL-dimension of φ is at least k.
- 10 May 2024
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Management of Data
- Vol. 2 (2) , 1-17
Open AccessThe Weisfeiler-Leman Dimension of Conjunctive Queries
A graph parameter is a function f on graphs with the property that, for any pair of isomorphic graphs G 1 and G 2 , f(G 1 )=f(G 2 ). The Weisfeiler--Leman (WL) dimension of f is the minimum k such that, if G 1 and G 2 are indistinguishable by the k-dimensional WL-algorithm then f(G 1 )=f(G 2 ). The WL-dimension of f is ∞ if no such k exists. We study the WL-dimension of graph parameters characterised by the number of answers from a fixed conjunctive query to the graph. Given a conjunctive query φ, we quantify the WL-dimension of the function that maps every graph G to the number of answers of φ in G. The works of Dvorak (J. Graph Theory 2010), Dell, Grohe, and Rattan (ICALP 2018), and Neuen (ArXiv 2023) have answered this question for full conjunctive queries, which are conjunctive queries without existentially quantified variables. For such queries φ, the WL-dimension is equal to the treewidth of the Gaifman graph of φ. In this work, we give a characterisation that applies to all conjunctive queries. Given any conjunctive query φ, we prove that its WL-dimension is equal to the semantic extension width sew(φ), a novel width measure that can be thought of as a combination of the treewidth of φ and its quantified star size, an invariant introduced by Durand and Mengel (ICDT 2013) describing how the existentially quantified variables of φ are connected with the free variables. Using the recently established equivalence between the WL-algorithm and higher-order Graph Neural Networks (GNNs) due to Morris et al. (AAAI 2019), we obtain as a consequence that the function counting answers to a conjunctive query φ cannot be computed by GNNs of order smaller than sew(φ). The majority of the paper is concerned with establishing a lower bound of the WL-dimension of a query. Given any conjunctive query φ with semantic extension width k, we consider a graph F of treewidth k obtained from the Gaifman graph of φ by repeatedly cloning the vertices corresponding to existentially quantified variables. Using a modification due to Furer (ICALP 2001) of the Cai-Fürer-Immerman construction (Combinatorica 1992), we then obtain a pair of graphs χ(F) and ^χ(F) that are indistinguishable by the (k-1)-dimensional WL-algorithm since F has treewidth k. Finally, in the technical heart of the paper, we show that φ has a different number of answers in χ(F) and ^χ(F). Thus, φ can distinguish two graphs that cannot be distinguished by the (k-1)-dimensional WL-algorithm, so the WL-dimension of φ is at least k.
- Open Access
- 10 May 2024
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Management of Data
- Vol. 2 (2) , 1-17
Counting Answers to Unions of Conjunctive Queries: Natural Tractability Criteria and Meta-Complexity
We study the problem of counting answers to unions of conjunctive queries (UCQs) under structural restrictions on the input query. Concretely, given a class C of UCQs, the problem #UCQ (C) provides as input a UCQ Ψ ∈ C and a database D and the problem is to compute the number of answers of Ψ in D. Chen and Mengel [PODS'16] have shown that for any recursively enumerable class C, the problem #UCQ (C) is either fixed-parameter tractable or hard for one of the parameterised complexity classes W[1] or #W[1]. However, their tractability criterion is unwieldy in the sense that, given any concrete class C of UCQs, it is not easy to determine how hard it is to count answers to queries in C. Moreover, given a single specific UCQ Ψ, it is not easy to determine how hard it is to count answers to Ψ. In this work, we address the question of finding a natural tractability criterion: The combined conjunctive query of a UCQ Ψ=φ 1 ∨ ... ∨ φ l is the conjunctive query ^ Ψ = φ_1 ∧ ... ∧ φ l . We show that under natural closure properties of C, the problem #UCQ (C) is fixed-parameter tractable if and only if the combined conjunctive queries of UCQs in C, and their contracts, have bounded treewidth. A contract of a conjunctive query is an augmented structure, taking into account how the quantified variables are connected to the free variables --- if all variables are free, then a conjunctive query is equal to its contract; in this special case the criterion for fixed-parameter tractability of #UCQ (C) thus simplifies to the combined queries having bounded treewidth. Finally, we give evidence that a closure property on C is necessary for obtaining a natural tractability criterion: We show that even for a single UCQ Ψ, the meta problem of deciding whether #UCQ (Ψ) can be solved in time O(|D| d ) is NP-hard for any fixed d ≥ 1. Moreover, we prove that a known exponential-time algorithm for solving the meta problem is optimal under assumptions from fine-grained complexity theory. As a corollary of our reduction, we also establish that approximating the Weisfeiler-Leman-Dimension of a UCQ is NP-hard.
- 10 May 2024
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Management of Data
- Vol. 2 (2) , 1-17
Open AccessCounting Answers to Unions of Conjunctive Queries: Natural Tractability Criteria and Meta-Complexity
We study the problem of counting answers to unions of conjunctive queries (UCQs) under structural restrictions on the input query. Concretely, given a class C of UCQs, the problem #UCQ (C) provides as input a UCQ Ψ ∈ C and a database D and the problem is to compute the number of answers of Ψ in D. Chen and Mengel [PODS'16] have shown that for any recursively enumerable class C, the problem #UCQ (C) is either fixed-parameter tractable or hard for one of the parameterised complexity classes W[1] or #W[1]. However, their tractability criterion is unwieldy in the sense that, given any concrete class C of UCQs, it is not easy to determine how hard it is to count answers to queries in C. Moreover, given a single specific UCQ Ψ, it is not easy to determine how hard it is to count answers to Ψ. In this work, we address the question of finding a natural tractability criterion: The combined conjunctive query of a UCQ Ψ=φ 1 ∨ ... ∨ φ l is the conjunctive query ^ Ψ = φ_1 ∧ ... ∧ φ l . We show that under natural closure properties of C, the problem #UCQ (C) is fixed-parameter tractable if and only if the combined conjunctive queries of UCQs in C, and their contracts, have bounded treewidth. A contract of a conjunctive query is an augmented structure, taking into account how the quantified variables are connected to the free variables --- if all variables are free, then a conjunctive query is equal to its contract; in this special case the criterion for fixed-parameter tractability of #UCQ (C) thus simplifies to the combined queries having bounded treewidth. Finally, we give evidence that a closure property on C is necessary for obtaining a natural tractability criterion: We show that even for a single UCQ Ψ, the meta problem of deciding whether #UCQ (Ψ) can be solved in time O(|D| d ) is NP-hard for any fixed d ≥ 1. Moreover, we prove that a known exponential-time algorithm for solving the meta problem is optimal under assumptions from fine-grained complexity theory. As a corollary of our reduction, we also establish that approximating the Weisfeiler-Leman-Dimension of a UCQ is NP-hard.
- 12 March 2024
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 53 (2) , 189-220
Counting Small Induced Subgraphs with Hereditary Properties
We study the computational complexity of the problem [Formula: see text] of counting [Formula: see text]-vertex induced subgraphs of a graph [Formula: see text] that satisfy a graph property [Formula: see text]. 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 [Formula: see text] is true for all graphs, or if it is true only for finitely many graphs, then [Formula: see text] is solvable in polynomial time. Otherwise, [Formula: see text] is [Formula: see text]-complete when parameterized by [Formula: see text], and, assuming ETH, it cannot be solved in time [Formula: see text] for any function [Formula: see text]. This classification features a wide range of properties for which the corresponding detection problem (as classified by Khot and Raman [ Theoret. Comput. Sci., 289 (2002), pp. 997–1008]) 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 an additional result, we also present an exhaustive and explicit parameterized 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 generalize some of the earlier results on this problem. For instance, our results fully subsume and strengthen the existing classification of [Formula: see text] for monotone (subgraph-closed) properties due to Roth, Schmitt, and Wellnitz [ SIAM J. Comput., (2022), pp. FOCS20-139–FOCS20-174].
- 12 March 2024
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 53 (2) , 189-220
Counting Small Induced Subgraphs with Hereditary Properties
We study the computational complexity of the problem [Formula: see text] of counting [Formula: see text]-vertex induced subgraphs of a graph [Formula: see text] that satisfy a graph property [Formula: see text]. 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 [Formula: see text] is true for all graphs, or if it is true only for finitely many graphs, then [Formula: see text] is solvable in polynomial time. Otherwise, [Formula: see text] is [Formula: see text]-complete when parameterized by [Formula: see text], and, assuming ETH, it cannot be solved in time [Formula: see text] for any function [Formula: see text]. This classification features a wide range of properties for which the corresponding detection problem (as classified by Khot and Raman [ Theoret. Comput. Sci., 289 (2002), pp. 997–1008]) 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 an additional result, we also present an exhaustive and explicit parameterized 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 generalize some of the earlier results on this problem. For instance, our results fully subsume and strengthen the existing classification of [Formula: see text] for monotone (subgraph-closed) properties due to Roth, Schmitt, and Wellnitz [ SIAM J. Comput., (2022), pp. FOCS20-139–FOCS20-174].
- 26 April 2023
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 37 (2) , 405-486
Parameterized Counting and Cayley Graph Expanders
Given a graph property [Formula: see text], we consider the problem [Formula: see text] EdgeSub [Formula: see text], where the input is a pair of a graph [Formula: see text] and a positive integer [Formula: see text], and the task is to compute the number of [Formula: see text]-edge subgraphs in [Formula: see text] that satisfy [Formula: see text]. Specifically, we study the parameterized complexity of [Formula: see text] EdgeSub [Formula: see text] with respect to both approximate and exact counting, as well as its decision version EdgeSub [Formula: see text]. Among others, our main result fully resolves the case of minor-closed properties [Formula: see text]: the decision problem EdgeSub [Formula: see text] always admits a fixed-parameter tractable algorithm, and the counting problem [Formula: see text] EdgeSub [Formula: see text] always admits a fixed-parameter tractable randomized approximation scheme. For exact counting, we present an exhaustive and explicit criterion on the property [Formula: see text] which, if satisfied, yields fixed-parameter tractability and otherwise [Formula: see text]-hardness. Additionally, our hardness results come with an almost tight conditional lower bound under the exponential time hypothesis. Our main technical result concerns the exact counting problem: Building upon the breakthrough result of Curticapean, Dell, and Marx (Symposium on Theory of Computing 2017), we express the number of subgraphs satisfying [Formula: see text] 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 [Formula: see text]-groups, which might be of independent interest. The properties of those expanders allow us to analyze the coefficients in the aforementioned linear combinations over the field [Formula: see text] which gives us significantly more control over the cancelation behavior of the coefficients.
- 26 April 2023
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 37 (2) , 405-486
Parameterized Counting and Cayley Graph Expanders
Given a graph property [Formula: see text], we consider the problem [Formula: see text] EdgeSub [Formula: see text], where the input is a pair of a graph [Formula: see text] and a positive integer [Formula: see text], and the task is to compute the number of [Formula: see text]-edge subgraphs in [Formula: see text] that satisfy [Formula: see text]. Specifically, we study the parameterized complexity of [Formula: see text] EdgeSub [Formula: see text] with respect to both approximate and exact counting, as well as its decision version EdgeSub [Formula: see text]. Among others, our main result fully resolves the case of minor-closed properties [Formula: see text]: the decision problem EdgeSub [Formula: see text] always admits a fixed-parameter tractable algorithm, and the counting problem [Formula: see text] EdgeSub [Formula: see text] always admits a fixed-parameter tractable randomized approximation scheme. For exact counting, we present an exhaustive and explicit criterion on the property [Formula: see text] which, if satisfied, yields fixed-parameter tractability and otherwise [Formula: see text]-hardness. Additionally, our hardness results come with an almost tight conditional lower bound under the exponential time hypothesis. Our main technical result concerns the exact counting problem: Building upon the breakthrough result of Curticapean, Dell, and Marx (Symposium on Theory of Computing 2017), we express the number of subgraphs satisfying [Formula: see text] 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 [Formula: see text]-groups, which might be of independent interest. The properties of those expanders allow us to analyze the coefficients in the aforementioned linear combinations over the field [Formula: see text] which gives us significantly more control over the cancelation behavior of the coefficients.
- Open Access
The Complexity of Pattern Counting in Directed Graphs, Parameterised by the Outdegree
We study the fixed-parameter tractability of the following fundamental problem: given two directed graphs $\vec H$ and $\vec G$, count the number of copies of $\vec H$ in $\vec G$. The standard setting, where the tractability is well understood, uses only $|\vec H|$ as a parameter. In this paper we take a step forward, and adopt as a parameter $|\vec H|+d(\vec G)$, where $d(\vec G)$ is the maximum outdegree of $|\vec G|$. Under this parameterization, 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 $\rho^*$ and the source number $\alpha_s$. On the one hand we give algorithms with running time $f(|\vec H|,d(\vec G)) \cdot |\vec G|^{\rho^*\!(\vec H)+O(1)}$ and $f(|\vec H|,d(\vec G)) \cdot |\vec G|^{\alpha_s(\vec H)+O(1)}$ for counting respectively the copies and induced copies of $\vec H$ in $\vec G$; on the other hand we show that, unless the Exponential Time Hypothesis fails, for any class $\vec C$ of directed graphs the (induced) counting problem is fixed-parameter tractable if and only if $\rho^*(\vec C)$ ($\alpha_s(\vec C)$) is bounded. 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, Nishizeki SICOMP 85; Bressan Algorithmica 21) are optimal unless ETH fails.Open AccessThe Complexity of Pattern Counting in Directed Graphs, Parameterised by the Outdegree
We study the fixed-parameter tractability of the following fundamental problem: given two directed graphs $\vec H$ and $\vec G$, count the number of copies of $\vec H$ in $\vec G$. The standard setting, where the tractability is well understood, uses only $|\vec H|$ as a parameter. In this paper we take a step forward, and adopt as a parameter $|\vec H|+d(\vec G)$, where $d(\vec G)$ is the maximum outdegree of $|\vec G|$. Under this parameterization, 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 $\rho^*$ and the source number $\alpha_s$. On the one hand we give algorithms with running time $f(|\vec H|,d(\vec G)) \cdot |\vec G|^{\rho^*\!(\vec H)+O(1)}$ and $f(|\vec H|,d(\vec G)) \cdot |\vec G|^{\alpha_s(\vec H)+O(1)}$ for counting respectively the copies and induced copies of $\vec H$ in $\vec G$; on the other hand we show that, unless the Exponential Time Hypothesis fails, for any class $\vec C$ of directed graphs the (induced) counting problem is fixed-parameter tractable if and only if $\rho^*(\vec C)$ ($\alpha_s(\vec C)$) is bounded. 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, Nishizeki SICOMP 85; Bressan Algorithmica 21) are optimal unless ETH fails.