%============================================================================ % last changes: Petr Nov 12 2015 % %============================================================================ \documentclass[12pt]{article} \usepackage{e-jc} \specs{P4.30}{22(4)}{2015} \usepackage{amsmath} \usepackage{amssymb} \usepackage{bm} \usepackage{microtype} %\usepackage{enumitem} %\usepackage{framed} %======================================================================= % Definitions, etc. %======================================================================= \usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} \newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}} \newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}} \newtheorem{theorem}{Theorem}[section] \newtheorem{corollary}[theorem]{Corollary} \newtheorem{definition}[theorem]{Definition} \newtheorem{lemma}[theorem]{Lemma} %%\newtheorem{claim}[theorem]{Claim} %\newtheorem{conjecture}[theorem]{Conjecture} %%\newtheorem{fact}[theorem]{Fact} %%\newtheorem{invariant}[theorem]{Invariant} %%\newtheorem{proposition}[theorem]{Proposition} %\newtheorem{observation}[theorem]{Observation} \def\floor#1{\lfloor #1 \rfloor} \def\ceil#1{\lceil #1 \rceil} \newcommand {\brc} [1] {\left(#1\right)} \newcommand{\Oh}{\mathcal{O}} \newcommand {\Prob} [1] {\Pr \brc{#1 }} \newcommand{\sq}{\hbox{\rlap{$\sqcap$}$\sqcup$}} \newcommand{\xc}{\textrm{xc}} \newcommand\textline[5][t]{ \par\smallskip\noindent\parbox[#1]{.60\textwidth}{\raggedright\textsc{#2}} \parbox[#1]{.12\textwidth}{\centering #3} \parbox[#1]{.12\textwidth}{\centering #4} \parbox[#1]{.14\textwidth}{\raggedleft #5}\par\smallskip } \newcommand\textlineii[5][t]{ \par\smallskip\noindent\parbox[#1]{.23\textwidth}{\raggedright\textsc{#2}} \parbox[#1]{.20\textwidth}{\centering #3} \parbox[#1]{.30\textwidth}{\centering #4} \parbox[#1]{.25\textwidth}{\raggedleft #5}\par\smallskip } \newcommand\textlineiii[5][t]{ \par\smallskip\noindent\parbox[#1]{.45\textwidth}{\raggedright\textsc{#2}} \parbox[#1]{.27\textwidth}{\centering #3} \parbox[#1]{.12\textwidth}{\centering #4} \parbox[#1]{.14\textwidth}{\raggedleft #5}\par\smallskip } \newcommand\problemline[4]{\textline[t]{#1}{\proj{#2}}{$\Oh($#3$)$}{$\Oh($#4$)$}} \newcommand\problemlinealt[4]{\textline[t]{#1}{#2}{#3}{#4}} \newcommand\problemlinealtt[4]{\textlineiii[t]{#1}{#2}{#3}{#4}} \newcommand\rest{\hspace{-1mm}\upharpoonright} \newcommand\proj[1]{$\textrm{proj}_{#1}$} \newcommand\ex{$\textrm{ex}$} \newcommand{\qed}{\hspace*{\fill}\sq} \newenvironment{proof}{\noindent {\it Proof.}\/}{\qed\par\vskip 4mm\par} \def\xx{\bm{x}} \def\yy{\bm{y}} \def\zz{\bm{z}} \def\gg{\bm{g}} \def\ff{\bm{f}} \def\BB{\mathcal{B}} \def\CC{\mathcal{C}} \def\DD{\mathcal{D}} \def\FF{\mathcal{F}} \def\HH{\mathcal{H}} \def\II{\mathcal{I}} \def\KK{\mathcal{K}} \def\CK{\mathcal{K}} \def\RP{\mathcal{R}} \def\NN{\mathbb{N}} \def\RR{\mathbb{R}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \title{\bf Extended Formulation for CSP that is Compact\\ for Instances of Bounded Treewidth\thanks{This research was partially supported by the project 14-10003S of GA \v{C}R.}} \author{Petr Kolman, Martin Kouteck\' y \\ \small Department of Applied Mathematics, \\[-0.8ex] \small Faculty of Mathematics and Physics,\\[-0.8ex] \small Charles University in Prague, \\[-0.8ex] \small Czech Republic\\[-0.8ex] \small \tt kolman@kam.mff.cuni.cz, koutecky@kam.mff.cuni.cz} \date{\dateline{Aug 7, 2015}{Nov 17, 2015}{Nov 27, 2015}\\ \small Mathematics Subject Classifications: 03D15; 52B12; 90C05} \begin{document} \maketitle \begin{abstract} 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. \end{abstract} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Introduction} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Many important combinatorial optimization problems belong to the class of constraint satisfaction problems (CSP). Naturally, a lot of effort has been given to design efficient approximation algorithms for CSP, to prove complexity lower bounds for CSP, and to identify tractable instances of CSP (e.g., from the point of view of parameterized complexity). It has been shown that CSP is solvable in polynomial time for instances whose constraint graph has bounded treewidth~\cite{Freuder:90}. % primal graph is bounded, the problem becomes W[1]-hard~\cite{GSS:02}. In recent years, a lot of attention has been given to study {\em extension complexity} of problems~\cite{CCZ:13}: given a problem $Q$, what is the minimum number of inequalities representing a polytope whose (suitably chosen) linear projection coincides with the convex hull $H$ of all integral solutions of $Q$? Any polytope which projects to $H$ is called an {\em extended formulation} of $H$. %a polytope whose (suitably chosen) linear projection coincides %with the convex hull of all integral solutions of $Q$~\cite{CCZ:13}. Note that membership of a problem in the class P of polynomially solvable problems does not necessarily imply the existence of an extended formulation of polynomial size~\cite{Roth:14}. In this work, we present an extended formulation for CSP and show that its size is polynomial for instances of CSP whose constraint graph has bounded treewidth. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{Notation and Terminology} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% An instance $Q=(V,\DD,\HH,\CC)$ of CSP consists of \begin{itemize} %\item a set of {\em indices} $V = \{1,\ldots,n\}$, \item a set of {\em variables} $z_v$, one for each $v\in V$; without loss of generality we assume that $V = \{1,\ldots,n\}$, \item a set $\DD$ of finite {\em domains} $D_v\subseteq \RR$ (also denoted $D(v)$), one for each $v\in V$, \item a set of {\em hard constraints} $\HH \subseteq \{C_{U}\ |\ U \subseteq V \}$ where each hard constraint $C_{U} \in \HH$ with $U=\{i_1, i_2,\dots,i_k\}$ and $i_1 < i_2 < \cdots < i_k$, is a $|U|$-ary relation $C_U \subseteq D_{i_1}\times D_{i_2}\times \cdots \times D_{i_k}$, \item a set of {\em soft constraints} $\CC \subseteq \{C_U \ |\ U \subseteq V\}$ where each soft constraint $C_{U} \in \CC$ with $U=\{i_1, i_2,\dots,i_k\}$ and $i_1 < i_2 < \cdots < i_k$, is a $|U|$-ary relation $C_{U}\subseteq D_{i_1}\times D_{i_2}\times \cdots \times D_{i_k}$. \end{itemize} The \emph{constraint graph} of $Q$ is defined as $G=(V,E)$ where $E= \{\{u,v\} \ |\ \exists C_{U} \in \CC\cup \HH \textrm{ s.t. } \{u,v\} \subseteq U\}$. We say that a {\em CSP instance $Q$ has bounded treewidth} if the constraint graph of $Q$ has bounded treewidth. In {\em binary CSP}, every hard and soft constraint is a unary or binary relation, and in {\em boolean CSP}, the domain $D_v$ of every variable $v\in V$ is $D_v=\{0,1\}$. We use $D$ to denote the maximal size of all domains, that is, $D=\max_{u\in V}|D_u|$. For a vector $z^{}=(z^{}_1, z_2, \ldots,z^{}_n)$ and a set $U=\{i_1, i_2,\dots,i_k\}\subseteq V$ with $i_1 < i_2 < \cdots < i_k$, we define the {\em projection of} $z$ on $U$ as $z^{}|_U=(z^{}_{i_1}, z_{i_2}, \ldots, z^{}_{i_k})$. A vector $z\in \RR^n$ {\em satisfies the constraint} $C_U \in \CC\cup \HH$ if and only if $z|_U \in C_U$. We say that a vector $z^{\star}=(z^{\star}_1,\ldots,z^{\star}_n)$ is {\em a feasible assignment} for $Q$ if $z^{\star} \in D_1\times D_2\times \ldots\times D_n$ and $z^{\star}$ satisfies every hard constraint $C\in \HH$. For a given feasible assignment $z^{\star}$ we define an {\em extended feasible assignment} $\ex(z^{\star})=(z^{\star},h^{\star})\in \RR^{n+|\CC|}$ as follows: the coordinates of $h^{\star}$ are indexed by the soft constraints from $\CC$ (to be more precise: by the subsets $U$ of $V$ used as lower indices of the soft constraints) and for each $C_U\in \CC$, we have $h^{\star}_U=1$ if and only if $z^{\star}|_U\in C_U$, and $h^{\star}_U=0$ otherwise. We denote by $\FF(Q)$ the set of all feasible assignments for $Q$, by $\FF^{ex}(Q)=\{\ex(z^{\star}) \ | \ z^{\star}\in \FF(Q)\}$ the set of all extended feasible assignments for~$Q$. For every instance $Q$ we define two polytopes: % associated with it: $CSP(Q)$ is the convex hull of $\FF^{ex}(Q)$ and $CSP'(Q)$ the convex hull of $\FF(Q)$. We also define three trivial linear projections: \begin{itemize} \item $\textrm{proj}_V(z,h) = z$, \ \ \ \ \ \ $\textrm{proj}_E(z,h) = h$, \ \ \ \ \ \ $\textrm{proj}_{id}(z,h) = (z,h)$ \end{itemize} where $z\in \RR^n$ and $h\in \RR^{|\CC|}$, and observe that $\textrm{proj}_V(CSP(Q)) = CSP'(Q)$. In the {\em decision} version of CSP, the set $\CC$ of soft constraints is empty and the task is to decide whether there exists a feasible assignment. In the {\em maximization} ({\em minimization}, resp.) version of the problem, the task is to find a {feasible assignment} that maximizes (minimizes, resp.) the number of \emph{satisfied} (unsatisfied, resp.) soft constraints. Note that there is no difference between maximization and minimization versions of the problem with respect to optimal solutions but the two versions differ significantly from an approximation perspective. In the {\em weighted} version of CSP we are also given a weight function $w: \CC \rightarrow \RR$ that specifies for each soft constraint $C \in \CC$ its weight $w(C)$. The goal is to find a feasible assignment that maximizes (minimizes, resp.) the total weight of satisfied (unsatisfied, resp.) constraints. The unweighted version of CSP is equivalent to the weighted version with $w(C) = 1$ for all $C \in \CC$. Even more generally, the relations in the soft constraints can be replaced by bounded real valued payoff functions: a soft constraint $C_U \in \cal C$ with $U=\{i_1, i_2,\dots,i_k\}$ is not a $|U|$-ary relation but a function $w:D_{i_1}\times D_{i_2}\times \ldots\times D_{i_k}\rightarrow \RR$ and the payoff of the soft constraint $C_U$ for a feasible assignment $z^{\star}$ is $w(z^{\star}|_U)$; the objective is to maximize (minimize, resp.) the total payoff. For the sake of simplicity of the presentation we do not consider the problem in this generality although the techniques used in this paper apply in the general setting as well. For notions related to the treewidth of a graph, % and nice tree decomposition, we stick to the standard terminology as given in the book by Kloks~\cite{Kloks:94}. For the sake of completeness, below we provide the definition of the tree decomposition and the nice tree decomposition of a graph. A \emph{tree decomposition} of a graph $G=(V,E)$ is a tree $T=(V_T,E_T)$ in which each \emph{node} $a \in T$ has an assigned set of vertices $B(a) \subseteq V$ (called a \emph{bag}) such that $\bigcup_{a \in V_T} B(a) = V$ with the following properties: \begin{itemize} %\setlength\itemsep{0em} \item for any $uv \in E$, there exists a node $a \in V_T$ such that $u, v \in B(a)$. \item if $v \in B(a)$ and $v \in B(b)$, then $v \in B(c)$ for all $c$ on the path from $a$ to $b$ in $T$. \end{itemize} The {\em treewidth $tw(T)$ of a tree decomposition} $T$ is the size of the largest bag of $T$ minus one. The {\em treewidth $tw(G)$ of a graph} $G$ is the minimum treewidth over all possible tree decompositions of $G$. A \emph{nice tree decomposition} is a tree decomposition with one special node $r$ called the \emph{root} in which each node is one of the following types: \begin{itemize} %\setlength\itemsep{0em} \item \emph{Leaf node}: a leaf $a$ of $T$ with $|B(a)|=1$. \item \emph{Introduce node}: an internal node $a$ of $T$ with one child $b$ for which $B(a) = B(b) \cup \{v\}$ for some $v \in B(a)\setminus B(b)$. \item \emph{Forget node}: an internal node $a$ of $T$ with one child $b$ for which $B(a) = B(b) \setminus \{v\}$ for some $v \in B(b)$. \item \emph{Join node}: an internal node $a$ with two children $b$ and $c$ with $B(a) = B(b) = B(c)$. \end{itemize} Note that restricting ourselves to nice tree decompositions is not a problem: any tree decomposition with $b$ bags can be transformed in linear time into a nice one of the same width and with at most $4b$ bags~\cite{Kloks:94}. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{Related Work} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsubsection{CSP for graphs of bounded treewidth.} As CSP captures many NP-hard problems, it is a natural problem to identify tractable special cases of CSP. %One of them constitute instances whose constraint graph has bounded treewidth. Freuder~\cite{Freuder:90} showed that CSP instances with treewidth bounded by $\tau$ can be solved in time $O(D^{\tau}n)$ when a tree decomposition of treewidth $\tau$ of the constraint graph is given. Later, Grohe et al.~\cite{GSS:01} proved that, assuming $FPT\not= W[1]$, this is essentially the only nontrivial class of graphs for which CSP is solvable in polynomial time (cf.~Marx~\cite{Marx:10}). %Grohe~\cite{Grohe:07} Describing the polytope of CSP solutions by the means of linear programming, for instances of bounded treewidth, is not a new idea. In 2007, Sellmann et al. published a paper~\cite{SML:07} in which they described a linear program that was supposed to define the convex hull of all feasible solutions of a binary CSP when the constraint graph is a tree. They also provided a procedure to convert a given CSP instance with bounded treewidth into one whose constraint graph is a tree, at the cost of blowing up the number of variables and constraints by a function of the treewidth. Unfortunately, there was a substantial bug in their proof and one of the main theorems in the paper does not even hold~\cite{Sellmann:08}. The paper~\cite{SML:07} also implicitly includes this folklore result: if the constraint graph has treewidth at most $\tau$, then CSP can be solved by $\tau$ levels of the Sherali-Adams hierarchy (we are not aware of an explicit formulation of this result in its generality though partial results of this type are known, e.g., for independent set~\cite{BO:04}). The resulting formulation is of size $\Oh(n^\tau)$ while our approach yields size $\Oh(D^\tau n)$. %Compared to their approach, we describe directly the polytope of the original %problem and our proof is self-contained, without relying on other techniques; %also, our results apply not only for binary CSP but for any CSP. \subsubsection{CSP for general graphs.} %Among the most general and powerful techniques in the design of %optimal and approximation algorithms belong linear programming (LP) %and semidefinite programming (SDP). The effort to use these %techniques in coping with CSP on general graphs is not %surprising. Here we present a sample of a few relevant recent results. % Chan et al.~\cite{CLRS:13} study the extent to which linear programming relaxation can be used in dealing with approximating CSP. They show that polynomial-sized LPs are exactly as powerful as LPs obtained from a constant number of rounds of the Sherali-Adams hierarchy. They also prove integrality gaps for polynomial-sized LPs for some CSP. %FOCS Raghavendra~\cite{Ragha:08} shows that under the Unique Games Conjecture, a certain simple SDP relaxation achieves the best approximation ratio for every CSP. In a follow up paper, Raghavendra and Steurer~\cite{RS:09a} describe an efficient rounding scheme that achieves the integrality gap of the simple SDP relaxation, and, in another paper~\cite{RS:09b}, they show unconditionally that the integrality gap of this SDP relaxation cannot be reduced by Sherali-Adams hierarchies. \subsubsection{Other related results.} Laurent~\cite{Laurent:09} provides extended formulations for the independent set and the max cut problems, both a special case of CSP, that have size $O(2^{\tau}n)$ where $\tau$ denotes the treewidth of the given graph. These results are given in the context of moment matrices as an application of a sparsity structure present in instances of bounded treewidth. Independently, Buchanan and Butenko~\cite{BB:14} later gave the same result for the independent set problem. Our results can be viewed as a generalization: the size of our formulation for a general CSP, when applied to the independent set and the max cut problems, is also $O(2^{\tau}n)$. In a recent work, independently of our result, Bienstock and Munoz~\cite{BM:15} define a class of so called {\em general binary} optimization problems which are essentially weighted boolean CSP problems, % with binary % variables, a linear objective function and a set of CSP-like constraints, and, among other results, for instances of treewidth $\tau$ provide an LP formulation of size $O(2^{\tau}n)$. Again, this is a special case of our result in this paper. It is worth mentioning at this point that every CSP instance can be transformed into a boolean CSP instance by encoding every variable with domain size $D$ by $\ceil{\log D}$ boolean variables. This increases the treewidth of the constraint graph by a factor of $\ceil{\log D}$ and thus leads to a formulation of size $\Oh(2^{\tau \ceil{\log D}}n)$. This bound corresponds to $\Oh(D^\tau n)$ in the special case that $D$ is a power of two, and to $\Oh(D^\tau 2^\tau n)$ in the general case. % \pagebreak %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{New Results} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %In this paper, for every CSP instance $Q=(V,\DD,\HH,\CC)$, we %describe a polytope $P(Q)$ and show that $P(Q)$ is an extended formulation %of $CSP(Q)$ and $CSP'(Q)$. %%That is, a certain projection of $P(Q)$ coincides with $CSP(Q)$ %%and another projection with $CSP'(Q)$. %We also show that the size of $P(Q)$ is $O(D^\tau n)$ %where $\tau$ is the treewidth of $Q$. %%and $D = \max_{v \in V} |D_v|$. Our main result is summarized as the following theorem. \begin{theorem}\label{thm:main} For every instance $Q=(V,\DD,\HH,\CC)$ of CSP, there exists an extended formulation $P(Q)$ of $CSP(Q)$ and $CSP'(Q)$ of size $\Oh(D^{\tau}n)$ where $\tau$ is the treewidth of $Q$; moreover, given a tree decomposition of the constraint graph of $Q$ of width $\tau$, the corresponding LP can be constructed in time $\Oh(D^{\tau}n)$. %and $D = \max_{v \in V} |D_v|$ %The size of the formulation (\ref{LP:sumtoone}) - (\ref{LP:f_nonnegative}) \end{theorem} As a corollary we obtain upper bounds on the extension complexity for several NP-hard problems on the class of graphs with bounded treewidth; as far as we know, these results have not been known. \iffalse \paragraph{Organization of the paper.} In Section~\ref{sec:polytope} we provide a new linear program and prove that it is an extended formulation for CSP. In Section~\ref{sec:problems} we look at several known NP-hard problems and provide upper bounds on their extension complexity on graphs of bounded treewidth as implied by the main theorem. \fi %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{CSP Polytope}\label{sec:polytope} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{Integer Linear Programming Formulation} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% We start by introducing the terms and notation that we use throughout this section. We assume that $Q=(V,\DD,\HH,\CC)$ is a given instance of CSP. % with $V=\{1, 2, \ldots, n\}$. Let $\lambda$ be a symbol not appearing in any of the domains $D_u$, $u\in V$. For every subset $W \subseteq V$ we define the set of all {\em configurations of} $W$ as $$\CK(W) = \{(\alpha_1, \dots, \alpha_n)\ |\ \forall C_U\in \HH \ (U\subseteq W \implies \alpha|_{U}\in C_U), \mbox{ and } \forall i \not\in W \ \alpha_i = \lambda\}\ $$ For a configuration $K\in \CK(U)$ and $v\in V$, we use the notation $K(v)$ to refer to the $v$-th element of $K$. % that is, to the value in $K$ corresponding to the variable $z_v$. % Petr: neni presne, neb pro u\in V\setminus U to neodpovida z_i Also, for a configuration $K\in \CK(U)$, $v\in V\setminus U$ and $\alpha\in D_v$, we use the notation $K[v \leftarrow \alpha]$ to denote the vector $K'$ %%\in \KK(U\cup\{v\})$ such that $K'(v) = \alpha$ and $K'(u) = K(u)$ for every $u \neq v$. Note that $K[v \leftarrow \alpha]$ does not necessarily have to be a configuration. For an $n$-dimensional vector $K=(\alpha_1, \dots, \alpha_n)$ and a subset of variables $U \subseteq V$ we denote by $K\rest_U$ the \textit{restriction of $K$ to $U$} that is defined as an $n$-dimensional vector with $K\rest_U(i) = K(i)$ for $i \in U$ and $K\rest_U(i) = \lambda$ for $i \not\in U$ (i.e., we set to $\lambda$ all coordinates of $K$ outside of $U$). We denote by $\Lambda$ the configuration $(\lambda, \dots, \lambda)\in \KK(\emptyset)$; note that for $\alpha\in D_v$, $\Lambda[v \leftarrow \alpha]$ is the vector with exactly one non-$\lambda$ element, namely the $v$-th element, equaling $\alpha$. In our linear program, for every index $v \in V$ and every $i\in D_v$, we introduce a binary variable $y_v^i$. The task of the variable $y_v^i$ is to encode the value of the CSP-variable $z_v$: the variable $y_v^i$ is set to one if and only if $z_v=i$. Since in every solution each variable assumes a unique value, we enforce the constraint $\sum_{i\in D(v)} y_{v}^i = 1$ for each $v\in V$. %Let $\KK_\CC=\bigcup_{U: C_U \in \CC\cup \HH} \KK(U)$. For every configuration $K \in \bigcup_{U: C_U \in \CC\cup \HH} \KK(U)$ we introduce a binary variable $g(K)$. The intended meaning of the variable $g(K)$, for $K\in \KK(U)$ and $U\subseteq V$, is to provide information about the values of the CSP-variables $z_u$ for $u\in U$ in the following way: $g(K)=1$ if and only if for every $u \in U$, $z_u = K(u)$. To ensure consistency between the $y$ and $g$ variables, for every $C_U\in \CC\cup \HH$ and for every $v\in U$, we enforce the constraint $\sum_{K \in \KK(U): K(v)=i} g(K) = y_v^i$. Note that for binary CSP, the $g$ variables capture the values of CSP-variables $z$ for pairs of elements from $V$ that correspond to edges of the constraint graph. Relaxing the integrality constraints we obtain the following initial LP relaxation of the CSP problem~$Q=(V,\DD, \HH, \CC)$: \begin{align} \sum_{i\in D(v)} y_{v}^i & = 1 & & \forall v\in V \label{LP2:sumtoone} \\ \sum_{K \in \KK(U): K(v)=i} g(K) & = y_v^i & & \forall C_U \in \CC\cup\HH \ \forall v\in U \ \forall i\in D(v) \label{LP2:y_i} \\ 0 \leq \yy,\gg & \leq 1. & & \label{LP2:non-negative1} \end{align} %Note that the soft unary constraints do not yield any constraints in the LP; %they only affect the objective function. Note that there is a one to one correspondence between the (extended) feasible assignments of $Q$ and integral solutions of (\ref{LP2:sumtoone}) - (\ref{LP2:non-negative1}); from now on we denote by $\textrm{proj}_1$ the linear projection of the convex hull of integral solutions of %\marginpar{\small Details!} (\ref{LP2:sumtoone}) - (\ref{LP2:non-negative1}) to $CSP(Q)$. Also observe that the total weight of CSP-constraints satisfied by an integral vector $(\yy,\gg)$ satisfying (\ref{LP2:sumtoone}) - (\ref{LP2:non-negative1}) is\footnote{In the case of general payoff functions, the total weight is given by $\sum_{C_U \in \CC} \sum_{K\in \KK(U):K|_U \in C_U} w(K|_U) g(K) $} \begin{align} \sum_{C_U \in \CC} w(C_U) \sum_{K\in \KK(U):K|_U \in C_U} g(K). \nonumber \end{align} \iffalse and that \begin{align} P_{asg}(Q) = & \{\zz \ | \ \exists (\yy,\gg)\in P_I(Q) \mbox{ s.t. } \forall v\in V, z_{v}=\sum_{i\in D(v)} i \cdot y_{v}^{i} \ \}. %\sum_{(u,v)\in E}\sum_{i\in D(u)} \sum_{j\in D(v)} r_{uv}^{ij} \cdot g_{uv}^{ij}. \end{align} In words, the polytope $P_{asg}(Q)$ is a projection of the polytope $P_I(Q)$. \fi Unfortunately, even for CSP problems whose constraint graph is series-parallel, the polytope given by the LP~(\ref{LP2:sumtoone}) - (\ref{LP2:non-negative1}) is not integral (consider, e.g., the instance of CSP corresponding to the independent set problem on $K_3$). The weakness of the formulation is that no {\em global} consistency among the $\yy$ variables is guaranteed. To strengthen the relaxation, we introduce new variables and constraints derived from a tree decomposition of the constraint graph of $Q$. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{Extended Formulation} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Here we describe, for every CSP instance $Q=(V,\DD,\HH,\CC)$, a polytope $P(Q)$, and in the next subsection we prove that $P(Q)$ is an extended formulation of $CSP(Q)$ and $CSP'(Q)$. The set of variables in the given LP description of $P(Q)$ is substantially different from the set of variables used in the LP~(\ref{LP2:sumtoone}) - (\ref{LP2:non-negative1}), and the set of new constraints is completely different from the the set of constraints in the LP~(\ref{LP2:sumtoone})~-~(\ref{LP2:non-negative1}). Whereas in the previous subsection, there is (roughly) a variable $g(K)$ for every feasible assignment of every subset of CSP variables corresponding to a {\em soft or hard constraint}, here we have a variable for every feasible assignment of every subset of CSP variables corresponding to a {\em bag in a given tree decomposition of the constraint graph}. Nevertheless, as we show after defining $P(Q)$, there exists a simple linear projection of $P(Q)$ to the convex hull of all integral points in the polytope given by the LP~(\ref{LP2:sumtoone})~-~(\ref{LP2:non-negative1}). Let $T=(V_T,E_T)$ be a fixed nice tree decomposition~\cite{Kloks:94} of the constraint graph of $Q$ and for every node $a\in V_T$, let $B(a)\subseteq V$ denote the corresponding bag. Let $\BB = \{B(a) \ |\ a \in V_T\}$ denote the set of all bags of $T$. %Note that in general $|\BB| \neq |V_T|$ as, e.g., for a join node $c$ %with children $a,b$ we have $B(a) = B(b) = B(c)$. Let $\KK_\BB=\bigcup_{B\in \BB} \KK(B)$ be the set of all configurations of all bags in $T$. We use $V_I\subseteq V_T$ to denote the subset of all introduce nodes in $T$ and $V_F \subseteq V_T$ to denote the subset of all forget nodes in $T$. For every configuration $K\in \KK_\BB$ we introduce a binary variable $f(K)$. As in the previous subsection, the intended meaning of the variable $f(K)$ for $B\in \BB$ and $K\in \KK(B)$, is to provide information about the values of the CSP-variables $z_u$ for $u\in B$ in the following way: $f(K)=1$ if and only if for every $u \in B$, $z_u = K(u)$. To ensure consistency among variables indexed by the configurations of the same bag, namely to ensure that for every $B \in \BB$ there exists exactly one configuration $K \in \KK(B)$ with $f(K) = 1$, we introduce for every $B \in \BB$ the LP constraint $\sum_{K \in \KK(B)} f(K) = 1$. For every introduce node $c\in V_T$ with a child $b\in V_T$ and for every configuration $K\in \KK(B(b))$ we have the constraint $\sum_{K' \in \KK(B(c)): K'\ \rest_{B(b)} = K}f(K') = f(K)$, % where $v$ is the only element in $B(c)\setminus B(b)$. and symmetrically, for every forget node $c\in V_T$ with a child $b\in V_T$ and for every configuration $K\in \KK(B(c))$ we have the constraint $\sum_{K' \in \KK(B(b)): K'\ \rest_{B(c)} = K}f(K') = f(K)$. % where $v$ is the only element in $B(b)\setminus B(c)$. Relaxing the integrality constraints and putting all these additional constraints together, we obtain: \begin{align} \sum_{K\in \KK(B)} f(K) & = 1 & & \forall B\in \BB \label{LP:configurations} \\ \sum_{K' \in \KK(B(c)): K'\ \rest_{B(b)} = K}f(K') & = f(K) & & \forall c\in V_I, \forall K\in \KK(B(b)) \mbox{ where $b$ is } \label{LP:introduce} \\[-14pt] & & & \mbox{the only child of $c$} \nonumber \\[3pt] \sum_{K' \in \KK(B(b)): K'\ \rest_{B(c)} = K}f(K') & = f(K) & & \forall c\in V_F, \forall K\in \KK(B(c)) \mbox{ where $b$ is } \label{LP:forget} \\[-14pt] & & & \mbox{the only child of $c$} \nonumber \\[3pt] 0\leq \ff & \leq 1. & & \label{LP:f_nonnegative} \end{align} For the given binary CSP instance $Q$, we denote the polytope associated with the LP (\ref{LP:configurations}) - (\ref{LP:f_nonnegative}), as $P(Q)$. %P_{proj}=\{(\sum_{0\le i\le L}\sum_{\substack{0\le j\le L\\ j\ne i-1,i,i+1}} g_e^{ij})_{e\in E} \in \RR^E\ | \ %% d(\yy,\gg,\ff)\in P \}.$$ %let $$P_{proj}(Q)=\{(\yy,\gg)\ | \ (\yy,\gg,\ff)\in P(Q) \mbox{ for some } \ff \}. $$ Consider now a vector $\ff\in P(Q)$ and the following set of linear equations: \begin{align} y_{v}^i & = \sum_{{K\in \KK(B) : K(v)=i}} f(K) & & \forall B\in\BB, \forall v\in B, \forall i\in D_v \label{LP3:y} \\ g(K) & = \sum_{K'\in \KK(B) : K'\ \rest_U = K} f(K') & & \forall B\in\BB, \forall C_U \in \CC\cup\HH \mbox{ s.t. } U\subseteq B, \forall K\in \BB(U) \label{LP3:gK}. \end{align} % \forall B\in \BB \ \forall U \subseteq B \ % \mbox{ s.t. } C_U\in \CC \cup \HH, \mbox{ and } \ \forall K\in \KK(U) It is just a technical exercise to check that for a given $\ff\in P(Q)$, there always exists a unique solution $(\yy, \gg)$ of this LP and that the unique $(\yy, \gg)$ is a linear projection of $\ff$. Moreover, such a vector $(\yy, \gg)$ also satisfies the LP constraints~(\ref{LP2:sumtoone}) - (\ref{LP2:non-negative1}). The point is that there exists a linear projection, obtained from ~(\ref{LP3:y}) - (\ref{LP3:gK}), of $P(Q)$ into the polytope defined by the LP~(\ref{LP2:sumtoone}) - (\ref{LP2:non-negative1}); moreover, an integral point from $P(Q)$ is mapped on an integral point. From now on we denote this projection $\textrm{proj}_2$. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{Proof of Theorem~\ref{thm:main}}\label{subsec:proof} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% As in the previous subsections, we assume that $Q=(V,\DD,\HH,\CC)$ is a given instance of CSP, $G=(V,E)$ is the constraint graph of $Q$ and $T=(V_T, E_T)$ is a fixed nice tree decomposition of $G$. We start by introducing several notions that will help us dealing with tree decompositions and our linear program. For a node $a\in V_T$, let $T(a)=(V_{a},E_{a})$ be the subtree of $T$ rooted in $a$; % and $G'=(V',E')$ be the subgraph of $G$ corresponding to $T'$; the {\em configurations relevant to} $T(a)$ are those in the set $\RP(a)=\bigcup_{b \in V_{a}} \KK(B(b))$, and the {\em variables relevant to} $T(a)$ are those $f(K)$ for which $K\in \RP(a)$. %is a configuration relevant to $G'$. For succinctness of notation, we denote the projection $\ff|_{\RP(a)}$ of the vector $\ff$ on the set of variables relevant to $T(a)$ also by $\ff|_{a}$. The {\em constraints relevant to} $T(a)$ are those containing only the variables relevant to $T(a)$. We say that a vector $I\in \{0,1\}^{\RP(a)}$ {\em agrees with the configuration} $K\in \RP(a)$ if $I(K)=1$. Let $\ff$ be a fixed solution of the LP~(\ref{LP:configurations}) - (\ref{LP:f_nonnegative}) that corresponds to a vertex of the polytope $P(Q)$. Our main tool is the following lemma; our approach was partially inspired by the proof of the matching polytope theorem as given by Schrijver~\cite{Schrijver:86}. \begin{lemma}\label{lem:combination} For every %subgraph $G'$ of $G$ corresponding to a subtree of $T$ % rooted in a node $b\in V_T$, there exist a positive integer $M$ and binary vectors $I_1, I_2, \dots, I_M \in\{0,1\}^{\RP(b)}$, some possibly identical, such that \begin{itemize} \item[$\spadesuit$] every $I_i$ satisfies the constraints relevant to $T(b)$, \item[$\clubsuit$] $\ff|_{b} = \frac{1}{M}\sum_{i=1}^M I_i $. % that is, the % vector $\ff|_{b}$ consisting of % variables relevant to $T(b)$ is a convex combination of the % integral partial solutions. \end{itemize} \end{lemma} \begin{proof} By induction. We start in the leaves of $T$ and proceed in a bottom-up fashion. \subsubsection{Base case.} Assume that $b\in V_T$ is a leaf of the nice decomposition tree $T$. By definition of a nice tree decomposition, the bag $B(b)$ consists of a single vertex, say a vertex $v\in V$. The only variables relevant to $T(b)$ are $f(K)$ for all %$K\in \KK(B(b))=\bigcup_{j\in D(v)}\Lambda[v \leftarrow j]$, $K\in \KK(B(b))=\{\Lambda[v \leftarrow j] \mid j\in D(v)\}$ and the only relevant constraints are those of the type (\ref{LP:configurations}) and (\ref{LP:f_nonnegative}). Let $M' \in \mathbb{N}$ be such that an $M'$-multiple of every relevant variable is integral; as $\ff$ is a solution corresponding to a vertex of the polytope $P(Q)$, all the variables are rational which guarantees that such an $M'$ exists. For every $j\in D_v$ we define an integral vector $I_j$ such that $I_j(\Lambda[v \leftarrow j])=1$ and $I_j(\Lambda[v \leftarrow i])=0$ for every $i\neq j$. The vector $I_j$ will appear with multiplicity $M'\cdot y_v^j$ among the integral solutions $I_1,\ldots,I_{M'}$ for $G'$. Then, obviously, both properties $\spadesuit$ and $\clubsuit$ are satisfied. \subsubsection{Inductive step.} Consider an internal node $c\in V_T$ of the nice decomposition tree~$T$. We distinguish three cases: $c$ is a join node, $c$ is an introduce node and $c$ is a forget node. {\em Join node.} Assume that the two children of the join node $c$ are $a$ and $b$. Recall that $B(a)=B(b)=B(c)$. By the inductive assumption, there exist integers $M$ and $M'$ and integral vectors $I_1,\ldots,I_M\in\{0,1\}^{\RP(a)}$, each of them satisfying the relevant constraints for $T(a)$ and such that $\ff|_{a} = \frac{1}{M}\sum_{i=1}^M I_i $, and integral vectors $J_1,\ldots,J_{M'}\in\{0,1\}^{\RP(b)}$, each of them satisfying the relevant constraints for $T(b)$ and such that $\ff|_{b} = \frac{1}{M'}\sum_{i=1}^{M'} J_i $. Two vectors $I_i$ and $J_j$ that agree with a given configuration $K \in \KK(B(c))$ can be easily merged into an integral vector $L\in\{0,1\}^{\RP(c)}$ that satisfies $L|_{a}=I_i$ and $L|_{b}=J_j$; as the set of all constraints relevant to $T(c)$ is the union of the constraints relevant to $T(a)$ and the constraints relevant to $T(b)$, the vector $L$ satisfies also all the constraints relevant to $T(c)$. For simplicity we assume, without loss of generality, that $M=M'$. Then, by the property $\clubsuit$ and since $B(a) = B(b) = B(c)$, for every configuration $K\in \KK(B(c))$, the number of vectors $I_i$ that agree with $K$ is equal to the number of vectors $J_j$ that agree with $K$, namely $M\cdot f(K)$. Thus, it is possible to match the vectors $I_i$ and $J_j$ one to one in such a way that both vectors in each pair agree with the same configuration; let $L_1, L_2, \ldots, L_M$ denote the result of their merging as described above. Then the vectors $L_i$ satisfy the property $\spadesuit$ as explained in the previous paragraph, and by construction they also satisfy the property $\clubsuit$. {\em Introduce node.} Assume that the only child of the introduce node $c$ is a node $b$ and $B(c)=B(b)\cup \{v\}$. By the inductive assumption, there exists integer $M$ and integral vectors $I_1,\ldots,I_M\in\{0,1\}^{\RP(b)}$, each of them satisfying the relevant constraints for $T(b)$ and such that $\ff|_{b} = \frac{1}{M}\sum_{i=1}^M I_i$. Without loss of generality we assume that for every variable relevant to $T(c)$, its $M$-multiple is integral. We partition the vectors $I_1,\ldots,I_M$ into several groups indexed by the configurations from $\KK(B(b))$: the group $Z_K$, for $K\in \KK(B(b))$, consists exactly of those vectors $I_i$ that agree with $K$. Consider a fixed configuration $K\in \KK(B(b))$ and the corresponding group $Z_K$. Note that the size of this group is $M\cdot f(K)$. We further partition the group $Z_K$ into at most $|D_v|$ subgroups $Z_{K'}$, where $K' = K[v \leftarrow j]$, for every $j\in D_v$ satisfying $K[v \leftarrow j]\in \KK(B(c))$, in such a way that $Z_{K'}$ contains exactly $M\cdot f(K')$ vectors (it does not matter which ones); the LP constraint~(\ref{LP:introduce}) makes this possible. Then, for every $j\in D_v$, we create from every vector $I\in Z_{K[v \leftarrow j]}$ a new integral vector $J_{I}$ in the following way: \begin{itemize} \item for every $\bar K\in \RP(b)$, $J_I(\bar K)=I(\bar K)$; this guarantees $J_{I}|_{b}=I$, \item $J_I(K[v \leftarrow j])=1$, \item for every $i\in D_v$, $i\not =j$, $J_I(K[v \leftarrow i])=0$. \end{itemize} Obviously, the new vectors $J_{I}$ %, for $K\in \KK(B(b))$ and $j\in D_v$ and $K' = K[v \leftarrow j]$, satisfy all constraints relevant to $T(b)$, and it is easy to check that they satisfy all constraints relevant to $T(c)$ as well, given the definitions above. Moreover, the definitions above imply that the vectors $J_{I}$ satisfy the property $\clubsuit$. {\em Forget node.} Assume that the only child of the forget node $c$ is a node $b$, $B(c)=B(b)\setminus \{v\}$. This case is symmetric to the previous one in that instead of splitting the groups $Z_K$ into smaller groups $Z_{K'}$, we merge them into bigger $Z_{K'}$. %Since the subgraphs corresponding to the forget node and its child are %the same, %The only possibly new relevant variables are $f(K')$ for %$K' \in \KK(B(c))$. By the inductive assumption, there exists an integer $M$ and integral vectors $I_1,\ldots,I_M\in\{0,1\}^{\RP(b)}$, each of them satisfying the relevant constraints for $T(b)$ and such that $\ff|_{b} = \frac{1}{M}\sum_{i=1}^M I_i$. Without loss of generality we assume that for every variable relevant to $T(c)$, its $M$-multiple is integral. We partition the vectors $I_1,\ldots,I_M$ into several groups indexed by the configurations from $\KK(B(b))$: the group $Z_K$, for $K\in \KK(B(b))$, consists exactly of those vectors $I_i$ that agree with $K$. Note that the size of $Z_K$ is $M\cdot f(K)$. For every $K' \in \KK(B(c))$ we create a bigger group $Z_{K'}$ by merging $|D_v|$ of the groups $Z_K$, namely those satisfying $K|_{B(c)} = K'$. By the LP constraint~(\ref{LP:forget}), the new group $Z_{K'}$ contains exactly $M\cdot f(K')$ vectors. For every $K' \in \KK(B(c))$, we create from every vector $I\in Z_{K'}$ a new integral vector $J_{I}$ in the following way: \begin{itemize} \item for every $\bar K\in\RP(b)$, $J_I(\bar K)=I(\bar K)$. \end{itemize} If $\KK(B(c))\subseteq \RP(b)$, there is nothing more to do. Otherwise we further define \begin{itemize} \item $J_I(K')=1$, and for every $\hat{K} \in \KK(B(c))$, $\hat{K}\not = K'$, $J_I(\hat{K}) = 0$. \end{itemize} We have to check that the vectors $J_{I}$ satisfy all constraints relevant to $T(c)$. The only possibly new constraints are those using variables $f(K')$ for $K' \in \KK(B(c))$ and it is easily seen that they are satisfied, given the definitions above. Also, the definitions above imply that the vectors $J_{K'}$ satisfy the property $\clubsuit$. %\qed \end{proof} By applying Lemma~\ref{lem:combination} to the whole tree $T$, that is, to the subtree rooted in the root of $T$, we immediately obtain that $\ff$ is an integral vector, and, thus, also the corresponding vertex of $P(Q)$ is integral. As this holds for every vertex of $P(Q)$, we conclude that $P(Q)$ is an integral polytope. Considering the notes at the ends of the previous two subsections, we also conclude that $CSP(Q) = \textrm{proj}_1(\textrm{proj}_2(P(Q))$ and $CSP'(Q)=\textrm{proj}_V(CSP(Q))$. %then easily obtained from $CSP(Q)$ by projecting out the variables %$h$. To complete the proof of Theorem~\ref{thm:main}, we observe that the number of variables and constraints in the LP~(\ref{LP:configurations}) - (\ref{LP:f_nonnegative}) is $\Oh(D^{\tau}n)$. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Applications}\label{sec:problems} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% The purpose of this section is to make explicit the extension complexity upper bounds given in Theorem~\ref{thm:main} for several well known graph problems. Note that in all considered cases the constraint graph obtained from our CSP formulation is identical with the input graph; specifically, this means the treewidth of the CSP instance is the treewidth of the input graph. This is not obvious: for example, a natural CSP formulation of the \textsc{Minimum Dominating Set} problem involves constraints over a neighborhood of a vertex and thus has a possibly unbounded treewidth. %; as far as we know. %, they have not been stated in this form before. We find it interesting that the attained extension complexity upper bounds almost meet the best possible, assuming Strong ETH, \textit{time complexity} lower bounds, given by Lokshtanov et al. \cite{LMS:11}. They show for several problems whose time complexity is upper bounded by $\Oh(c^\tau n^{\Oh(1)})$, that they cannot be solved in time $\Oh((c-\epsilon)^\tau n^{\Oh(1)})$, for any $\epsilon>0$, unless SETH fails. %Note that this does not rule out the existence of an %algorithm running e.g. in time $\Oh(c-\frac{1}{\log n})^\tau n^{\Oh(1)})$. The only exception in our list is the \textsc{Multiway Cut} problem where the corresponding lower bounds are not known. \iffalse \begin{theorem} The problems \textsc{Coloring}, \textsc{List-$H$-Coloring} (\textsc{List Homomorphism}), \textsc{Unique Games}, \textsc{Multiway Cut}, \textsc{Max Cut}, \textsc{Edge Bipartization}, \textsc{Vertex Cover}, \textsc{Independent Set} and \textsc{Odd Cycle Transversal} are binary CSP problems and have compact extended formulations.\label{thm:problems_are_csp} \end{theorem} \fi %\subsection{Proof of Theorem \ref{thm:problems_are_csp}} To state our results, we use for each problem % in the form of a list of problems, each %accompanied with definition, CSP formulation and other relevant information. the following template: \begingroup %\setlength{\parindent}{0em} \noindent \hrulefill %\begin{framed} \textlineii[t]{Problem name}{Projection}{Extension complexity}{Time complexity} \textsc{Instance:} \ \ \ldots % Graph $G=(V,E)$ \dots \textsc{Solution:} \ \ \ldots % A subset of vertices $W \subseteq V$ of minimum size such that \dots \textsc{CSP formulation:} $V$, $\DD$, $\HH$, $\CC$. \hfill CSP version: Decision / \textsc{Max} / \textsc{Min} where {\em Projection} is the name of the linear projection that yields the natural polytope of the problem $Q$ from the $CSP(Q)$ polytope (or from the $P(Q)$ polytope, in case of the OCT problem). %Given $z\in \RR^n$ and $h\in \RR^{|\CC|}$, we define %the following projections: %\begin{itemize} %\item $\textrm{proj}_V(z,h) = z$, %\item $\textrm{proj}_E(z,h) = h$, %\item $\textrm{proj}_{id}(z,h) = (z,h)$ %(i.e., an identity) %\item $\textrm{proj}_V(CSP(Q)) = \{z \in \RR^n \ |\ (z,h) \in CSP(Q)\}$ %\item $\textrm{proj}_E(CSP(Q)) = \{h \in \RR^{\CC} \ |\ (z,h) \in CSP(Q)\}$ %\item $\textrm{proj}_{id}(CSP(Q)) = CSP(Q)$ (i.e., an identity) %\item $\textrm{proj}_{OCT}(P(Q)) = \{z' \in \RR^n \ %| \ (y,g) \in \textrm{proj}_2(P(Q)); z'_v = 0y_u^0 + 1y_u^1 + 1y_u^2\}$ % (i.e., $z'_v = % 0$ iff $z_v = 0$ and $z'_v = 1$ iff $z_v = 1$ or $z_v = 2$). %\end{itemize} We use the notation $[n] = \{1, \dots, n\}$. \noindent \hrulefill %%% COLORING %\begin{framed} \problemline{Coloring / Chromatic Number \cite{ACGKMP:99}}{V}{$q^\tau n$}{$q^\tau n$} \textsc{Instance:} Graph $G=(V,E)$, set of colors $[q]$. \textsc{Solution:} A coloring of $G$ with $q$ colors with no monochromatic edges. \textsc{CSP formulation:} $V = [n]$, $D_v = [q]$ for every $v \in V$, $H_{uv} = \{(i,j) \ | \ i \in D_u, j \in D_v, i \neq j\}$ for every $uv \in E$, $\CC = \emptyset$. \hfill Decision \textbf{Comment:} Note that \textsc{Chromatic Number} $\chi(G)$ of $G$ is always upper bounded by $\tau+1$ since graphs of bounded treewidth are $\tau$-degenerate~\cite{Kloks:94} and $\tau$-degenerate graphs are $(\tau+1)$-colorable~\cite{SW:68}. Thus, if the goal is to determine $\chi(G)$, it suffice to find the smallest $q$ such that $CSP(Q)$ is non-empty. %\end{framed} \noindent \hrulefill %%% LIST COLORING \iffalse %\begin{framed} \problemline{List Coloring}{V}{$L^{\tau}n$}{$L^{\tau}n$} \textsc{Instance:} Graph $G=(V,E)$, colors $[q]$ and for every vertex $v \in V$ a list of permitted colors $L(v) \subseteq [q]$. \textsc{Solution:} A proper coloring of $G$ with $q$ colors such that for every $v \in V$, the color assigned to $v$, $c(v)$, is in $L(v)$. \textsc{CSP formulation:} $V = [n]$, $D_v = L(v)$ for all $v \in V$, $H_{uv} = \{(i,j) \ | \ i \in D_u, j \in D_v, i \neq j\}$ for all $uv \in E$, $\CC = \emptyset$.\hfill Decision \textbf{Comment:} $L = \max_{v \in V} |L(v)|$. $L$ is always upper-bounded by $q$; thus since this problem is a generalization of \textsc{Coloring}, the lower-bound of Lokshtanov et al. \cite{LMS:11} applies as well. %\end{framed} %%% PRECOLORING EXTENSION \hrulefill %\begin{framed} \problemline{Precoloring Extension}{V}{$q^{\tau}n$}{$q^{\tau}n$} \textsc{Instance:} Graph $G=(V,E)$, colors $[q]$ and for all vertices $v$ of a precolored set $V' \subseteq V$ a color $c(v) \in [q]$. \textsc{Solution:} A proper coloring of $G$ with $q$ colors such that for every $v \in V'$, the color assigned to $v$ is $c(v)$. \textsc{CSP formulation:} $V = [n]$, $D_v = \{c(v)\}$ for $v \in V'$ and $D_v = [q]$ for all $v \not\in V'$, $H_{uv} = \{(i,j) \ | \ i \in D_u, j \in D_v, i \neq j\}$ for all $uv \in E$, $\CC = \emptyset$.\hfill Decision \textbf{Comment:} This problem is a simple special case of \textsc{List Coloring}. %\end{framed} \hrulefill %%% H-COLORING / HOM %\begin{framed} \problemline{$H$-Coloring / Homomorphism}{V}{$q^{\tau}n$}{$q^{\tau}n$} \textsc{Instance:} Graph $G=(V,E)$, graph $H=(V_H, E_H)$, $|V_H| = q$, $E_H$ possibly containing loops. \textsc{Solution:} A mapping $f: V \rightarrow V_H$ such that $\forall uv \in E$ it holds that $f(u)f(v) \in E_H$. \textsc{CSP formulation:} $V = [n]$, $D_v = [q]$ for $v \in V$, $H_{uv} = \{(i,j) \ | \ i \in D_v, j \in D_u, ij \in E_H\}$ for all $uv \in E$, $\CC = \emptyset$.\hfill Decision \textbf{Comment:} For example, $G$ has a classical coloring with $q$ colors iff it has a $K_q$-coloring. %\end{framed} \hrulefill \fi %%% LIST HOMOMORPHISM %\begin{framed} \problemline{List-$H$-Coloring / List Homomorphism \cite{FH:98}}{V}{$L^\tau n$}{$L^\tau n$} \textsc{Instance:} Graph $G=(V,E)$, graph $H=(V_H, E_H)$ % $|V_H| = q$, possibly containing loops, and for every vertex $v \in V$ a set $L(v) \subseteq V_H$. %(We denote $L = \max_{v \in V} |L(v)|$) \textsc{Solution:} A mapping $f: V \rightarrow V_H$ such that $\forall uv \in E$ it holds that $f(u)f(v) \in E_H$ and $f(v) \in L(v)$ for every $v \in V$. \textsc{CSP formulation:} $V = [n]$, $D_v = L(v)$ for every $v \in V$, $H_{uv} = \{(i,j) \ | \ i \in D_u, j \in D_v, ij \in E_H\}$ for every $uv \in E$, $\CC = \emptyset$.\hfill Decision \textbf{Comment:} Note that the problems \textsc{List Coloring}, \textsc{Precoloring Extension} and \textsc{$H$-Coloring} (or \textsc{Graph Homomorphism}) are all special cases of this problem. The lower bound given by Lokshtanov et al. \cite{LMS:11} applies to all of them since \textsc{Coloring} is a special case of each of them. %\end{framed} \noindent \hrulefill %%% UNIQUE GAMES %\begin{framed} \problemlinealt{Unique Games \cite{Khot:02}}{\proj{id}}{$\Oh(t^\tau n)$}{---} \textsc{Instance:} Graph $G=(V,E)$, an integer $t \in \NN$, a permutation $\pi_e$ of order $t$ for every edge $e \in E$. \textsc{Solution:} A mapping $\ell: V \rightarrow [t]$ such that the number of edges $uv \in E$ with $\pi_{uv}(\ell(u)) = \ell(v)$ is maximized. \textsc{CSP formulation:} $V = [n]$, $D_v = [t]$ for every $v \in V$, $\HH = \emptyset$, $C_{uv} = \{(i,\pi_{uv}(i)) \ | \ i \in D_u \}$ for every edge $uv \in E$.\hfill \textsc{Max} \textbf{Comment:} The decision variant of this problem is not interesting as it is trivially solvable in polynomial time. %\end{framed} \noindent \hrulefill %%% MULTIWAY CUT %\begin{framed} \problemlinealt{Min Multiway Cut \cite{ACGKMP:99}}{\proj{E}}{$\Oh(t^\tau n)$}{$\Oh(t^\tau n)$} \textsc{Instance:} Graph $G=(V,E)$, an integer $t \in \NN$ and $t$ vertices $s_1, \dots, s_t \in V$. \textsc{Solution:} A partition of $V$ into sets $V_1, \dots, V_t$ such that for every $i$ we have $s_i \in V_i$ and the total number of edges between $V_i$ and $V_j$ for $i \neq j$ is minimized. \textsc{CSP formulation:} $V=[n]$, $D_v = [t]$ for every $v \in V$, $\HH = \emptyset$, $C_{uv} = \{(i,i) \ | \ i \in [t]\}$ for every edge $uv \in E$.\hfill \textsc{Max} \textbf{Comment:} Setting $z_v = i$ models vertex $v$ belonging to the set $V_i$. Not satisfying the constraint $C_{uv}$ means that the edge $uv$ belongs to the multiway cut. %\end{framed} \noindent \hrulefill %%% MAX CUT %\begin{framed} \problemline{Max Cut \cite{ACGKMP:99}}{E}{$2^\tau n$}{$2^\tau n$} \textsc{Instance:} Graph $G=(V,E)$. \textsc{Solution:} A partition of vertices into two sets $V_1, V_2$ such that the number of edges between $V_1$ and $V_2$ is maximized. \textsc{CSP formulation:} $V=[n]$, $D_v = \{0,1\}$ for every $v \in V$, $\HH = \emptyset$, $C_{uv} = \{(1,0), (0,1)\}$ for every edge $uv \in E$.\hfill \textsc{Max} \textbf{Comment:} The values $0,1$ model the vertex belonging to the set $V_1$ or $V_2$. If we replace maximization by minimization, the problem becomes \textsc{Edge Bipartization} (aka \textsc{Edge OCT}) problem which is a parametric dual of \textsc{Max~Cut}. %\end{framed} \noindent \hrulefill %%% VERTEX COVER %\begin{framed} \problemline{Min Vertex Cover \cite{ACGKMP:99}}{V}{$2^\tau n$}{$2^\tau n$} \textsc{Instance:} Graph $G=(V,E)$. \textsc{Solution:} A set of vertices $C \subseteq V$ of minimal size such that every edge contains a vertex $v \in C$ as at least one of its endpoints. \textsc{CSP formulation:} $V=[n]$, $D_v = \{0,1\}$ for every $v \in V$, $H_{uv} = \{(1,1), (0,1), (1,0)\}$ for every edge $uv \in E$, $C_v = \{0\}$ for every vertex $v\in V$. \hfill \textsc{Min} \textbf{Comment:} The values $1,0$ model the vertex belonging to $C$ or $V \setminus C$. % If we replace maximization by minimization, %set $C_v=\{1\}$ for every $v\in V$ and %$H_{uv} = \{(0,0), (0,1), (1,0)\}$ for every edge $uv \in E$, %the problem becomes the \textsc{Independent Set} problem which is a parametric dual of %\textsc{Vertex~Cover}. %\end{framed} \noindent \hrulefill %%% INDEPENDENT SET %\begin{framed} \problemline{Max Independent Set \cite{ACGKMP:99}}{V}{$2^\tau n$}{$2^\tau n$} \textsc{Instance:} Graph $G=(V,E)$. \textsc{Solution:} A set of vertices $C \subseteq V$ of maximal size such that no edge contains both its endpoints in $C$. \textsc{CSP formulation:} $V=[n]$, $D_v = \{0,1\}$ for every $v \in V$, $H_{uv} = \{(0,0), (0,1), (1,0)\}$ for every edge $uv \in E$, $C_v = \{1\}$ for every vertex $v\in V$. \hfill \textsc{Max} \textbf{Comment:} The values $1,0$ model the vertex belonging to $C$ or $V \setminus C$. %\end{framed} \noindent \hrulefill %%% OCT %\begin{framed} \problemlinealtt{Odd Cycle Transversal \cite{LMS:11}}{\proj{OCT} $\circ$ \proj{2}}{$\Oh(3^\tau n)$}{$\Oh(3^\tau n)$} %\cite{Yannakakis:78} \textsc{Instance:} Graph $G=(V,E)$. \textsc{Solution:} A subset of vertices $W \subseteq V$ of minimal size such that $G[V \setminus W]$ is a bipartite graph. \textsc{CSP formulation:} $V=[n]$, $D_v = \{0,1,2\}$ for every $v \in V$, $H_{uv} = \{0,1,2\}^2 \setminus \{(0,0), (1,1)\}$ for every edge $uv \in E$, $C_v = \{0,1\}$ for every $v \in V$.\hfill \textsc{Min} \textbf{Comment:} The values $0,1,2$ model the vertex belonging to either the first or the second partite of a bipartite graph, or the deletion set $W$. Satisfying the constraint $C_v$ corresponds to not putting $v$ in the deletion set $W$. Also known as \textsc{Vertex Bipartization}. The projection $\textrm{proj}_{OCT}:P(Q)\rightarrow \{0,1\}^V$ is defined as % $\textrm{proj}_{OCT}(y_1^0,y_1^1,y_1^2,y_2^0,y_2^1,y_2^2,\ldots, %y_n^0,y_n^1,y_n^2,\gg)=(y_1^2,y_2^2,\ldots,y_n^2)$. $$\textrm{proj}_{OCT}(y_1^0,y_1^1,y_1^2,y_2^0,y_2^1,y_2^2,\ldots, y_n^0,y_n^1,y_n^2,\gg)=(y_1^2,y_2^2,\ldots,y_n^2).$$ %\end{framed} \endgroup %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Open problems} %\paragraph{Open problems.} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% A natural research direction is to examine more closely the extension complexity for CSP and the specific graph problems on graphs with bounded treewidth, in particular, what are the best possible upper bounds? \iffalse Especially the correspondence between our extension complexity upper bounds and existing time complexity lower bounds in Section \ref{sec:problems} warrants a question: what is a natural problem whose time complexity does not match the extension complexity of its natural polytope when parameterized by treewidth? \fi \vspace{-2mm} \subsection*{Acknowledgments} The authors thank Hans Raj Tiwary and Ji\v r\'{\i} Sgall for stimulating discussions. \SquashBibFurther %\bibliographystyle{plain} \bibliographystyle{abbrv} \begin{thebibliography}{99} \bibitem{ACGKMP:99} G.~Ausiello, P.~Creczenzi, G.~Gambosi, V.~Kann, A.~Marchetti-Spaccamela, and M.~Protasi. \newblock {\em Complexity and Approximation; Combinatorial Optimization Problems and Their Approximability Properties}. \newblock Springer, 1999. \bibitem{BM:15} D.~{Bienstock} and G.~{Munoz}. \newblock {LP approximations to mixed-integer polynomial optimization problems}, \newblock \arxiv{1501.00288v14} \newblock July 2015. \bibitem{BO:04} D.~Bienstock and N.~{\"O}zbay. \newblock Tree-width and the sherali-adams operator. \newblock {\em Discrete Optimization}, 1(1):13--21, 2004. \bibitem{BB:14} A.~Buchanan and S.~Butenko. \newblock Tight extended formulations for independent set, 2014. \newblock Available on Optimization Online. \bibitem{CLRS:13} S.~O. Chan, J.~R. Lee, P.~Raghavendra, and D.~Steurer. \newblock Approximate constraint satisfaction requires large {LP} relaxations. \newblock In {\em Proc. of the 54th Annual {IEEE} Symposium on Foundations of Computer Science {(FOCS)}}, pages 350--359, 2013. \bibitem{CCZ:13} M.~Conforti, G.~Cornu{\'e}jols, and G.~Zambelli. \newblock Extended formulations in combinatorial optimization. \newblock {\em Annals OR}, 204(1):97--143, 2013. \bibitem{FH:98} T.~Feder and P.~Hell. \newblock List homomorphisms to reflexive graphs. \newblock {\em J. Comb. Theory, Ser. B}, 72(2):236--250, 1998. \bibitem{Freuder:90} E.~C. Freuder. \newblock Complexity of {$K$}-tree structured constraint satisfaction problems. \newblock In {\em Proc. of the 8th National Conference on Artificial Intelligence}, pages 4--9, 1990. \bibitem{GSS:01} M.~Grohe, T.~Schwentick, and L.~Segoufin. \newblock When is the evaluation of conjunctive queries tractable? \newblock In {\em Proc. of the 33rd Annual ACM Symposium on Theory of Computing (STOC)}, pages 657--666, 2001. \bibitem{Khot:02} S.~Khot. \newblock On the power of unique {2-Prover} {1-Round} games. \newblock In {\em Proc. of the 34th Annual {ACM} Symposium on Theory of Computing ({STOC})}, pages 767--775, 2002. \bibitem{Kloks:94} T.~Kloks. \newblock {\em Treewidth: Computations and Approximations}, volume 842 of {\em Lecture Notes in Computer Science}. \newblock Springer, 1994. \bibitem{Laurent:09} M.~Laurent. \newblock Sums of squares, moment matrices and optimization over polynomials. \newblock In {\em Emerging applications of algebraic geometry}, pages 157--270. Springer, 2009. \bibitem{LMS:11} D.~Lokshtanov, D.~Marx, and S.~Saurabh. \newblock Known algorithms on graphs on bounded treewidth are probably optimal. \newblock In {\em Proc. of the 22nd Annual {ACM}-{SIAM} Symposium on Discrete Algorithms {(SODA)}}, pages 777--789, 2011. \bibitem{Marx:10} D.~Marx. \newblock Can you beat treewidth? \newblock {\em Theory of Computing}, 6(1):85--112, 2010. \bibitem{Ragha:08} P.~Raghavendra. \newblock Optimal algorithms and inapproximability results for every {CSP}? \newblock In {\em Proc. of the 40th Annual {ACM} Symposium on Theory of Computing (STOC)}, pages 245--254, 2008. \bibitem{RS:09a} P.~Raghavendra and D.~Steurer. \newblock How to round any {CSP}. \newblock In {\em Proc. of the 50th Annual {IEEE} Symposium on Foundations of Computer Science {(FOCS)}}, pages 586--594, 2009. \bibitem{RS:09b} P.~Raghavendra and D.~Steurer. \newblock Integrality gaps for strong {SDP} relaxations of unique games. \newblock In {\em Proc. of the 50th Annual {IEEE} Symposium on Foundations of Computer Science {(FOCS)}}, pages 575--585, 2009. \bibitem{Roth:14} T.~Rothvo{\ss}. \newblock The matching polytope has exponential extension complexity. \newblock In {\em Proc. of the 46th ACM Symposium on Theory of Computing {(STOC)}}, pages 263--272, 2014. \bibitem{Schrijver:86} A.~Schrijver. \newblock {\em Theory of Linear and Integer Programming}. \newblock John Wiley \& Sons, 1986. \bibitem{Sellmann:08} M.~Sellmann. \newblock The polytope of tree-structured binary constraint satisfaction problems. \newblock In {\em Proc. of Integration of {AI} and {OR} Techniques in Constraint Programming for Combinatorial Optimization Problems ({CPAIOR})}, volume 5015 of {\em Lecture Notes in Computer Science}, pages 367--371. Springer, 2008. \bibitem{SML:07} M.~Sellmann, L.~Mercier, and D.~H. Leventhal. \newblock The linear programming polytope of binary constraint problems with bounded tree-width. \newblock In {\em Proc. of Integration of {AI} and {OR} Techniques in Constraint Programming for Combinatorial Optimization Problems ({CPAIOR})}, volume 4510 of {\em Lecture Notes in Computer Science}, pages 275--287. Springer, 2007. \bibitem{SW:68} G.~Szekeres and H.~S. Wilf. \newblock An inequality for the chromatic number of a graph. \newblock {\em Journal of Combinatorial Theory}, 4(1):1--3, 1968. \end{thebibliography} \end{document} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%