\documentclass[25pt, a0paper, portrait, margin=0mm, innermargin=15mm,
     blockverticalspace=15mm, colspace=15mm, subcolspace=8mm]{tikzposter} 

% LATEX PACKAGES
% --------------

\usepackage[utf8]{inputenc}
\usepackage{amsmath,amsthm,amssymb}
\usepackage{graphicx}  % package for inserting images, including .pdf
%\usepackage{adjustbox} % package for cropping images
%\usepackage[colorlinks=true, urlcolor=blue]{hyperref} % package for url and hyperlinks
% \usepackage{wrapfig}
% \usepackage{xspace}
% \usepackage{multicol}
% THEOREMS et al.
% ---------------


\newtheorem{theorem}{Theorem}
\newtheorem{corollary}{Corollary}
\theoremstyle{definition}
\newtheorem{definition}{Definition}
% My definitions

\newcommand{\td}{\operatorname{td}}
\newcommand{\pw}{\operatorname{pw}}
\newcommand{\tw}{\operatorname{tw}}

\newcommand{\R}{\mathbb{R}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Oh}{{\cal O}}

\newcommand{\FPT}{{\sf FPT}}
\newcommand{\W}{{\sf W}[1]}
\newcommand{\NP}{{\mathsf{NP}}}
\newcommand{\coNPpoly}{{\mathsf{coNP/poly}}}
\newcommand\disjcup{\mathbin{\dot{\cup}}}

% TITLE, AUTHORS, INSTITUTE
% -------------------------

\title{\parbox{\linewidth}{\centering Parameterized Complexity of Length-bounded Cuts \\ and Multicuts}}
\author{Pavel Dvo\v r\' ak, Du\v san Knop}

\institute{Faculty of Mathematics and Physics, Charles University in Prague, Czech Republic \\  
E-mail: \texttt{koblich@iuuk.mff.cuni.cz, knop@kam.mff.cuni.cz}}

% THEME SETTING
% -------------

\usetheme{Envelope}
\usecolorstyle{Default}
%\useblockstyle{Default}[colorPalette=Spain]
\usebackgroundstyle{VerticalGradation}
%\usetitlestyle{Wave}


% HEAD
% ----

\begin{document}
\maketitle


%\begin{multicols*}{2}
\begin{columns}

% ------------------------
% COLUMN 1 ---------------

\column{0.5}


% Scheduling models and assumed parameters
% ----
% 
\block{Length-bounded Cuts}
{
Let $G = (V,E)$ be a graph, $s,t \in V$ and $L \in \N$. 
A set $F \subseteq V$ is an $L$-bounded cut if a distance between $s$ and $t$ in a graph $(V, E \setminus F)$ is at least $L + 1$.

\vskip 0.5cm
\innerblock{Problem {\sc Minimum Length-bounded Cut (MLBC)}}
{
\begin{tabular}{ll}
 Instance: & Graph $G = (V,E)$, vertices $s,t \in V$ and integer $L \in \N$. \\
 Goal: & Find a minimum $L$-bounded cut $F \subseteq E$. \\
\end{tabular}
}
}

\block{Considered Graph Parameters}
{
% \begin{itemize}
%  \item Tree-width $\tw$
%  \item Path-width $\pw$
%  \item Tree-depth $\td$
% \end{itemize}

 \begin{definition}
The closure $\mathit{Clos}(F)$ of a forest $F$ is the graph obtained from $F$
by making every vertex adjacent to all of its ancestors. The \emph{tree-depth} $\td(G)$ of
a graph $G$ is one more than the minimum height of a rooted forest $F$ such that
$G\subseteq \mathit{Clos}(F).$ 
\end{definition}
}

\block{Previous Results}
{
\innerblock{Length-bounded Cut vs. Flow}
{
Maximum length-bounded flow is a dual problem to MLBC. 
I.e., we need to find an $L$-bounded flow $F$ to given graph $G$ such that $F$ can use only path of length at least $L + 1$.
These problems were introduced by Adámek and Koubek in 1971.
They showed that the max-flow min-cut duality does not hold anymore and also that integral capacities do not imply integral flow.
\begin{tikzfigure}[For $L = 4$ and unit capacities on all edges the size of maximum $L$-bounded flow is $3/2$ (green, red and blue path each with flow $1/2$) and the size of minimum $L$-bounded cut is 3 (edges $a$,$b$ and $c$). ]
\includegraphics{example.pdf}
\end{tikzfigure}

}
\vskip 0.5cm

\innerblock{{\sc Gapped Minimum Length-bounded Cut}}
{

\begin{tabular}{lp{32cm}}
 Instance: & Graph $G = (V,E)$, vertices $s,t \in V$ and integers $L, K \in \N$. \\
 Promise: & There is an $L$-bounded cut in $G$ of size exactly $K$ or every $L$-bounded cut in $G$ has more than $1.13K$ edges. \\
 Question: & Is there an $L$-bounded cut in $G$ of size exactly $K$? \\
\end{tabular}

\begin{theorem}[Baier et al., ACM Trans. Algorithms 7, 2010]
 {\sc Gapped MLBC} in $\NP$-hard even if $L \geq 4$ is constant.
\end{theorem}

}
}

\block{Framework for Refuting a Polynomial Kernel}
{
\begin{definition}[Polynomial equivalence relation]\label{d:polyRelation}
An equivalence relation $\mathcal{R}$ on the set $\Sigma^*$ is called {\em polynomial equivalence relation} if the following conditions are satisfied:
\begin{enumerate}
  \item There exists an algorithm such that, given strings $x,y\in\Sigma^*,$ resolves whether $x\equiv_\mathcal{R} y$ in time polynomial in $|x| + |y|$.
  \item Relation $\mathcal{R}$ restricted to the set $\Sigma^{\le n}$ has at most $p(n)$ equivalence classes for some polynomial $p(\cdot).$
\end{enumerate}
\end{definition}

\begin{definition}[AND-cross-composition]\label{d:crossComposition}
Let $L\subseteq\Sigma^*$ be an unparameterized language and $Q\subseteq\Sigma^*\times\N$ be a parameterized language. We say that $L$ {\em cross-composes} into $Q$ if there exists a polynomial equivalence relation $\mathcal{R}$ and an algorithm $\mathcal{A},$ called the AND-cross-composition, satisfying the following conditions. 
The algorithm $\mathcal{A}$ takes on input a sequence of strings $x_1,x_2,\dots,x_t\in\Sigma^*$ that are equivalent with respect to $\mathcal{R}$, runs in polynomial time in $\sum_{i = 1}^t |x_i|,$ and outputs one instance $(y,k)\in\Sigma^*\times\N$ such that:
\begin{enumerate}
  \item $k\le p(\max_{i = 1}^t |x_i|, \log t)$ for some polynomial $p(\cdot,\cdot),$ and
  \item $(y,k)\in Q$ if and only if $x_i\in L$ for all $i.$
\end{enumerate}
\end{definition}

\begin{theorem}[Drucker, FOCS, 2012]
\label{thm:PolyKernelFramework}
Assume that an $\NP$-hard language $L$ AND-cross-composes to a parameterized language $Q.$ Then $Q$ does not admit a polynomial compression, unless $\NP\subseteq\coNPpoly.$
\end{theorem}
}


 \column{0.5}





\block{Our Results}
{
\innerblock{{\FPT} algorithms}
{
\begin{theorem}
\label{thm:FptAlgorithm}
 MLBC problem can be solved in time $\Oh\bigl((L^{2\tw(G)^2}) \cdot n \bigr)$.
\end{theorem}

\begin{corollary}
\label{cor:Td}
 MLBC problem can be solved in time $\Oh\bigl((2^{2\td(G)^3}) \cdot n \bigr)$.
\end{corollary}

}
\vskip 0.5cm
\innerblock{Hardness}
{
\begin{theorem}
\label{thm:Hardness}
 MLBC is \W-hard when parameterized by path-width of the input graph.
\end{theorem}

\begin{theorem}
\label{thm:PolyKernel}
 MLBC parameterized by path-width of the input graph and $L$ does not admit a polynomial kernel, unless $\NP \not\subseteq \coNPpoly$.
\end{theorem}

}
}

\block{{\FPT} Proofs Ideas}
{
\innerblock{Theorem~\ref{thm:FptAlgorithm}}
{
Ingredients:
\begin{description}
 \item[Dynamic programming] over a tree decomposition of $G$.
 \item[Nice tree decomposition:] Every edge of $G$ is in some leaf of the tree decomposition.
 \item[Leafs:] Computing exact solution using Floyd-Warshal method.
 \item[Join nodes:] Joining two partial solutions over a cut.
 \item[Forget/introduce nodes:] nothing interesting here.
\end{description}
}
\vskip 0.5cm

\innerblock{Corollary~\ref{cor:Td}}
{
We use only two bounds:
\begin{itemize}
 \item $\tw(G) \leq \td(G)$ for every graph $G$.
 \item The longest path in any graph $G$ length at most $2^{\td(G)}$, therefore we can suppose $L \leq 2^{\td(G)}$ .
\end{itemize}
}
}

\block{Hardness Proofs Ideas}
{
\innerblock{Theorem~\ref{thm:Hardness}}
{
Fpt-redution from {\sc Mutlicolor Clique}, which is \W-hard:

\begin{tabular}{ll}
Instance: & $k$-partite graph $G=(V_1 \disjcup V_2 \disjcup \dots \disjcup V_k,E)$\\ 
Parameter: & $k$\\ 
Goal: & find a clique of the size $k$
\end{tabular}

In the $k$-{\sc Multicolor Clique} problem we need to select exactly one vertex from each independent set $V_i$ and make sure that all selected vertices are adjacent.

Ideas:
\begin{itemize}
 \item We have a basic gadget $g_v$ for every vertex $v$.
 \item We connect gadgets $g_v$ for every $v \in V_i$ into a path $P_i$. 
 \item The path $P_i$ is cut in the gadget $g_v$ if and only if the vertex $v \in V_i$ is selected into the clique.
\end{itemize}

}
\vskip 0.5cm
\innerblock{Theorem~\ref{thm:PolyKernel}}
{
By framework of AND-cross-composition (Theorem~\ref{thm:PolyKernelFramework}):
\begin{description}
 \item[$\NP$-hard problem:] {\sc Gapped MLBC} for $L = 4$.
 \item[Polynomial equivalence relation ${\cal R}$]: $(G_1,s_1,t_1,4,K_1) \sim_{\cal R} (G_2,s_2,t_2,4,K_2)$ if and only if $|V(G_1)| = |V(G_2)| = n$ and $K_1 = K_2 = K'$.
 \item[AND-cross-composition:] We take $r$ equivalence instances of {\sc Gapped MLBC} $(G_i,s_i,t_i,4,K')$ and create a {\sc Gapped MLBC} instance $(G,4,s,t,rK)$ where the graph $G$ is a disjoint union of $G_i$ with unifying the vertices $s_i$ into $s$ and the vertices $t_i$ into $t$.
 \item[Path-width] of $G$ is bounded by $n$.
 \item[Correctness:] The graph $G$ has 4-bounded cut of size $rK$ if and only if all graphs $G_i$ have 4-bounded cuts of size $K'$.

\end{description}
}
}



\end{columns}
%\end{multicols*}

% ----------------
\end{document}
\endinput
%%
%% End of file 
