%============================================================================
% 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}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

