### Tractable Hypergraph Properties for Constraint Satisfaction and Conjunctive QueriesTractable Hypergraph Properties for Constraint Satisfaction and Conjunctive Queries

Access Restriction
Subscribed

 Author Marx, Dniel Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2013 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Constraint satisfaction ♦ Fractional edge covers ♦ Hypergraphs ♦ Hypertree width Abstract An important question in the study of constraint satisfaction problems (CSP) is understanding how the graph or hypergraph describing the incidence structure of the constraints influences the complexity of the problem. For binary CSP instances (that is, where each constraint involves only two variables), the situation is well understood: the complexity of the problem essentially depends on the treewidth of the graph of the constraints [Grohe 2007; Marx 2010b]. However, this is not the correct answer if constraints with unbounded number of variables are allowed, and in particular, for CSP instances arising from query evaluation problems in database theory. Formally, if $\textit{H}$ is a class of hypergraphs, then let $CSP(\textit{H})$ be CSP restricted to instances whose hypergraph is in $\textit{H}.$ Our goal is to characterize those classes of hypergraphs for which $CSP(\textit{H})$ is polynomial-time solvable or fixed-parameter tractable, parameterized by the number of variables. Note that in the applications related to database query evaluation, we usually assume that the number of variables is much smaller than the size of the instance, thus parameterization by the number of variables is a meaningful question. The most general known property of $\textit{H}$ that makes $CSP(\textit{H})$ polynomial-time solvable is bounded fractional hypertree width. Here we introduce a new hypergraph measure called submodular width, and show that bounded submodular width of $\textit{H}$ (which is a strictly more general property than bounded fractional hypertree width) implies that $CSP(\textit{H})$ is fixed-parameter tractable. In a matching hardness result, we show that if $\textit{H}$ has unbounded submodular width, then $CSP(\textit{H})$ is not fixed-parameter tractable (and hence not polynomial-time solvable), unless the Exponential Time Hypothesis (ETH) fails. The algorithmic result uses tree decompositions in a novel way: instead of using a single decomposition depending on the hypergraph, the instance is split into a set of instances (all on the same set of variables as the original instance), and then the new instances are solved by choosing a different tree decomposition for each of them. The reason why this strategy works is that the splitting can be done in such a way that the new instances are “uniform” with respect to the number extensions of partial solutions, and therefore the number of partial solutions can be described by a submodular function. For the hardness result, we prove via a series of combinatorial results that if a hypergraph $\textit{H}$ has large submodular width, then a 3SAT instance can be efficiently simulated by a CSP instance whose hypergraph is $\textit{H}.$ To prove these combinatorial results, we need to develop a theory of (multicommodity) flows on hypergraphs and vertex separators in the case when the function $\textit{b}(\textit{S})$ defining the cost of separator $\textit{S}$ is submodular, which can be of independent interest. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2013-11-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 60 Issue Number 6 Page Count 51 Starting Page 1 Ending Page 51

#### Open content in new tab

Source: ACM Digital Library