Thumbnail
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

   Open content in new tab
Source: ACM Digital Library