Search

A classic result due to Schaefer (1978) classifies all constraint satisfaction problems (CSPs) over the Boolean domain as being either in P or NP-hard. This paper considers a promise-problem variant of CSPs called PCSPs. A PCSP over a finite set of pairs of constraints Γ consists of a pair (ΨP,ΨQ) of CSPs with the same set of variables such that for every (P,Q)∈Γ, P(xi1,...,xik) is a clause of ΨP if and only if Q(xi1,...,xik) is a clause of ΨQ. The promise problem PCSP(Γ) is to distinguish, given (ΨP,ΨQ), between the cases ΨP is satisfiable and ΨQ is unsatisfiable. Many natural problems including approximate graph and hypergraph coloring can be placed in this framework. This paper is motivated by the pursuit of understanding the computational complexity of Boolean promise CSPs. As our main result, we show that PCSP(Γ) exhibits a dichotomy (it is either polynomial time solvable or NP-hard) when the relations in Γ are symmetric and allow for negations of variables. We achieve our dichotomy theorem by extending the weak polymorphism framework of Austrin, Guruswami, and Håstad [FOCS '14] which itself is a generalization of the algebraic approach to study CSPs. In both the algorithm and hardness portions of our proof, we incorporate new ideas and techniques not utilized in the CSP case. Furthermore, we show that the computational complexity of any promise CSP (over arbitrary finite domains) is captured entirely by its weak polymorphisms, a feature known as Galois correspondence, as well as give necessary and sufficient conditions for the structure of this set of weak polymorphisms. Such insights call us to question the existence of a general dichotomy for Boolean PCSPs case. [ABSTRACT FROM AUTHOR]

The approximate graph coloring problem, whose complexity is unresolved in most cases, concerns finding a c-coloring of a graph that is promised to be k-colorable, where c\geq k. This problem naturally generalizes to promise graph homomorphism problems and further to promise constraint satisfaction problems. The complexity of these problems has recently been studied through an algebraic approach. In this paper, we introduce two new techniques to analyze the complexity of promise CSPs: one is based on topology and the other on adjunction. We apply these techniques, together with the previously introduced algebraic approach, to obtain new unconditional NP-hardness results for a significant class of approximate graph coloring and promise graph homomorphism problems. [ABSTRACT FROM AUTHOR]

In this paper, we design efficient algorithms to approximately count the number of edges of a given k-hypergraph, and to sample an approximately uniform random edge. The hypergraph is not given explicitly and can be accessed only through its colorful independence oracle: The colorful independence oracle returns yes or no depending on whether a given subset of the vertices contains an edge that is colorful with respect to a given vertex-coloring. Our results extend and/or strengthen recent results in the graph oracle literature due to Beame et al. [ACM Trans. Algorithms, 16 (2020), 52], Dell and Lapinskas [Proceedings of STOC, ACM, 2018, pp. 281-288], and Bhattacharya et al. [Proceedings of ISAAC, 2019]. Our results have consequences for approximate counting/sampling: We can turn certain kinds of decision algorithms into approximate counting/sampling algorithms without causing much overhead in the running time. We apply this approximate counting/sampling-to-decision reduction to key problems in fine-grained complexity (such as k-SUM, k-OV, and weighted k-Clique) and parameterized complexity (such as induced subgraphs of size k or weight-k solutions to constraint satisfaction problems). [ABSTRACT FROM AUTHOR]

The characterization of all the constraint satisfaction problems solvable by local consistency checking (also known as CSPs of bounded width) was proposed by Feder and Vardi [SIAM J. Comput., 28 (1998), pp. 57104]. It was confirmed by two independent proofs by Bulatov [Bounded Relational Width, manuscript, 2009] and Barto and Kozik [L. Barto and M. Kozik, 50th Annual IEEE Symposium on Foundations of Computer Science, 2009, pp. 595 603], [L. Barto and M. Kozik, J. ACM, 61 (2014), 3]. Later Barto [J. Logic Comput., 26 (2014), pp. 923 943] proved a collapse of the hierarchy of local consistency notions by showing that (2; 3) minimality solves all the CSPs of bounded width. In this paper we present a new consistency notion, jpq consistency, which also solves all the CSPs of bounded width. Our notion is strictly weaker than (2; 3) consistency, (2; 3) minimality, path consistency, and singleton arc consistency (SAC). This last fact allows us to answer the question of Chen, Dalmau, and Gruien [J. Logic Comput., 23 (2013), pp. 87 108] by confirming that SAC solves all the CSPs of bounded width. Moreover, as known algorithms work faster for SAC, the result implies that CSPs of bounded width can be, in practice, solved more efficiently. The definition of jpq consistency is closely related to a consistency condition obtained from the rounding of an SDP relaxation of a CSP instance. In fact, the main result of this paper is used by Dalmau et al. [Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, ACM, New York, 2017, pp. 340{357] to show that CSPs with near unanimity polymorphisms admit robust approximation algorithms with polynomial loss. Finally, an algebraic characterization of some term conditions satisfied in algebras associated with templates of bounded width, first proved by Brady, is a direct consequence of our result. [ABSTRACT FROM AUTHOR]

Answering conjunctive queries is a fundamental problem in database theory, and it is equivalent to solving constraint satisfaction problems in artificial intelligence and to other fundamental problems arising in computer science, which can be recast in terms of looking for homomorphisms between relational structures. The problem is NP-hard, so that several research e orts have been made in the literature for identifying tractable classes, known as islands of tractability, as well as for devising clever heuristics for solving efficiently real-world instances. Many heuristic approaches are based on enforcing on the given instance a property called local consistency (also, relational arc-consistency), where each tuple in every query atom matches at least one tuple in every other query atom. Interestingly, for many well-known classes of instances, such as for the acyclic ones, enforcing local consistency is even sufficient to solve the given instance correctly. However, the precise power of such a procedure was unclear, but for some very restricted cases. The paper provides answers to long-standing questions about the precise power of algorithms based on enforcing local consistency. The paper deals with both the general framework of tree projections, where local consistency is enforced among arbitrary views defined over the given database instance, and the specific cases where such views are computed according to the so-called structural decomposition methods, such as generalized hypertree width, component hypertree decompositions, and so on. Moreover, the paper deals with both decision and computation problems, by characterizing those tuples that are correct projections of query answers, which finds application in algorithms for answering queries and solving constraint satisfaction problems. As a relevant special case, the power of algorithms based on enforcing local consistency is characterized over the fundamental and deeply studied class of acyclic conjunctive queries. It turns out that local consistency provides the correct answer to a Boolean acyclic query if, and only if, the query is semantically acyclic. [ABSTRACT FROM AUTHOR]

An instance of the constraint satisfaction problem (CSP) is given by a family of constraints on overlapping sets of variables, and the goal is to assign values from a fixed domain to the variables so that all constraints are satisfied. In the optimization version, the goal is to maximize the number of satisfied constraints. An approximation algorithm for a CSP is called robust if it outputs an assignment satisfying an (1 - g(ε))-fraction of constraints on any (1 - ε )- satisfiable instance, where the loss function g is such that g(ε ) \rightarrow 0 as ε \rightarrow 0. We study how the robust approximability of CSPs depends on the set of constraint relations allowed in instances, the so-called constraint language. All constraint languages admitting a robust polynomial-time algorithm (with some g) have been characterized by Barto and Kozik, with the general bound on the loss g being doubly exponential, specifically g(ε ) = O((log log(1/ε ))/ log(1/ε)). It is natural to ask when a better loss can be achieved, in particular polynomial loss g(ε ) = O(ε 1/k) for some constant k. In this paper, we consider CSPs with a constraint language having a near-unanimity polymorphism. This general condition almost matches a known necessary condition for having a robust algorithm with polynomial loss. We give two randomized robust algorithms with polynomial loss for such CSPs: one works for any near-unanimity polymorphism and the parameter k in the loss depends on the size of the domain and the arity of the relations in Γ, while the other works for a special ternary near-unanimity operation called the dual discriminator with k = 2 for any domain size. In the latter case, the CSP is a common generalization of Unique Games with a fixed domain and 2-Sat. In the former case, we use the algebraic approach to the CSP. Both cases use the standard semidefinite programming relaxation for the CSP [ABSTRACT FROM AUTHOR]

An algorithm for a constraint satisfaction problem is called robust if it outputs an assignment satisfying at least (1−g(ε))-fraction of the constraints given a (1−ε)-satisfiable instance, where g(ε) → 0 as ε → 0. Guruswami and Zhou conjectured a characterization of constraint languages for which the corresponding constraint satisfaction problem admits an efficient robust algorithm. This paper confirms their conjecture. [ABSTRACT FROM AUTHOR]

We propose a new algorithm for Promise Constraint Satisfaction Problems (PCSPs). It is a combination of the Constraint Basic LP relaxation and the Affine IP relaxation (CLAP). We give a characterization of the power of CLAP in terms of a minion homomorphism. Using this characterization, we identify a certain weak notion of symmetry which, if satisfied by infinitely many polymorphisms of PCSPs, guarantees tractability. We demonstrate that there are PCSPs solved by CLAP that are not solved by any of the existing algorithms for PCSPs; in particular, not by the BLP+AIP algorithm of Brakensiek et al. [SIAM J. Comput., 49 (2020), pp. 1232--1248] and not by a reduction to tractable finite-domain CSPs. [ABSTRACT FROM AUTHOR]

We study the complexity of Boolean constraint satisfaction problems (CSPs) when the assignment must have Hamming weight in some congruence class modulo M, for various choices of the modulus M. Due to the known classification of tractable Boolean CSPs, this mainly reduces to the study of three cases: \sanstwo -\sansS \sansA \sansT, \sansH \sansO \sansR \sansN -\sansS \sansA \sansT, and \sansL \sansI \sansN -\sanstwo (linear equations mod 2). We classify the moduli M for which these respective problems are polynomial time solvable, and when they are not (assuming the exponential time hypothesis). Our study reveals that this modular constraint lends a surprising richness to these classic, well-studied problems, with interesting broader connections to complexity theory and coding theory. The \sansH \sansO \sansR \sansN -\sansS \sansA \sansT case is connected to the covering complexity of polynomials representing the \sansN \sansA \sansN \sansD function mod M. The \sansL \sansI \sansN -\sanstwo case is tied to the sparsity of polynomials representing the \sansO \sansR function mod M, which in turn has connections to modular weight distribution properties of linear codes and locally decodable codes. In both cases, the analysis of our algorithm as well as the hardness reduction rely on these polynomial representations, highlighting an interesting algebraic common ground between hard cases for our algorithms and the gadgets which show hardness. These new complexity measures of polynomial representations merit further study. The inspiration for our study comes from a recent work by N\"agele, Sudakov, and Zenklusen on submodular minimization with a global congruence constraint. Our algorithm for \sansH \sansO \sansR \sansN -\sansS \sansA \sansT has strong similarities to their algorithm, and in particular identical kinds of set systems arise in both cases. Our connection to polynomial representations leads to a simpler analysis of such set systems and also sheds light on (but does not resolve) the complexity of submodular minimization with a congruency requirement modulo a composite M. [ABSTRACT FROM AUTHOR]

We produce a class of ω-categorical structures with finite signature by applying a model-theoretic construction--a refinement of the Hrushovski-encoding--to ω-categorical structures in a possibly infinite signature. We show that the encoded structures retain desirable algebraic properties of the original structures, but that the constraint satisfaction problems (CSPs) associated with these structures can be badly behaved in terms of computational complexity. This method allows us to systematically generate ω-categorical templates whose CSPs are complete for a variety of complexity classes of arbitrarily high complexity and ω-categorical templates that show that membership in any given complexity class containing AC0 cannot be expressed by a set of identities on the polymorphisms. It moreover enables us to prove that recent results about the relevance of topology on polymorphism clones of ω-categorical structures also apply for CSP templates, i.e., structures in a finite language. Finally, we obtain a concrete algebraic criterion which could constitute a description of the delineation between tractability and NP-hardness in the dichotomy conjecture for first-order reducts of finitely bounded homogeneous structures. [ABSTRACT FROM AUTHOR]

The constraint satisfaction problem (CSP) is concerned with homomorphisms between two structures. For CSPs with restricted left-hand-side structures, the results of Dalmau, Kolaitis, and Vardi [Proceedings of the 8th International Conference on Principles and Practice of Constraint Programming, Springer, New York, 2002, pp. 310--326], Grohe [J. ACM, 54 (2007), 1], and Atserias, Bulatov, and Dalmau [Proceedings of the 34th International Colloquium on Automata, Languages and Programming, Springer, New York, 2007, pp. 279--290] establish the precise borderline of polynomial-time solvability (subject to complexity-theoretic assumptions) and of solvability by bounded-consistency algorithms (unconditionally) as bounded treewidth modulo homomorphic equivalence. The general-valued constraint satisfaction problem (VCSP) is a generalization of the CSP concerned with homomorphisms between two valued structures. For VCSPs with restricted left-hand-side valued structures, we establish the precise borderline of polynomial-time solvability (subject to complexity-theoretic assumptions) and of solvability by the kth level of the Sherali--Adams LP hierarchy (unconditionally). We also obtain results on related problems concerned with finding a solution and recognizing the tractable cases; the latter has an application in database theory. [ABSTRACT FROM AUTHOR]

The logic MMSNP is a restricted fragment of existential second-order logic which can express many interesting queries in graph theory and finite model theory. The logic was introduced by Feder and Vardi, who showed that every MMSNP sentence is computationally equivalent to a finite-domain constraint satisfaction problem (CSP); the involved probabilistic reductions were derandomized by Kun using explicit constructions of expander structures. We present a new proof of the reduction to finite-domain CSPs that does not rely on the results of Kun. The new universalalgebraic proof allows us to obtain a stronger statement and to verify the more general Bodirsky--Pinsker dichotomy conjecture for CSPs in MMSNP. Our approach uses the fact that every MMSNP sentence describes a finite union of CSPs for countably infinite ѡ-categorical structures; moreover, by a recent result of Hubička and Nešetřil, these structures can be expanded to homogeneous structures with finite relational signature and the Ramsey property. [ABSTRACT FROM AUTHOR]

In the field of constraint satisfaction problems (CSPs), promise CSPs are an exciting new direction of study. In a promise CSP, each constraint comes in two forms: "strict" and "weak," and in the associated decision problem one must distinguish between being able to satisfy all the strict constraints versus not being able to satisfy all the weak constraints. The most commonly cited example of a promise CSP is the approximate graph coloring problem--which has recently seen exciting progress [Bulín, Krokhin, and Oprsal, Proceedings of the Symposium on Theory of Computing, 2019, pp. 602--613 and Wrochna and Zivny, Proceedings of the Symposium on Discrete Algorithms, 2020, pp. 1426--1435] benefiting from a systematic algebraic approach to promise CSPs based on polymorphisms," operations that map tuples in the strict form of each constraint to tuples in the corresponding weak form. In this work, we present a simple algorithm which in polynomial time solves the decision problem for all promise CSPs that admit infinitely many symmetric polymorphisms, which are invariant under arbitrary coordinate permutations. This generalizes previous work of the first two authors [Brakensiek and Guruswami, Proceedings of the Symposium on Discrete Algorithms, 2019, pp. 436--455]. We also extend this algorithm to a more general class of block-symmetric polymorphisms. As a corollary, this single algorithm solves all polynomial-time tractable Boolean CSPs simultaneously. These results give a new perspective on Schaefer's classic dichotomy theorem and shed further light on how symmetries of polymorphisms enable algorithms. Finally, we show that block symmetric polymorphisms are not only sufficient but also necessary for this algorithm to work, thus establishing its precise power. [ABSTRACT FROM AUTHOR]

For n ≥ 3, let (Hn, E) denote the nth Henson graph, i.e., the unique countable homogeneous graph with exactly those finite graphs as induced subgraphs that do not embed the complete graph on n vertices. We show that for all structures Γ with domain Hn whose relations are first-order definable in (Hn, E) the constraint satisfaction problem for Γ either is in P or is NP-complete. We moreover show a similar complexity dichotomy for all structures whose relations are first-order definable in a homogeneous graph whose reflexive closure is an equivalence relation. Together with earlier results, in particular for the random graph, this completes the complexity classification of constraint satisfaction problems of structures first-order definable in countably infinite homogeneous graphs: all such problems are either in P or NP-complete. [ABSTRACT FROM AUTHOR]

For each finite relational structure A, let CSP(\bfA) denote the CSP instances whose constraint relations are taken from A. The resulting family of problems CSP(A) has been considered heavily in a variety of computational contexts. In this article, we consider this family from the perspective of property testing: given a CSP instance and query access to an assignment, one wants to decide whether the assignment satisfies the instance or is far from doing so. While previous work on this scenario studied concrete templates or restricted classes of structures, this article presents a comprehensive classification theorem. Our main contribution is a dichotomy theorem completely characterizing the finite structures A such that CSP(A) is constant-query testable: (i) If A has a majority polymorphism and a Maltsev polymorphism, then CSP(A) is constant-query testable with one-sided error. (ii) Otherwise, testing CSP(A) requires a superconstant number of queries. [ABSTRACT FROM AUTHOR]

We investigate problems addressing combined connectivity augmentation and orientations settings. We give a polynomial-time 6-approximation algorithm for finding a minimum cost subgraph of an undirected graph G that admits an orientation covering a nonnegative crossing G-supermodular demand function, as defined by Frank [J. Comb. Theory Ser. B, 28 (1980), pp. 251-261]. An important example is (k; ℓ)-edge-connectivity, a common generalization of global and rooted edge-connectivity. Our algorithm is based on a nonstandard application of the iterative rounding method. We observe that the standard linear program with cut constraints is not amenable and use an alternative linear program with partition and copartition constraints instead. The proof requires a new type of uncrossing technique on partitions and copartitions. We also consider the problem setting when the cost of an edge can be different for the two possible orientations. The problem becomes substantially more difficult already for the simpler requirement of k-edge-connectivity. Khanna, Naor, and Shepherd [SIAM J. Discrete Math., 19 (2005), pp. 245-257] showed that the integrality gap of the natural linear program is at most 4 when k = 1 and conjectured that it is constant for all fixed k. We disprove this conjecture by showing Ω (|V |) integrality gap even when k = 2. [ABSTRACT FROM AUTHOR]

We study the problem of discrete geometric packing. Here, given weighted regions (say, in the plane) and points (with capacities), one has to pick a maximum weight subset of the regions such that no point is covered more than its capacity. We provide a general framework and an algorithm for approximating the optimal solution for packin g in hypergraphs arising out of such geometric settings. Using this framework we get a flotilla of results on this problem (and also on its dual, where one wants to pick a maximum weight subset of the points when the regions have capacities). For example, for the case of fat triangles of similar s ize, we show an O(1)-approximation and prove that no PTAS is possible. [ABSTRACT FROM AUTHOR]

We prove the following hardness result for a natural promise variant of the classical CNF-satisfiability problem: Given a CNF-formula where each clause has width ω and the guarantee that there exists an assignment satisfying at least g = [ω2]-1 literals in each clause, it is NP-hard to find a satisfying assignment to the formula (that sets at least one literal to true in each clause). On the other hand, when g = [ω2], it is easy to find a satisfying assignment via simple generalizations of the algorithms for 2-Sat. Viewing 2-SAT ∊ P as tractability of Sat when 1 in 2 literals are true in every clause, and NP-hardness of 3-Sat as intractability of Sat when 1 in 3 literals are true, our result shows, for any fixed " > 0, the difficulty of finding a satisfying assignment to instances of "(2 + ε)-SAT" where the density of satisfied literals in each clause is guaranteed to exceed 1/2+ε. We also strengthen the results to prove that, given a (2k +1)-uniform hypergraph that can be 2-colored such that each edge has perfect balance (at most k +1 vertices of either color), it is NP-hard to find a 2-coloring that avoids a monochromatic edge. In other words, a set system with discrepancy 1 is hard to distinguish from a set system with worst possible discrepancy. Finally, we prove a general result showing the intractability of promise constraint satisfaction problems based on the paucity of certain \weak polymorphisms." The core of the above hardness results is the claim that the only weak polymorphisms in these particular cases are juntas depending on few variables. [ABSTRACT FROM AUTHOR]

We give a precise algebraic characterization of the power of Sherali-Adams relaxations for solvability of valued constraint satisfaction problems (CSPs) to optimality. The condition is that of bounded width, which has already been shown to capture the power of local consistency methods for decision CSPs and the power of semidefinite programming for robust approximation of CSPs. Our characterization has several algorithmic and complexity consequences. On the algorithmic side, we show that several novel and well-known valued constraint languages are tractable via the third level of the Sherali-Adams relaxation. For the known languages, this is a significantly simpler algorithm than those previously obtained. On the complexity side, we obtain a dichotomy theorem for valued constraint languages that can express an injective unary function. This implies a simple proof of the dichotomy theorem for conservative valued constraint languages established by Kolmogorov and Živný [J. ACM, 60 (2013), 10], and also a dichotomy theorem for the exact solvability of minimum-solution problems. These are generalizations of minimum-ones problems to arbitrary finite domains. Our result improves on several previous classifications by Khanna et al. [SIAM J. Comput., 30 (2001), pp. 1863-1920], Jonsson, Kuivinen, and Nordh [SIAM J. Comput., 38 (2008), pp. 329-365], and Uppman [ABSTRACT FROM AUTHOR]

An instance of the valued constraint satisfaction problem (VCSP) is given by a finite set of variables, a finite domain of labels, and a sum of functions, each function depending on a subset of the variables. Each function can take finite values specifying costs of assignments of labels to its variables or the infinite value, which indicates an infeasible assignment. The goal is to find an assignment of labels to the variables that minimizes the sum. We study, assuming that P ≠ NP, how the complexity of this very general problem depends on the set of functions allowed in the instances, the so-called constraint language. The case when all allowed functions take values in f0;1g corresponds to ordinary CSPs, where one deals only with the feasibility issue, and there is no optimization. This case is the subject of the algebraic CSP dichotomy conjecture predicting for which constraint languages CSPs are tractable (i.e., solvable in polynomial time) and for which they are NP-hard. The case when all allowed functions take only finite values corresponds to a finite- valued CSP, where the feasibility aspect is trivial and one deals only with the optimization issue. The complexity of finite-valued CSPs was fully classified by Thapper and Živný. An algebraic necessary condition for tractability of a general-valued CSP with a fixed constraint language was recently given by Kozik and Ochremiak. As our main result, we prove that if a constraint language satisfies this algebraic necessary condition, and the feasibility CSP (i.e., the problem of deciding whether a given instance has a feasible solution) corresponding to the VCSP with this language is tractable, then the VCSP is tractable. The algorithm is a simple combination of the assumed algorithm for the feasibility CSP and the standard LP relaxation. As a corollary, we obtain that a dichotomy for ordinary CSPs would imply a dichotomy for general-valued CSPs. [ABSTRACT FROM AUTHOR]

The Unique Coverage problem, given a universe V of elements and a collection E of subsets of V , asks to find S ⊆ V to maximize the number of e ∈ E that intersects S in exactly one element. When each de ∈ E has cardinality at most k, it is also known as 1-in-k Hitting Set and admits a simple Ω( 1/ log k )-approximation algorithm. For constant k, we prove that 1-in-k Hitting Set is NP-hard to approximate within a factor O( 1/ log k ). This improves the result of Guruswami and Zhou [Theory Comput., 8 (2012), pp. 239-267], who proved the same result assuming the Unique Games Conjecture. For Unique Coverage, we prove that it is hard to approximate within a factor O( 1/log1-∊ n ) for any ∊ > 0, unless NP admits quasi-polynomial time algorithms. This improves the results of Demaine et al. [SIAM J. Comput., 38 (2008), pp. 1464-1483], including their ≈ 1/ log1/3 n inapproximability factor, which was proven under the Random 3SAT Hypothesis. Our simple proof combines ideas from two classical inapproximability results for the Set Cover and Constraint Satisfaction Problems, made efficient by various derandomization methods based on bounded independence. [ABSTRACT FROM AUTHOR]

We prove a complexity dichotomy theorem for counting constraint satisfaction problems (#CSPs) with nonnegative and algebraic weights. This caps a long series of important results on counting problems including counting unweighted and weighted graph homomorphisms and the celebrated dichotomy theorem for unweighted #CSPs. Our dichotomy theorem gives a succinct criterion for tractability. If a set F of constraint functions satisfies this criterion, then the problem #CSP(F) defined by F is solvable in polynomial time; if F does not satisfy this criterion, then the problem is #P-hard. Furthermore, we show that the question of whether a given F satisfies the criterion or not is decidable in NP. Surprisingly, our tractability criterion is simpler than the previous criteria for the more restricted classes of counting problems, although when specialized to those classes, they are logically equivalent. Our proof mainly uses linear algebra and represents a departure from universal algebra, the dominant methodology in recent years for the study of #CSPs on large domains. [ABSTRACT FROM AUTHOR]

It is known that unions of acyclic conjunctive queries (CQs) can be evaluated in linear time, as opposed to arbitrary CQs, for which the evaluation problem is NP-complete. It follows from techniques in the area of constraint-satisfaction problems that semantically acyclic unions of CQs--i.e., unions of CQs that are equivalent to a union of acyclic ones--can be evaluated in polynomial time, though testing membership in the class of semantically acyclic CQs is NP-complete. We study here the fundamental notion of semantic acyclicity in the context of graph databases and unions of conjunctive regular path queries with inverse (UC2RPQs). It is known that unions of acyclic C2RPQs can be evaluated efficiently, but it is by no means obvious whether similarly good evaluation properties hold for the class of UC2RPQs that are semantically acyclic. We prove that checking whether a UC2RPQ is semantically acyclic is Expspace-complete and obtain as a corollary that evaluation of semantically acyclic UC2RPQs is fixed-parameter tractable. In addition, our tools yield a strong theory of approximations for UC2RPQs when no equivalent acyclic UC2RPQ exists. [ABSTRACT FROM AUTHOR]

The calculation of ground-state energies of physical systems can be formalized as the k-local Hamiltonian problem, which is a natural quantum analogue of classical constraint satisfaction problems. One way of making the problem more physically meaningful is to restrict the Hamiltonian in question by picking its terms from a fixed set S and scaling them by arbitrary weights. Examples of such special cases are the Heisenberg and Ising models from condensed-matter physics. In this work we characterize the complexity of this problem for all 2-local qubit Hamiltonians. Depending on the subset S, the problem falls into one of the following categories: in P; NP-complete; polynomial-time equivalent to the Ising model with transverse magnetic fields; or QMA-complete. The third of these classes has been shown to be StoqMA-complete by Bravyi and Hastings. The characterization holds even if S does not contain any 1-local terms; for example, we prove for the first time QMA-completeness of the Heisenberg and XY interactions in this setting. If S is assumed to contain all 1-local terms, which is the setting considered by previous work, we have a characterization that goes beyond 2-local interactions: for any constant k, all k-local qubit Hamiltonians whose terms are picked from a fixed set S correspond to problems either in P; polynomial-time equivalent to the Ising model with transverse magnetic fields; or QMA-complete. These results are a quantum analogue of the maximization variant of Schaefer's dichotomy theorem for Boolean constraint satisfaction problems. [ABSTRACT FROM AUTHOR]

Let D, called the domain, be a fixed finite set and let Γ, called the valued constraint language, be a fixed set of functions of the form f : Dm → Q ∪ {∞}, where different functions might have different arity m. We study the valued constraint satisfaction problem parametrized by Γ, denoted by VCSP(Γ). These are minimization problems given by n variables and the objective function given by a sum of functions from Γ, each depending on a subset of the n variables. For example, if D = {0, 1} and Γ contains all ternary {0,∞}-valued functions, VCSP(Γ) corresponds to 3-SAT. More generally, if Γ contains only {0,∞}-valued functions, VCSP(Γ) corresponds to CSP(Γ). If D = {0, 1} and Γ contains all ternary {0, 1}-valued functions, VCSP(Γ) corresponds to Min-3-SAT, in which the goal is to minimize the number of unsatisfied clauses in a 3-CNF instance. Finite-valued constraint languages contain functions that take on only rational values and not infinite values. Our main result is a precise algebraic characterization of valued constraint languages whose instances can be solved exactly by the basic linear programming relaxation (BLP). For a valued constraint language Γ, BLP is a decision procedure for Γ if and only if Γ admits a symmetric fractional polymorphism of every arity. For a finite-valued constraint language Γ, BLP is a decision procedure if and only if Γ admits a symmetric fractional polymorphism of some arity, or equivalently, if Γ admits a symmetric fractional polymorphism of arity 2. Using these results, we obtain tractability of several novel classes of problems, including problems over valued constraint languages that are (1) submodular on arbitrary lattices; (2) k-submodular on arbitrary finite domains; (3) weakly (and hence strongly) tree submodular on arbitrary trees. [ABSTRACT FROM AUTHOR]