Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userCombining Treewidth and Backdoors for CSP
135
0
0.0
(
0
)
Added by
Robert Ganian
Publication date
2016
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We show that CSP is fixed-parameter tractable when parameterized by the treewidth of a backdoor into any tractable CSP problem over a finite constraint language. This result combines the two prominent approaches for achieving tractability for CSP: (i) by structural restrictions on the interaction between the variables and the constraints and (ii) by language restrictions on the relations that can be used inside the constraints. Apart from defining the notion of backdoor-treewidth and showing how backdoors of small treewidth can be used to efficiently solve CSP, our main technical contribution is a fixed-parameter algorithm that finds a backdoor of small treewidth.
rate research
Read More
We extend the notion of a strong backdoor from the CSP setting to the Valued CSP setting (VCSP, for short). This provides a means for augmenting a class of tractable VCSP instances to instances that are outside the class but of small distance to the class, where the distance is measured in terms of the size of a smallest backdoor. We establish that VCSP is fixed-parameter tractable when parameterized by the size of a smallest backdoor into every tractable class of VCSP instances characterized by a (possibly infinite) tractable valued constraint language of finite arity and finite domain. We further extend this fixed-parameter tractability result to so-called scattered classes of VCSP instances where each connected component may belong to a different tractable class.
In this paper we provide an extended formulation for the class of constraint satisfaction problems and prove that its size is polynomial for instances whose constraint graph has bounded treewidth. This implies new upper bounds on extension complexity of several important NP-hard problems on graphs of bounded treewidth.
The notion of directed treewidth was introduced by Johnson, Robertson, Seymour and Thomas [Journal of Combinatorial Theory, Series B, Vol 82, 2001] as a first step towards an algorithmic metatheory for digraphs. They showed that some NP-complete properties such as Hamiltonicity can be decided in polynomial time on digraphs of constant directed treewidth. Nevertheless, despite more than one decade of intensive research, the list of hard combinatorial problems that are known to be solvable in polynomial time when restricted to digraphs of constant directed treewidth has remained scarce. In this work we enrich this list by providing for the first time an algorithmic metatheorem connecting the monadic second order logic of graphs to directed treewidth. We show that most of the known positive algorithmic results for digraphs of constant directed treewidth can be reformulated in terms of our metatheorem. Additionally, we show how to use our metatheorem to provide polynomial time algorithms for two classes of combinatorial problems that have not yet been studied in the context of directed width measures. More precisely, for each fixed $k,w in mathbb{N}$, we show how to count in polynomial time on digraphs of directed treewidth $w$, the number of minimum spanning strong subgraphs that are the union of $k$ directed paths, and the number of maximal subgraphs that are the union of $k$ directed paths and satisfy a given minor closed property. To prove our metatheorem we devise two technical tools which we believe to be of independent interest. First, we introduce the notion of tree-zig-zag number of a digraph, a new directed width measure that is at most a constant times directed treewidth. Second, we introduce the notion of $z$-saturated tree slice language, a new formalism for the specification and manipulation of infinite sets of digraphs.
We consider the convex hull $P_{varphi}(G)$ of all satisfying assignments of a given MSO formula $varphi$ on a given graph $G$. We show that there exists an extended formulation of the polytope $P_{varphi}(G)$ that can be described by $f(|varphi|,tau)cdot n$ inequalities, where $n$ is the number of vertices in $G$, $tau$ is the treewidth of $G$ and $f$ is a computable function depending only on $varphi$ and $tau.$ In other words, we prove that the extension complexity of $P_{varphi}(G)$ is linear in the size of the graph $G$, with a constant depending on the treewidth of $G$ and the formula $varphi$. This provides a very general yet very simple meta-theorem about the extension complexity of polytopes related to a wide class of problems and graphs. As a corollary of our main result, we obtain an analogous result % for the weaker MSO$_1$ logic on the wider class of graphs of bounded cliquewidth. Furthermore, we study our main geometric tool which we term the glued product of polytopes. While the glued product of polytopes has been known since the 90s, we are the first to show that it preserves decomposability and boundedness of treewidth of the constraint matrix. This implies that our extension of $P_varphi(G)$ is decomposable and has a constraint matrix of bounded treewidth; so far only few classes of polytopes are known to be decomposable. These properties make our extension useful in the construction of algorithms.
After the number of vertices, Vertex Cover is the largest of the classical graph parameters and has more and more frequently been used as a separate parameter in parameterized problems, including problems that are not directly related to the Vertex Cover. Here we consider the TREEWIDTH and PATHWIDTH problems parameterized by k, the size of a minimum vertex cover of the input graph. We show that the PATHWIDTH and TREEWIDTH can be computed in O*(3^k) time. This complements recent polynomial kernel results for TREEWIDTH and PATHWIDTH parameterized by the Vertex Cover.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
