\documentclass[11pt]{article}
\usepackage[russian,greek,english]{babel}
\usepackage{amsmath,ifthen,color,eurosym}
\usepackage{wrapfig,hyperref,cite}
\usepackage{latexsym,amsthm,amsmath,amssymb,url,cite}
\usepackage{fancyhdr}
\usepackage{graphicx}
\usepackage{stmaryrd,wasysym}
\usepackage{colortbl}
\usepackage[lined,boxed,commentsnumbered]{algorithm2e}
\usepackage[english]{babel}
\usepackage[utf8x]{inputenc}

\def\baselinestretch{1}


\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{corollary}{Corollary}
\newtheorem{claim}{Claim}
\newtheorem{observation}{Observation}
\newtheorem{proposition}{Proposition}

\setlength{\textheight}{22cm}
\setlength{\topmargin}{-1cm}
\setlength{\textwidth}{165mm}
\setlength{\oddsidemargin}{-3mm}
\setlength{\unitlength}{1mm}


%\renewcommand{\refname}{\small References}
\addto{\captionsenglish}{\renewcommand{\refname}{\normalsize
    References}}



%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%
%Put here the package you need, new commands, ...



%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%

\begin{document}
%1 page max !! 

%Write your title here: 
\noindent{\bf\Large Cutwidth in Tournament and Applications}

%List the authors as follows (you may underline the speaker, or just
%name the speaker, and mention your co-authors at the end, up to you):  
\noindent \underline{F. Barbero} -- {\small LIRMM, Université de Montpellier, Montpellier, France}\\
\noindent C. Paul -- {\small LIRMM, Université de Montpellier, Montpellier, France}


\vspace{2ex}

\noindent{\bf Abstract:} 
In the proof of the graph minor theorem~\cite{RS04}, Robertson and Seymour introduced the concept of tree decompositions and their associated width measures. Alternative width measures have been proposed to deal with directed graphs. But so far, the development of a minor theory for directed graphs is still limited. Only recently~\cite{CFS12}, semi-complete digraphs have been proved to be well-quasi ordered under the \emph{immersion} inclusion relation. The width measure associated to the immersion relation in semi-complete digraph is the \emph{cutwidth}~\cite{CS11,CFS12,Pil13} which is defined as follows. Let $D=(V,E)$ be a digraph and $\pi$ be an ordering of $V$.  The \emph{cutwidth} of $\pi$ is $$\mathsf{cw}(D,\pi)=\max_{0\leqslant i\leqslant |V|} |E(V_i,V\setminus V_i)|$$ where $V_i$ is the set containing the $i$ first vertices of $V$ in $\pi$ and $E(V\setminus V_i,V_i)$ denotes the set of arcs from $V\setminus V_i$ to $V_i$. The \emph{cutwidth} of $D$ is given by $$\mathsf{cw}(D)=\min_{\pi} \mathsf{cw}(D,\pi)$$

In this talk, we focus on \emph{tournaments}, a subclass of semi-complete digraphs. It is easy to observe that the cutwidth of a transitive tournament is $0$. It follows that the well-known \textsc{Feedback Arc Set in Tournament} ({\sf FAST}) problem can be expressed as the problem of deciding the existence of a subset of at most $k$ arcs whose reversal yields a cutwidth-$0$ tournament. A natural generalization is to consider the same question with respect to cutwidth-$c$ for a fixed constant $c$. We call this problem \textsc{$c$-Cutwidth Arc Reversal in Tournament} ($c$-{\sf CART}).

As a consequence of the facts that 1) tournaments are well-quasi ordered under the immersion inclusion relation ~\cite{CS11,CFS12} and 2) testing whether a digraph $H$ is included as an immersion in a semi-complete $D$ is {\sf FPT}~\cite{CFS12}, the $c$-{\sf CART} problem can be solved in non-uniform {\sf FPT} time. We show that $c$-{\sf CART} can be solved in single exponential {\sf FPT} time. The algorithm follows from the fact that any tournament $T$ such that $\mathsf{cw}(T)\geqslant c$, contains an induced subtournament $T'$ with $O(c^2)$ vertices such that $\mathsf{cw}(T')\geqslant c$. Moreover such a quadratic size obstruction can be found in polynomial time. Finally we observe that these obstructions also lead to single exponential {\sf FPT} algorithm for the vertex deletion version of the problem.



%\vspace{4cm}

%Let $D = (V,E)$ be a digraph. We denote by $E(X,Y) \subseteq E$ the set of edges directed from $X$ to $Y$. For an ordering $\pi$ of $V$, let $\pi[\alpha]$ be the first $\alpha$ vertices in the ordering $\pi$ and $cut(\pi,\alpha) = E(\pi[\alpha], V \setminus \pi[\alpha])$. Then, the \textit{cutwidth of $\pi$} is defined by $cw(\pi) = \underset{0 \le \alpha \le |V|}{\max} |cut(\pi,\alpha)|$ and the \textit{cutwidth $cw(G)$ of $G$} is the minimum width among all orderings of $V$.\\

%A \textit{semi-complete digraph} is such that for any pair $u,v \in V$, $uv \in E$ or $vu \in E$. Moreover, if we require that there is no parallel edges, the digraph is called a \textit{tournament}. %In his thesis, M.~Pilipczuk \cite{ThP} proved that %\textsc{Cutwidth in Semi-Complete} is FPT subexponential by giving a $2^{O(\sqrt{c \log(c)})}$-time parameterized algorithm. %He also showed how to get an order $\pi$  in polynomial time such that $cw(\pi) \le 16cw(D)^2 + 10cw(D) +1$, that is a %quadratic approximation. \\
%During this speak, I show that the restricted problem \textsc{Cutwidth in Tournament} is polynomial. As application, I prove that we may find an induced subtournament with cutwidth at least $c$ and at most $O(c^2)$ vertices in any tournament with cutwidth at least $c$ in polynomial time. Given a tournament $T = (V,E)$ and an integer $k$ as parameter, $c$-\textsc{Cutwidth Vertex Deletion in Tournament} is to decide whether there exists a set $W \subseteq V$, $|W| \le k$, such that the resulting digraph after deletion of $W$ in $T$ has cutwidth at most $c$ and $c$-\textsc{Cutwidth Arc Reversal in Tournament} is to decide whether there exists a set $F \subseteq E$, $|F| \le k$, such that the resulting digraph after reversal of $F$ in $T$ has cutwidth at most $c$. Using the containment result, I give FPT simple-exponential branching algorithms for both these problems.


%If you need a ref section, do it more or less like that : 
%\small
\begin{thebibliography}{1}

\bibitem{CFS12}
M. Chudnovsky and A. Fradkin and P. Seymour.
\newblock Tournament immersion and cutwidth.
\newblock {\em Journal of Combinatorial Theory, Series B},
\newblock 102:93-101, 2012.

\vspace{-0.2cm}
\bibitem{CS11}
M. Chudnovsky and P. Seymour.
\newblock A well-quasi-order for tournaments.
\newblock {\em Journal of Combinatorial Theory, Series B},
\newblock 101:47-53, 2011.

\vspace{-0.2cm}
\bibitem{Pil13}
M. Pilipczuk.
\newblock Tournaments and optimality: new results in parameterized complexity.
\newblock {\em University of Bergen},
\newblock 2013.

\vspace{-0.2cm}
\bibitem{RS04}
N. Roberston and P. Seymour
\newblock Graph minors {XX}: {W}agner's conjecture.
\newblock {\em Journal of Combinatorial Theory, Series B},
\newblock 92(2):325-357, 2004.
%@article{FS13,
%	Author = {A. Fradkin and P. Seymour},
%	Journal = {Journal of Combinatorial Theory, Series B},
%	Pages = {374-384},
%	Title = {Tournament pathwidth and topological containment},
%	Volume = {103},
%	Year = {2013}}

\end{thebibliography}
\end{document}