\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 Mixed structures in digraphs and completing orientations of partially oriented  graphs}

%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 Based on joint works with C-J. Casselgren, J. Huang, M. Kriesell, A. Maddaloni, S. Simonsen and A. Yeo,

\noindent \underline{J\o{}rgen Bang-Jensen} -- {\small University of Southern Denmark}



\vspace{2ex}

\noindent{\bf Abstract:}
This talk has two parts.
We first discuss the complexity of problems concerning mixed structures in digraphs. Examples of such problems are
\begin{itemize}
\item \cite{bangC31,bangJCT106,bangJGTta} Given a digraph $D$; does its underlying undirected digraph $UG(D)$ contain two (edge)-disjoint cycles $C$, $W$ so that $C$ is a directed cycle in $D$, whereas
 the edges of $W$ do not have to respect the orientation in $D$.
\item \cite{bangTCS438,bangAta} Given a digraph $D$; does $UG(D)$ have two edge-disjoint spanning trees $T_1,T_2$ so that $T_1$ is an out-branching from some root $s$ in $D$ (that is, $s$ can reach every other vertex using only the arcs of $T_1$), whereas the edges of $T_2$ do not have to respect the orientation in $D$.
\item \cite{bangTCS410} Given a digraph $D$ and vertices $s,t,u,v$ of $D$; does $UG(D)$ contain two (edge)-disjoint paths $P_1,P_2$ so that $P_1$ is a directed $(s,t)$-path in $D$ and $P_2$ is a path (not necessarily respecting the orientation of arcs of $D$) from $u$ to $v$ in $UG(D)$.

\item \cite{bangDAM193} Given a digraph $D$; does $UG(D)$ contain a 2-factor (spanning collection of disjoint cycles) $C_1,\ldots{},C_k$ so that $C_1$ is a directed cycle in $D$ but the other cycles need not be directed cycles in $D$.

\item \cite{bangTCS520} Mixed multicut: Given a digraph $D$ vertices (terminals) $t_1,t_2,\ldots{},t_r$ of $D$ and a mixed pattern graph $M=(\{t_1,t_2,\ldots{},t_r\},\hat{E}\cup\hat{A})$ and a natural number $k$; Does there exist a set $S$ of at most $k$ arcs of $D$ so that $D'=D-S$ satisfies the following: If $t_it_j\in \hat{E}$, then there is no path between $t_i$ and $t_j$ in $UG(D')$ and if $(t_i,t_j)\in \hat A$, then there is no directed $(t_i,t_j)$-path in $D'$.
\end{itemize}

In the second part of the talk we consider orientation completion problems. These can be defined as follows: Let ${\cal C}$ be a fixed class of digraphs (e.g. locally semicomplete, acyclic, having a directed cycle factor, strongly connected, locally transitive ...). The {\bf orientation completion problem} for the class ${\cal C}$ is to decide, for a given partically oriented graph $P=(V,E\cup A)$, whether we can orient the edges in $E$ so that the resulting digraph $D=(V,\stackrel{\rightarrow}{E}\cup A)$ belongs to the class $\cal C$. This is a common generalization of the recognition problems for the underlying graphs of digraphs and membership of a digraph class. The problem also has close relations to so-called {\bf representation extension} problems where we are given a partial geometric representation of an induced subgraph of  graph and the question is whether we can complete this to a full representation of the whole graph (see e.g. \cite{klavikLNCS6648,klavikLNCS8503}).

We will discuss recent results \cite{bangsub} on the problem when $\cal C$ is (a subclass of) the class of locally semicomplete digraphs. This includes the problem of orienting a semicomplete digraph as a locally transitive (every in- and out-neighbourhood is transitive) tournament.

 %Here write your abstract

%This paper is about ... Cite like that \cite{CCHPP}, \cite{Wol15}. 

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

\bibitem{bangDAM193} J. Bang-Jensen and C. J. Casselgren, Restricted cycle factors and arc-decompositions of digraphs, {\em Disc. Appl. Math.} {\bf 193} (2015) 80-93.

\bibitem{bangsub}J. Bang-Jensen, J. Huang and X. Zhu, Completing orientations of partially oriented graphs, arXiv 1509.01301v1

\bibitem{bangTCS410}J. Bang-Jensen and M. Kriesell, Disjoint directed and undirected paths and cycles in digraphs, {\em Theoretical Comp. Sci.} {410} (2009) 5138-5144. 

\bibitem{bangC31}J. Bang-Jensen and M. Kriesell, On the problem of finding disjojnt cycles and dicycles in a digraph, {\em Combinatorica} {\bf 31} (2011) 639-668.
\bibitem{bangJCT106} J. Bang-Jensen, M. Kriesell, A. Maddaloni and S. Simonsen, Vertex-disjoint directed and undirected cycles in general digraphs,
{\em J. Combin. Theory Ser B.} {\bf 106} (2014) 1-14.
\bibitem{bangJGTta} J. Bang-Jensen, M. Kriesell, A. Maddaloni and S. Simonsen,
Arc-disjoint directed and undirected cycles in digraphs,
{\em J. Graph Theory}, to appear.

\bibitem{bangAta} J. Bang-Jensen, S. Saurabh and S. Simonsen, Parameterized Algorithms for Non-separating Trees
and Branchings in Digraphs, {\em Algorithmica}, to appear.

\bibitem{bangTCS520} J. Bang-Jensen and A. Yeo, The complexity of multicut and mixed multicut problems in (di)graphs, {\em Theoretical Comp. Sci.} {\bf 520} (2014) 87-96.

\bibitem{bangTCS438} J. Bang-Jensen and A. Yeo, Arc-disjoint spanning subdigraphs in digraphs, {\em Theoretical Comp. Sci} {\bf 438} (2012) 48-54.

\bibitem{klavikLNCS8503} P. Klavik, J. Kratochv\'il, T. Otachi, I. Rutter. T. Saitoth., M. Saumell and T. Vysko\v{c}il, Extending partial representations of proper and unit interval graphs, in Ravi and G\o{}rtz (Eds.): SWAT 2014, LNCS 8503 (2014) 253-264.

\bibitem{klavikLNCS6648} P. Klavik, J. Kratochv\'il and T. Vysko\v{c}il,
 Extending partial representations of interval graphs, M. Ogihara and J. Tarui (Eds.): TAMC 2011, LNCS 6648 (2011) 276-285.

\end{thebibliography}
%\fi

\end{document}