Abstract The Multicut problem asks for a minimum cut separating certain pairs of vertices: formally, given a graph G and a demand graph H on a set $$T\subseteq V(G)$$ T ⊆ V ( G ) of terminals, the task is to find a minimum-weight set C of edges of G such that whenever two vertices of T are adjacent in H , they are in different components of $$G\setminus C$$ G \ C . Colin de Verdière [ Algorithmica, 2017] showed that Multicut with t terminals on a graph G of genus g can be solved in time $$f(t,g)n^{O(\sqrt{g^2+gt+t})}$$ f ( t , g ) n O ( g 2 + g t + t ) . Cohen-Addad et al. [ JACM , 2021] proved a matching lower bound showing that the exponent of n is essentially best possible (for every fixed value of t and g ), even in the special case of Multiway Cut , where the demand graph H is a complete graph. However, this lower bound tells us nothing about other special cases of Multicut such as Group 3-Terminal Cut (where three groups of terminals need to be separated from each other). We show that if the demand pattern is, in some sense, close to being a complete bipartite graph, then Multicut can be solved faster than $$f(t,g)n^{O(\sqrt{g^2+gt+t})}$$ f ( t , g ) n O ( g 2 + g t + t ) , and furthermore this is the only property that allows such an improvement. Formally, for a class $$\mathcal {H}$$ H of graphs, $$\textsc {Multicut}(\mathcal {H})$$ M U L T I C U T ( H ) is the special case where the demand graph H is in $$\mathcal {H}$$ H . For every fixed class $$\mathcal {H}$$ H

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).

We investigate how efficiently a well-studied family of domination-type problems can be solved on bounded-treewidth graphs. For sets \(\sigma,\rho\) of non-negative integers, a \((\sigma,\rho)\) -set of a graph G is a set S of vertices such that \(|N(u)\cap S|\in\sigma\) for every \(u\in S\) , and \(|N(\!\textit{v})\cap S|\in\rho\) for every \(\textit{v}\not\in S\) . The problem of finding a \((\sigma,\rho)\) -set (of a certain size) unifies standard problems, such as Independent Set , Dominating Set , Independent Dominating Set , and many others. For all pairs of finite or cofinite sets \((\sigma,\rho)\) , we determine (under standard complexity assumptions) the best possible value \(c_{\sigma,\rho}\) such that there is an algorithm that counts \((\sigma,\rho)\) -sets in time \(c_{\sigma,\rho}^{\textsf{tw}}\cdot n^{O(1)}\) (if a tree decomposition of width \(\textsf{tw}\) is given in the input). Let \(s_{{\rm top}}\) denote the largest element of \(\sigma\) if \(\sigma\) is finite, or the largest missing integer \(+1\) if \(\sigma\) is cofinite; \(r_{{\rm top}}\) is defined analogously for \(\rho\) . Surprisingly, \(c_{\sigma,\rho}\) is often significantly smaller than the natural bound \(s_{{\rm top}}+r_{{\rm top}}+2\) achieved by existing algorithms. Toward defining \(c_{\sigma,\rho}\) , we say that \((\sigma,\rho)\) is \({\mathrm{m}}\) -structured if there is a pair \((\alpha,\beta)\) such that every integer in \(\sigma\) equals \(\alpha\) mod \({\mathrm{m}}\) , and every integer in \(\rho\) equals \(\beta\) mod \({\mathrm{m}}\) . Then, setting — \(c_{\sigma,\rho}=s_{{\rm top}}+r_{{\rm top}}+2\) if \((\sigma,\rho)\) is not \({\mathrm{m}}\) -structured for any \({\mathrm{m}}\geq 2\) , — \(c_{\sigma,\rho}=\max\{s_{{\rm top}},r_{{\rm top}}\}+2\) if \((\sigma,\rho)\) is 2-structured, but not \({\mathrm{m}}\) -structured for any \({\mathrm{m}}\geq 3\) , and

The Multicut problem asks for a minimum cut separating certain pairs of vertices: formally, given a graph G and demand graph H on a set T\subseteq V(G) of terminals, the task is to find a minimum-weight set C of edges of G such that whenever two vertices of T are adjacent in H, they are in different components of G\setminus C. Colin de Verdière [Algorithmica, 2017] showed that Multicut with t terminals on a graph G of genus g can be solved in time f(t,g)n^{O(\sqrt{g^2+gt+t})}. Cohen-Addad et al. [JACM, 2021] proved a matching lower bound showing that the exponent of n is essentially best possible (for fixed values of t and g), even in the special case of Multiway Cut, where the demand graph H is a complete graph. However, this lower bound tells us nothing about other special cases of Multicut such as Group 3-Terminal Cut. We show that if the demand pattern is, in some sense, close to being a complete bipartite graph, then Multicut can be solved faster than f(t,g)n^{O(\sqrt{g^2+gt+t})}, and furthermore this is the only property that allows such an improvement. Formally, for a class \mathcal{H} of graphs, Multicut(\mathcal{H}) is the special case where the demand graph H is in \mathcal{H}. For every fixed class \mathcal{H} (satisfying some mild closure property), fixed g, and fixed t, our main result gives tight upper and lower bounds on the exponent of n in algorithms solving Multicut(\mathcal{H}). In addition, we investigate a similar setting where, instead of parameterizing by the genus g of G, we parameterize by the minimum number k of edges of G that need to be deleted to obtain a planar graph. Interestingly, in this setting it makes a significant difference whether the graph G is weighted or unweighted: further nontrivial algorithmic techniques give substantial improvements in the unweighted case.

The goal of this paper is to investigate a family of optimization problems arising from list homomorphisms, and to understand what the best possible algorithms are if we restrict the problem to bounded-treewidth graphs. For a fixed $H$, the input of the optimization problem LHomVD($H$) is a graph $G$ with lists $L(v)$, and the task is to find a set $X$ of vertices having minimum size such that $(G-X,L)$ has a list homomorphism to $H$. We define analogously the edge-deletion variant LHomED($H$). This expressive family of problems includes members that are essentially equivalent to fundamental problems such as Vertex Cover, Max Cut, Odd Cycle Transversal, and Edge/Vertex Multiway Cut. For both variants, we first characterize those graphs $H$ that make the problem polynomial-time solvable and show that the problem is NP-hard for every other fixed $H$. Second, as our main result, we determine for every graph $H$ for which the problem is NP-hard, the smallest possible constant $c_H$ such that the problem can be solved in time $c^t_H\cdot n^{O(1)}$ if a tree decomposition of $G$ having width $t$ is given in the input.Let $i(H)$ be the maximum size of a set of vertices in $H$ that have pairwise incomparable neighborhoods. For the vertex-deletion variant LHomVD($H$), we show that the smallest possible constant is $i(H)+1$ for every $H$. The situation is more complex for the edge-deletion version. For every $H$, one can solve LHomED($H$) in time $i(H)^t\cdot n^{O(1)}$ if a tree decomposition of width $t$ is given. However, the existence of a specific type of decomposition of $H$ shows that there are graphs $H$ where LHomED($H$) can be solved significantly more efficiently and the best possible constant can be arbitrarily smaller than $i(H)$. Nevertheless, we determine this best possible constant and (assuming the SETH) prove tight bounds for every fixed $H$.

We study a general family of problems that form a common generalization of classic hitting (also referred to as covering or transversal) and packing problems. An instance of X-HitPack asks: Can removing k (deletable) vertices of a graph G prevent us from packing $\ell$ vertex-disjoint objects of type X? This problem captures a spectrum of problems with standard hitting and packing on opposite ends. Our main motivating question is whether the combination X-HitPack can be significantly harder than these two base problems. Already for a particular choice of X, this question can be posed for many different complexity notions, leading to a large, so-far unexplored domain in the intersection of the areas of hitting and packing problems. On a high-level, we present two case studies: (1) X being all cycles, and (2) X being all copies of a fixed graph H. In each, we explore the classical complexity, as well as the parameterized complexity with the natural parameters k+l and treewidth. We observe that the combined problem can be drastically harder than the base problems: for cycles or for H being a connected graph with at least 3 vertices, the problem is Σ_2^P-complete and requires double-exponential dependence on the treewidth of the graph (assuming the Exponential-Time Hypothesis). In contrast, the combined problem admits qualitatively similar running times as the base problems in some cases, although significant novel ideas are required. For example, for X being all cycles, we establish a 2^poly(k+l)n^O(1) algorithm using an involved branching method. Also, for X being all edges (i.e., H = K_2; this combines Vertex Cover and Maximum Matching) the problem can be solved in time 2^\poly(tw)n^O(1) on graphs of treewidth tw. The key step enabling this running time relies on a combinatorial bound obtained from an algebraic (linear delta-matroid) representation of possible matchings.

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.

Abstract. 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].

The goal of this work is to give precise bounds on the counting complexity of a family of generalized coloring problems (list homomorphisms) on bounded-treewidth graphs. Given graphs G , H , and lists L (v) ⊆ V(H) for every v ∈ V(G) , a f:V(G) → V(H) that preserves the edges (i.e., uv ∈ E(G) implies f(u)f(v) ∈ E(H) ) and respects the lists (i.e., f(v) ∈ L(v) ). Standard techniques show that if G is given with a tree decomposition of width t , then the number of list homomorphisms can be counted in time |V(H)| t ⋅ n 𝒪(1) . Our main result is determining, for every fixed graph H , how much the base |V(H)| in the running time can be improved. For a connected graph H , we define irr( H ) in the following way: if H has a loop or is nonbipartite, then irr( H ) is the maximum size of a set S⊆ V(H) where any two vertices have different neighborhoods; if H is bipartite, then irr( H ) is the maximum size of such a set that is fully in one of the bipartition classes. For disconnected H , we define irr( H ) as the maximum of irr( C ) over every connected component C of H . It follows from earlier results that if irr( H )=1, then the problem of counting list homomorphisms to H is polynomial-time solvable, and otherwise it is #P-hard. We show that, for every fixed graph H , the number of list homomorphisms from (G,L) to H — can be counted in time \(\operatorname{irr}(H)^t\cdot n^{\mathcal {O}(1)}\) if a tree decomposition of G having width at most t is given in the input, and, — given that \(\operatorname{irr}(H)\ge 2\) , cannot be counted in time \((\operatorname{irr}(H)-\varepsilon)^t\cdot n^{\mathcal {O}(1)}\) for any \(\varepsilon \gt 0\) , even if a tree decomposition of G having width at most t is given in the input, unless the Counting Strong Exponential-Time Hypothesis (#SETH) fails. Thereby, we give a precise and complete complexity classification featuring matching upper and lower bounds for all target graphs with or without loops.

We investigate how efficiently a well-studied family of domination-type problems can be solved on bounded-treewidth graphs. For sets σ, ρ of non-negative integers, a (σ, ρ)-set of a graph G is a set S of vertices such that | N (u) ∩ S| ∈ σ for every u ∈ S, and | N (v) ∩ S| ∈ ρ for every v ∉ S. The problem of finding a (σ, ρ)-set (of a certain size) unifies standard problems such as INDEPENDENT SET, DOMINATING SET, INDEPENDENT DOMINATING SET, and many others. For all pairs of finite or cofinite sets (σ, ρ), we determine (under standard complexity assumptions) the best possible value cσ,ρ such that there is an algorithm that counts (σ, ρ)-sets in time ctwσ,ρ · nO(1) (if a tree decomposition of width tw is given in the input). Let stop denote the largest element of σ if σ is finite, or the largest missing integer +1 if σ is cofinite; rtop is defined analogously for ρ. Surprisingly, cσ,ρ is often significantly smaller than the natural bound stop + rtop + 2 achieved by existing algorithms [van Rooij, 2020]. Toward defining cσ,ρ, we say that (σ,ρ) is m-structured if there is a pair (α,β) such that every integer in σ equals α mod m, and every integer in ρ equals β mod m. Then, setting • cσ,ρ = stop + rtop +2 if (σ, ρ) is not m-structured for any m ≥ 2 • cσ,ρ = max{stop,rtop} + 2 if (σ,ρ) is 2-structured, but not m-structured for any m ≥ 3, and stop = rtop is even, and • cσ,ρ = max{stop, rtop} + 1, otherwise we provide algorithms counting (σ, ρ)-sets in time ctwσ,ρ · nO(1). For example, for the EXACT INDEPENDENT DOMINATING SET problem (also known as PERFECT CODE) corresponding to σ = {0} and ρ = {1}, this improves the 3tw · nO(1) algorithm of van Rooij to 2tw· nO(1). Despite the unusually delicate definition of cσ,ρ, we show that our algorithms are most likely optimal, i.e., for any pair (σ, ρ) of finite or cofinite sets where the problem is non-trivial, and any ε > 0, a (cσ,ρ — ε)tw · nO(1)- algorithm counting the number of (σ, ρ)-sets would violate the COUNTING STRONG EXPONENTIAL-TIME HYPOTHESIS (#SETH). For finite sets σ and ρ, our lower bounds also extend to the decision version, showing that our algorithms are optimal in this setting as well. In contrast, for many cofinite sets, we show that further significant improvements for the decision and optimization versions are possible using the technique of representative sets. * The full version of this work can be accessed at https://arxiv.org/abs/2211.04278. Research supported by the European Research Council (ERC) consolidator grant No. 725978 SYSTEMATICGRAPH.

We study the complexity of approximating the number of answers to a small query φ in a large database D. We establish an exhaustive classification into tractable and intractable cases if φ is a conjunctive query possibly including disequalities and negations: - If there is a constant bound on the arity of φ, 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 φ is bounded. - If the arity is unbounded and φ does not have negations, then the problem has an FPTRAS if and only if the adaptive width of φ (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 NP=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).

The goal of this work is to give precise bounds on the counting complexity of a family of generalized coloring problems (list homomorphisms) on bounded-treewidth graphs. Given graphs G, H, and lists L(v) ⊆ V(H) for every v ∊ V(G), a list homomorphism is a function f : V(G) → V(H) that preserves the edges (i.e., uv ∊ E(G) implies f(u)f(v) ∊ E(H)) and respects the lists (i.e., f(v) ∊ L(v)). Standard techniques show that if G is given with a tree decomposition of width t, then the number of list homomorphisms can be counted in time . Our main result is determining, for every fixed graph H, how much the base |V(H)| in the running time can be improved. For a connected graph H we define irr(H) in the following way: if H has a loop or is nonbipartite, then irr(H) is the maximum size of a set S ⊆ V(H) where any two vertices have different neighborhoods; if H is bipartite, then irr(H) is the maximum size of such a set that is fully in one of the bipartition classes. For disconnected H, we define irr(H) as the maximum of irr(C) over every connected component C of H. It follows from earlier results that if irr(H) = 1, then the problem of counting list homomorphisms to H is polynomial-time solvable, and otherwise it is #P-hard. We show that, for every fixed graph H, the number of list homomorphisms from (G, L) to H can be counted in time if a tree decomposition of G having width at most t is given in the input, and given that irr(H) ≥ 2, cannot be counted in time for any ∊ > 0, even if a tree decomposition of G having width at most t is given in the input, unless the Counting Strong Exponential-Time Hypothesis (#SETH) fails. Thereby we give a precise and complete complexity classification featuring matching upper and lower bounds for all target graphs with or without loops.

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.

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.

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 [ Theory Comput., 11 (2015), pp. 35--57] 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 $\oplus{P}$ of parity problems. We verify their conjecture for all graphs $H$ that exclude the complete graph on four vertices as a minor. Further, we rule out the existence of a subexponential-time algorithm for the $\oplus{P}$-complete cases, assuming the randomized 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 toward resolving the conjecture (Faben and Jerrum [ Theory Comput., 11 (2015), pp. 35--57]; Göbel, Goldberg, and Richerby [ ACM Trans. Comput. Theory, 6 (2014), 17; ACM Trans. Comput. Theory, 8 (2016), 12]). 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 retraction is a homomorphism from a graph G to an induced subgraph H of G that is the identity on H . In a long line of research, retractions have been studied under various algorithmic settings. Recently, the problem of approximately counting retractions was considered. We give a complete trichotomy for the complexity of approximately counting retractions to all square-free graphs (graphs that do not contain a cycle of length 4). It turns out there is a rich and interesting class of graphs for which this problem is complete in the class #BIS. As retractions generalise homomorphisms, our easiness results extend to the important problem of approximately counting homomorphisms. By giving new #BIS-easiness results, we now settle the complexity of approximately counting homomorphisms for a whole class of non-trivial graphs that were previously unresolved.

Let G be a graph that contains an induced subgraph H. A retraction from G to H is a homomorphism from G to H that is the identity function on H. Retractions are very well-studied: Given H, the complexity of deciding whether there is a retraction from an input graph G to H is completely classified, in the sense that it is known for which H this problem is tractable (assuming P ≠ NP). Similarly, the complexity of (exactly) counting retractions from G to H is classified (assuming FP ≠ #P). However, almost nothing is known about approximately counting retractions. Our first contribution is to give a complete trichotomy for approximately counting retractions to trees. The result is as follows: (1) Approximately counting retractions to a tree H is in FP if H is a star, a single looped vertex, or an edge with two loops. (2) Otherwise, if H is an irreflexive caterpillar or a partially bristled reflexive path, then approximately counting retractions to H is equivalent to approximately counting the independent sets of a bipartite graph — a problem which is complete in the approximate counting complexity class RHπ1. (3) Finally, if none of these hold, then approximately counting retractions to H is #P-complete under approximation-preserving reductions. Our second contribution is to locate the retraction counting problem in the complexity landscape of related approximate counting problems. Interestingly, our results are in contrast to the situation in the exact counting context. We show that the problem of approximately counting retractions is separated both from the problem of approximately counting homomorphisms and from the problem of approximately counting list homomorphisms — whereas for exact counting all three of these problems are interreducible. We also show that the number of retractions is at least as hard to approximate as both the number of surjective homomorphisms and the number of compactions. In contrast, exactly counting compactions is the hardest of these problems. The full version containing detailed proofs is available at https://arxiv.org/abs/1807.00590v1 (version from 2 July 2018). The theorem numbering here matches the full version.

A homomorphism from a graph $G$ to a graph $H$ is a function from the vertices of $G$ to the vertices of $H$ that preserves edges. A homomorphism is surjective if it uses all of the vertices of $H$, and it is a compaction if it uses all of the vertices of $H$ and all of the nonloop edges of $H$. Hell and Nešetřil gave a complete characterization of the complexity of deciding whether there is a homomorphism from an input graph $G$ to a fixed graph $H$. A complete characterization is not known for surjective homomorphisms or for compactions, though there are many interesting results. Dyer and Greenhill gave a complete characterization of the complexity of counting homomorphisms from an input graph $G$ to a fixed graph $H$. In this paper, we give a complete characterization of the complexity of counting surjective homomorphisms from an input graph $G$ to a fixed graph $H$, and we also give a complete characterization of the complexity of counting compactions from an input graph $G$ to a fixed graph $H$. In an addendum we use our characterizations to point out a dichotomy for the complexity of the respective approximate counting problems (in the connected case).

A homomorphism from a graph G to a graph H is a function from the vertices of G to the vertices of H that preserves edges. A homomorphism is surjective if it uses all of the vertices of H and it is a compaction if it uses all of the vertices of H and all of the non-loop edges of H. Hell and Nešetřil gave a complete characterisation of the complexity of deciding whether there is a homomorphism from an input graph G to a fixed graph H. A complete characterisation is not known for surjective homomorphisms or for compactions, though there are many interesting results. Dyer and Greenhill gave a complete characterisation of the complexity of counting homomorphisms from an input graph G to a fixed graph H. In this paper, we give a complete characterisation of the complexity of counting surjective homomorphisms from an input graph G to a fixed graph H and we also give a complete characterisation of the complexity of counting compactions from an input graph G to a fixed graph H.

We consider the minimum spanning tree (MST) problem in an uncertainty model where uncertain edge weights can be explored at extra cost. The task is to find an MST by querying a minimum number of edges for their exact weight. This problem has received quite some attention from the algorithms theory community. In this paper, we conduct the first practical experiments for MST under uncertainty, theoretically compare three known algorithms, and compare theoretical with practical behavior of the algorithms. Among others, we observe that the average performance and the absolute number of queries are both far from the theoretical worst-case bounds. Furthermore, we investigate a known general preprocessing procedure and develop an implementation thereof that maximally reduces the data uncertainty. We also characterize a class of instances that is solved completely by our preprocessing. Our experiments are based on practical data from an application in telecommunications and uncertainty instances generated from the standard TSPLib graph library.