Antistrong digraphs
An antidirected trail in a digraph is a trail (a walk with no arc repeated) in which the arcs alternate between forward and backward arcs. An antidirected path is an antidirected trail where no vertex is repeated. We show that it is NP-complete to decide whether two vertices $x,y$ in a digraph are connected by an antidirected path, while one can decide in linear time whether they are connected by an antidirected trail. A digraph $D$ is antistrong if it contains an antidirected $(x,y)$-trail starting and ending with a forward arc for every choice of $x,y\in V(D)$. We show that antistrong connectivity can be decided in linear time. We discuss relations between antistrong connectivity and other properties of a digraph and show that the arc-minimal antistrong spanning subgraphs of a digraph are the bases of a matroid on its arc-set. We show that one can determine in polynomial time the minimum number of new arcs whose addition to $D$ makes the resulting digraph the arc-disjoint union of $k$ antistrong digraphs. In particular, we determine the minimum number of new arcs which need to be added to a digraph to make it antistrong. We use results from matroid theory to characterize graphs which have an antistrong orientation and give a polynomial time algorithm for constructing such an orientation when it exists. This immediately gives analogous results for graphs which have a connected bipartite 2-detachment. Finally, we study arc-decompositions of antistrong digraphs and pose several problems and conjectures.
\section{Introduction}

We refer the reader to~\cite{bang2009} for notation and terminology
not explicitly defined in this paper. An {\bf antidirected path} in
a digraph $D$ is a path in which the arcs alternate between forward
and backward arcs. The digraph $D$ is said to be {\bf anticonnected}
if it contains an antidirected path between $x$ and $y$ for every
pair of distinct vertices $x,y$ of $D$. Anticonnected digraphs were
studied in~\cite{chartrandUM51}, where several properties such as
antihamiltonian connectivity have been considered.
We will show  in Theorem~\ref{antipathcheck} below that it is
NP-complete to decide whether a given digraph contains an antidirected
path between given vertices.

Our main purpose is to introduce a related connectivity property
based on the concept of a {\bf forward antidirected trail}, i.~e.~a
walk with no arc repeated which begins and ends with a forward arc
and in which the arcs alternate between forward and backward arcs. A
digraph $D$ is {\bf antistrong} if it has at least three vertices
and contains a forward antidirected $(x,y)$-trail for every pair of
distinct
vertices $x,y$ of $D$. We say that
$D$ is {\bf $k$-arc-antistrong} if it has at least three vertices
and contains $k$ arc-disjoint forward antidirected $(x,y)$-trails
for all distinct $x,y \in V(D)$.




\medskip

The paper is organized as follows. First we show that, from an
algorithmic point of view, anticonnectivity is not an easy concept to
work with, since deciding whether a digraph contains an antidirected
path between a given pair of vertices is NP-complete. Then we move to
the main topic of the paper, antistrong connectivity, and show that
this relaxed version of anticonnectivity is easy to check
algorithmically. In fact, we show in Section~\ref{ASsec} that there is
a close relation between antistrong connectivity of a digraph $D$ and
its so called bipartite representation $B(D)$, namely $D$ is
antistrong if and only if $B(D)$ is connected. This allows us in
Section~\ref{ASaugsec} to find the minimum number of new arcs we need
to add to a digraph which is not antistrong so that the resulting
digraph is antistrong. Furthermore, using the bipartite representation
we show in Section~\ref{matroidsec} that the arc-minimal antistrong
spanning subdigraphs of a digraph $D$ form the bases of a matroid on
the arc-set of $D$.
More generally, we show that the subsets of $A$ which contain no
closed antidirected trails are the independent sets of a matroid on
$A$. In Section~\ref{ASorsec} we study the problem of deciding whether
a given undirected graph has an antistrong orientation. We show how to
reduce this problem to a matroid problem and give a characterization
of those graphs that have an antistrong orientation. For the convenience of readers who are not familiar with matroids, we also provide, as an appendix,  a purely graph theoretical proof  of the key step which is Lemma \ref{lem:mat3}. Both proofs can be converted
to  polynomial time algorithms which either finds an antistrong
orientation of the given input graph $G$ or produce a certificate
which shows that $G$ has no such orientation. In
Section~\ref{detachsec} we show that being orientable as an antistrong
digraph can be expressed in terms of connected 2-detachments of graphs
(every vertex $v$ is replaced by two copies $v',v''$ and every
original edge $uv$ becomes an edge between precisely one of the 4
possible pairs $u'v',u'v'',u''v',u''v''$) with the extra requirement
that the 2-detachment is bipartite and contains no edge of the form
$u'v'$ or $u''v''$. This imediately leads to a characterization of
graphs having such a 2-detachment.  Finally, in Section~\ref{nosepsec}
we show that one can decide in polynomial time whether a given digraph
$D$ has a spanning antistrong subdigraph $D'$ so that $D-A(D')$ is
connected in the underlying sense (while it is NP-hard to decide
whether a given digraph contains a non-separating strong spanning
subdigraph).\\ We conclude the paper with some remarks and open
problems.



\iffalse
\section{Notation and Terminology}

We follow the notation from~\cite{bang2009}. We denote the vertex
set and arc set of a digraph $D$ by $V(D)$ and $A(D)$, respectively
and write $D=(V,A)$ where $V=V(D)$ and $A=A(D)$. Unless otherwise
specified, the numbers $n$ and $m$ will always be used to denote the
number of vertices and arcs/edges, respectively, in the digraph or
graph in question. Digraphs and graphs will not have parallel arcs
or edges unless explicitly stated. We will use the notation $[k]$
for the set of integers $\{1,2,\ldots{},k\}$.

The {\bf underlying graph} of a digraph $D$, denoted $U\!G(D)$, is
obtained from $D$ by suppressing the orientation of each arc and
deleting one copy from parallel edges arising from 2-cycles in $D$.
A digraph $D$ is {\bf connected} if $UG(D)$ is a connected graph.
When $xy$ is an arc of $D$ we say that $x$ is the {\bf tail} and $y$
the {\bf head} of the arc.  For a digraph $D=(V,A)$ the
{\bf out-degree} $d^+_D(x)$ and {\bf in-degree} $d^-_D(x)$ of a
vertex $x\in V$ is the number of arcs in $A$ of the form $xy$ or $yx$, respectively.
A vertex of in-degree zero or out-degree zero is a
{\bf source} or a {\bf sink}, respectively.


An arc $vw$ is {\bf forward} in a path/trail/walk $v_1v_2\ldots{}v_k$
if we have $v=v_i,w=v_{i+1}$ for some $i\in \{1,\dots,k-1\}$. It is {\bf
  backward} if we have $w=v_i,v=v_{i+1}$ for some $i\in \{1,\dots,k-1\}$.  An
{\bf antidirected trail} in a digraph is a trail (a walk with no arc
repeated) in which the arcs alternate between forward and backward
arcs. An {\bf antidirected path} is an antidirected trail where no
vertex is repeated.  An {\bf antidirected cycle} is the digraph we
obtain by identifying the end vertices of an antidirected path with an
even number of arcs.  An antidirected trail $T$ is a {\bf forward}
antidirected trail if it starts {\em and} ends with a forward arc.

Two vertices $x,y$ in a digraph $D$ are {\bf anticonnected} if $D$
contains an antidirected path with end vertices $x$ and $y$.  A
digraph $D$ is {\bf anticonnected} if it contains an antidirected path
between $x$ and $y$ for every pair of distinct vertices $x,y$ of
$D$. Anticonnected digraphs were studied in~\cite{chartrandUM51}, where
several properties such as antihamiltonian connectivity have been considered.
It is easy to see that being anticonnected is not an equivalence
relation on the vertex set of a digraph as we may have an antidirected
path between $x$ and $y$ and between $y$ and $z$ but none between $x$
and $z$. In fact, as we shall show below in
Theorem~\ref{antipathcheck}, it is NP-complete to decide whether
there exists an antidirected $(x,y)$-path in a digraph $D$.

The purpose of this paper is to introduce a new notion, antistrong
connectivity, which turns out to take polynomial time to check and show that
this has connections to several important topics in combinatorial
optimization.  A digraph $D$ is {\bf antistrong} if it contains
a forward antidirected $(x,y)$-trail for every choice of $x,y\in
V(D)$. Let us call $D$ {\bf $k$-arc-antistrong} if it contains $k$
arc-disjoint forward antidirected $(x,y)$-trails for all $x,y \in V(D)$.\\

{\bf More to be written here}

\fi

\section{Anticonnectivity}\label{anticonsec}
It was shown in~\cite{chartrandUM51} that every connected graph $G$
has an anticonnected orientation. This can be seen by considering a
breath first search tree rooted at some vertex $r$. Let
$\{r\}=L_0,L_1,L_2,\ldots{},L_k$ be the distance classes of $G$.
Orient all edges between $r$ and $L_1$ from $r$ to these vertices,
orient all edges between $L_1\cup L_3$ and $L_2$ from $L_2$ to
$L_1\cup L_3$, orient all edges from $L_4$ to $L_3\cup L_5$ etc.
Finally, orient all the remaining, not yet oriented edges
arbitrarily.


\iffalse

 There are various results in the literature on antidirected
cycles

\begin{itemize}
\item It is NP-complete to decide whether $D$ has an antidirected
  2-factor~\cite{diwanDM311}.
\item Every digraph with minimum semidegree (min of in and out-degree)
  at least $\frac{24}{46}n$ has an antidirected
  2-factor~\cite{diwanDM311}.
\item In~\cite{bogdanowiszAMS6} there are given necessary and sufficient conditions
  under which a circulant digraph $D$ can be decomposed into $k$
  pairwise arc-disjoint antidirected Hamilton cycles, each induced by
  two jumps.\mmk{What is a jump?}
\end{itemize}

\fi

We will show that it is NP-complete to decide if a digraph has an
antidirected path between two given vertices. We need the following
result which is not new, as it follows from a result in~\cite{gabowITSE2} on the vertex analogue,  but we include a new and short proof for
completeness.
\begin{theorem}
\label{avoidpairs}
It is NP-complete to decide for a given graph $G=(V,E)$, two specified
vertices $x,y\in V$ and pairs of distinct edges ${\cal
  P}=\{(e_1,f_1),(e_2,f_2),\ldots{},(e_p,f_p)\}$, all from $E$,
whether $G$ has an $(x,y)$-path which avoids at least one edge from
each pair in $\cal P$.
\end{theorem}

{\bf Proof: } We first slightly modify a very useful polynomial reduction, used in many papers such
as~\cite{bangTCS438}, from
3-SAT to a simple path problem and then show how to extend this to a reduction
from 3-SAT to the problem above. For simplicity our proof uses
multigraphs but it is easy to change to graphs.

Let $W[u,v,p,q]$ be the graph (the variable gadget) with vertices
$\{u,v,y_1,y_2,\dots{}y_p,z_1,z_2,\ldots z_q\}$ and the edges of the
two $(u,v)$-paths $uy_1y_2\ldots{}y_pv, uz_1z_2\ldots{}z_qv$.
\\
Let ${\cal F}$ be an instance of 3-SAT with variables
$x_1,x_2,\ldots{},x_n$ and clauses $C_1,C_2,\ldots{},C_m$.
The ordering of the clauses $C_1,C_2,\ldots{},C_m$ induces an ordering
of the occurrences of a variable $x$ and its negation $\overline{x}$ in
these. With each variable $x_i$ we associate a copy of
$W[u_i,v_i,p_i+1,q_i+1]$ where $x_i$ occurs $p_i$ times and
$\overline{x_i}$ occurs $q_i$ times in the clauses of $\cal F$. Identify
end vertices of these graphs by setting $v_i=u_{i+1}$ for
$i=1,2,\ldots{},n-1$. Let $s=u_1$ and $t=v_n$ and denote by $G'$ the
resulting graph. In $G'$ we respectively denote by $y_{i,j}$ and
$z_{i,j}$ the vertices $y_j$ and $z_j$ in the copy of $W$ associated with
the variable $x_i$.
\\
Next, for each clause $C_i$ we associate this with 3 edges from $G'$
as follows: assume $C_i$ contains variables $x_j,x_k,x_l$ (negated or
not). If $x_j$ is not negated in $C_i$ and this is the $r$th copy of
$x_j$ (in the order of the clauses that use $x_j$), then we associate
$C_i$ with the edge $y_{j,r}y_{j,r+1}$ and if $C_i$ contains
$\overline{x_j}$ and this is the $k$th occurrence of $\overline{x_j}$, then we
associate $C_i$ with the edge $z_{j,k}z_{j,k+1}$. We make similar
associations for the other two literals of $C_i$. Thus for each clause
$C_i$ we now have a set $E_i$ of three distinct edges
$e_{i,1},e_{i,2},e_{i,3}$ from $G'$ and $E_i\cap E_j=\emptyset$ for
$i\neq j$.
\\
Now it is easy to check that $G'$ has an $(s,t)$-path which avoids at
least one edge from each of the sets $E_1,E_2,\ldots{},E_m$ if and
only if $\cal F$ is satisfiable. Indeed, the $(s,t)$-path goes through the
`$z$-vertices' of the copy of $W$ associated with $x_i$ if
and only if  $x_i$ is
set to {\sc true} to satisfy $\cal F$.

Let us go back to the original problem. Let $H$ be the multigraph
consisting of vertices $c_0,c_1,\ldots{},c_m$ and three edges (denoted
$f_{i,1},f_{i,2},f_{i,3}$) from $c_{i-1}$ to $c_i$ for $i\in \{1,\dots,m\}$.
Let $G$ denote the multigraph we obtain from $G'$ and $H$ by identifying
$t$ and $c_0$. Let $x=s$ and $y=c_m$.  Finally, form three disjoint
pairs of arcs $(e_{i,1},f_{i,1}), (e_{i,2},f_{i,2}),(e_{i,3},f_{i,3})$
between $E_i$ and $\{f_{i,1},f_{i,2},f_{i,3}\}$ for every $i \in \{1 \dots m\}$.\\ By the observations
above it is easy to check that $G$ has an $(x,y)$-path which avoids
at least one arc from each of the forbidden pairs if and only if $\cal F$ is satisfiable. \hfill$\diamond$\\\vspace{2mm}


\begin{theorem}
\label{antipathcheck}
It is NP-complete to decide whether a given digraph contains an
antidirected path between given vertices $x,y$.
\end{theorem}

{\bf Proof: } The following proof is due to Anders Yeo (private communication,
April 2014).  Let $G=(V,E)$ be a graph with two specified vertices
$x,y\in V$ and pairs of distinct edges ${\cal
  P}=\{(e_1,f_1),(e_2,f_2),\ldots{},(e_p,f_p)\}$, all from $E$. We
will show how to construct a digraph $D_G$ with specified vertices
$s,t$ such that $D_G$ contains an antidirected $(s,t)$-path if and
only if $G$ has an $(x,y)$-path which avoids at least one edge from
each pair in $\cal P$. Since the construction can be done in
polynomial time this and Theorem~\ref{avoidpairs} will imply the
result.

Let $k$ be the maximum number of pairs in ${\cal P}$ involving the
same edge from $E$. Let $P$ be an antidirected path of length $2k+2$
which starts with a forward arc (and hence ends with a backward
arc). Now construct $D_G$ as follows: start from $G$ and first replace
every edge $uv$ with a private copy $P_{uv}$ of $P$ (no internal
vertices are common to two such paths). Then for each pair
$(e_i,f_i)\in {\cal P}$ we identify one sink of $P_{e_i}$ with one
source of $P_{f_i}$ so that the resulting vertex has in- and out-degree $2$.
By the choice of the length of $P$ we can identify in pairs, i.~e.~no three vertices will be identified.
Note that all the original vertices of $G$ will be sources in $D_G$.
The remaining (new vertices) will be called {\it internal} vertices.

Finally let $s=x$ and $t=y$. We claim that $D_G$ has an antidirected
$(s,t)$-path if and only if $G$ has an $(x,y)$-path which uses at most
one edge from each of the pairs in ${\cal P}$. Suppose first that
$xx_1x_2\ldots{}x_{r-1}x_ry$ is a path in $G$ which uses at most one
edge from each of the pairs in ${\cal P}$. Then
$P_{xx_1}P_{x_1x_2}\ldots{}P_{x_{r-1}x_r}P_{x_ry}$ is an antidirected
$(s,t)$-path in $D_G$ (no vertex is repeated since the identifications
above where only done for paths corresponding to pairs in ${\cal
  P}$). Conversely, suppose $D_G$ contains an antidirected
$(s,t)$-path $Q$.
By the way we identified vertex pairs according to ${\cal P}$, the internal
vertices have in- and out-degree at most $2$, and if an internal vertex
is on two paths $P_{e_i},P_{f_i}$ then it has both its in-neighbours
on $P_{e_i}$ and both its out-neighbours on $P_{f_i}$. This implies
that $Q$ will either completely traverse a path $P_{e_i}$ or not touch
any internal vertex of that path. Hence it cannot traverse both
$P_{e_i}$ and $P_{f_i}$ if $(e_i,f_i)\in {\cal P}$, and it follows that
if we delete all internal vertices of $Q$ and add back the edges of
$G$ corresponding to each of the traversed paths, we obtain an
$(x,y)$-path in $G$ that uses at most one edge from each pair in
${\cal P}$. \hfill$\diamond$\\\vspace{2mm}



\section{Properties of antistrong digraphs}\label{ASsec}
It follows from our definition that every pair of vertices of an antistrong digraph is joined by a trail of odd length. This immediately gives

\begin{lemma}
\label{nobipAS}
No bipartite digraph is antistrong.
\end{lemma}

For every digraph $D$ we can associate an undirected bipartite graph
which contains all the information we need to study antistrong
connectivity.  The {\bf bipartite representation}~\cite[Page
  19]{bang2009} of a digraph $D=(V,A)$ is the bipartite graph
$B(D)=(V'\cup V'',E)$, where $V'=\{v'|v\in V\}$, $V''=\{v''|v\in V\}$
and $E=\{v'w''|vw\in A\}$.

\begin{proposition}
\label{ASchar}
Let $D=(V,A)$ be a digraph with $|V|\ge 3$. The following are equivalent.
\begin{enumerate}
\item $D$ is antistrong
\item $B(D)$ is connected.
\item For every choice of distinct
vertices $x,y$, the digraph $D$ contains both an
  antidirected $(x,y)$-trail $T_{x,y}$ of even length starting on a
  forward arc and an antidirected $(x,y)$-trail $\bar{T}_{x,y}$ of
  even length starting on a backward arc.
\end{enumerate}
\end{proposition}


{\bf Proof: } Suppose (a) holds. Then, following the edges corresponding to the
arcs of a forward antidirected $(x,y)$-trail, $B(D)$ contains an
$(x',y'')$-path for every pair of distinct vertices $x,y\in V$. Now,
if $x$ and $y$ are distinct vertices of $D$, we choose a third vertex
$z$ in $D$ ($z\neq x$ and $z\neq y$), and the union of an
$(x',z'')$-path and a $(z'',y')$-path contains an $(x',y')$-path in
$B(D)$. Similarly we obtain an $(x'',y'')$-path in $B(D)$ for every
pair of distinct vertices $x,y\in V$. Finally, for any $x\in V$, an
$(x',x'')$-path in $B(D)$ can be found in the union of an $(x',y')$-path
and a $(y',x'')$-path, where $y$ is a vertex of $D$ distinct from $x$.
Hence $(a)\Rightarrow{}(b)$ holds. Conversely, $(b)\Rightarrow{}(a)$ holds, since
any $(x',y'')$-path in $B(D)$ corresponds to a forward antidirected
$(x,y)$-path in $D$ which starts and ends with a forward arc.\\
Now to prove $(b)\Rightarrow{}(c)$, it suffices to remark that
$T_{x,y}$ and $\bar{T}_{x,y}$ correspond to an
$(x',y')$-path and an $(x'',y'')$-path in $B(D)$, respectively.
Finally, to see that $(c)\Rightarrow{}(b)$ holds, it suffices to show that if (c) holds, then
$B(D)$ contains an $(x',y'')$-path for all $x,y\in V$ (possibly
equal). This follows by considering a neighbour $z''$ of $x'$ and a
$(z'',y'')$-path in $B(D)$.  \hfill$\diamond$\\\vspace{2mm}

Proposition~\ref{ASchar} immediately implies the next result.
\begin{corollary}
\label{checkAS}
One can check in linear time whether a digraph is antistrong.
\end{corollary}






Recall that a digraph is {\bf $\mathbf{k}$-strong} if it has at least
$k+1$ vertices and it remains strong after deletion of any set of at
most $k-1$ vertices.  The digraph obtained from three
disjoint independent sets $X,Y,Z$ each of
size $k$ by adding all arcs from $X$ to $Y$, from $Y$ to $Z$, and from $Z$ to $X$ is $k$-strong. However,
$B(D)$ has three connected components. This shows that no condition
on the strong connectivity will
guarantee that a digraph is antistrong.\\

Recall that $D$ is $k$-arc-antistrong if it contains $k$ arc-disjoint
forward antidirected $(x,y)$-trails for every ordered pair of distinct
vertices $x,y$.  We can check in time $O(mk)$ whether a digraph has
$k$ arc-disjoint forward antidirected $(x,y)$-trails for given
vertices $x,y$, because they correspond to edge-disjoint $(x',y'')$-paths in
$B(D)$ whose existence can be checked by using flows, see
e.g.~\cite[Section 5.5]{bang2009}. So we can check in polynomial time
if a digraph is $k$-arc-antistrong.

\begin{theorem}
If $D$ is $2k$-arc-antistrong, then it contains
$k$ arc-disjoint antistrong spanning subdigraphs.
\end{theorem}
{\bf Proof: } Since $D$ is $2k$-arc-antistrong, $B(D)$ is $2k$-edge-connected.
We can now use Nash-Williams'~theorem
(see~\cite[Theorem~9.4.2]{bang2009} for instance) to deduce that
$B(D)$ has $k$ edge-disjoint spanning trees.
Proposition~\ref{ASchar} now gives the required  set of $k$
arc-disjoint antistrong spanning subdigraphs of $D$.
\hfill$\diamond$\\\vspace{2mm}

\begin{theorem}
There exists a polynomial time algorithm which for a given digraph $D$ and a
natural number $k$ either returns $k$ arc-disjoint spanning antistrong
subdigraphs
of $D$ or correctly answers that
no such set exists.
\end{theorem}

{\bf Proof: } This follows from the fact that such subdigraphs exist if and
only if $B(D)$ has $k$ edge-disjoint spanning trees, and the
existence of such trees can be checked via Edmonds' algorithm for
matroid partition~\cite{edmondsJRNBS69}. \hfill$\diamond$\\\vspace{2mm}

The corresponding problem for containing two arc-disjoint {\em
strong} spanning subdigraphs is NP-complete (see
e.g.~\cite[Theorem~13.10.1]{bang2009}).

\begin{theorem}
\label{twospstrongD} It is NP-complete to decide whether a digraph
$D$ contains two spanning strong subdigraphs $D_1,D_2$ which are
arc-disjoint.
\end{theorem}

\section{Antistrong connectivity augmentation}\label{ASaugsec}
Note that
every complete digraph on at least 3
vertices is antistrong. Hence it is natural to ask for the minimum
number of new arcs one has to add to a digraph in order to make it
antistrong.

\begin{theorem}
\label{augmenttoAS}
There exists a polynomial time algorithm for finding, for a given digraph
$D=(V,A)$ on at least 3 vertices, a minimum cardinality set of new arcs
$F$ such that the digraph $D'=(V,A \dot{\cup} F)$ is antistrong.
\end{theorem}
{\bf Proof: } Let $D$ be a digraph on $n\geq 3$ vertices which is not
antistrong. By Proposition~\ref{ASchar}, its bipartite representation
$B(D)$ is not connected. First observe that in the bipartite
representation each new arc added to $D$ will correspond to an arc
from a vertex $u'$ of $V'$ to a vertex $v''\in V''$ such that $u\neq
v$ back in $V$. So we are looking for the minimum number of new edges
of type $u'v''$ with $u\neq v$ whose addition to $B(D)$ makes it
connected while preserving the bipartition $V',V''$. Note that, as long as
$n\geq 3$, in which case $B(D)$ has at least 6 vertices, we can always
obtain a connected graph by adding edges that are legal according to
the definition above.  So the number of edges we need is exactly the
number of connected components of $B(D)$ minus one.\footnote{This
  number is also equal to $(2n-1)-r(A)$ where $r$ is the rank function
  of the matroid $M(D)$ which we define in Section~\ref{matroidsec}.}

To find an optimal augmentation we add all missing edges between
$V'$ and $V''$ to $B(D)$, except for those of the form $v'v''$ and
give the new edges cost 1, while all original edges get cost 0. Now find a
minimum weight spanning tree in the resulting weighted complete
bipartite graph. The edges of cost 1 correspond to an optimal
augmenting set back in $D$. \hfill$\diamond$\\\vspace{2mm}

The complexity of the analogous question for $k$-arc-antistrong
connectivity is open.\\


\begin{problem}
\label{addtogetkAS} Given a digraph $D$ and a natural number $k$,
can we find in polynomial time a minimum cardinality set of new arcs
whose addition to $D$ results in a digraph $D'$ which is
$k$-arc-antistrong?
\end{problem}

Problem~\ref{addtogetkAS} is easily seen to be equivalent to the
following problem on edge-connectivity augmentation of bipartite
graphs.

\begin{problem}
\label{bipaug}
Given a natural number $k$ and a bipartite graph $B=(X,Y,E)$ with
$|X|=|Y|=p$ which admits a perfect matching $M$ in its bipartite
complement, find a minimum cardinality set of new edges $F$ such that
$F\cap M=\emptyset$ and $B+F$ is $k$-edge-connected and bipartite with the
same bipartition as $B$.
\end{problem}


Theorem~\ref{augmenttoAS} can be extended to find the minimum number
of new arcs whose addition to $D$ gives a digraph with $k$
arc-disjoint antistrong spanning subdigraphs $D_1,\ldots{},D_k$,
provided that $V(D)$ is large enough to allow the existence of $k$
such subdigraphs. Note that since each $D_i$ needs at least $2n-1$
arcs and we do not allow parallel arcs, we need $n$ to be large
enough, in particular we must have $n\geq 2k+1$.

\begin{theorem}
\label{addtogetkdisjointAS}
There exists a polynomial time algorithm for determining, for a given
digraph $D$ on at least 3 vertices, whether one can add some edges to
$D$ such that the resulting digraph is simple (no parallel arcs) and
has $k$ arc-disjoint antistrong spanning subdigraphs. In the case when
such a set exists, the algorithm will return a minimum cardinality set
of arcs $A'$ such that $D'=(V,A\cup A')$ contains $k$ arc-disjoint
antistrong spanning subdigraphs.
\end{theorem}
{\bf Proof: } This follows from the fact that the minimum set of new arcs is
exactly the minimum number of new edges, not of the form $v'v''$ that
we have to add to $B(D)$ such that the resulting bipartite graph is simple and
has $k$ edge-disjoint spanning trees. This number can be found using
matroid techniques as follows. Add all missing edges from $V'$ to
$V''$ and give those of the form $v'v''$ very large cost (larger than
$2nk$) and the other new edges cost 1. Now, if the resulting complete
bipartite digraph $K_{n,n}$ has $k$-edge-disjoint spanning trees of
total cost less than $2nk$, then the set of new edges added will form
a minimum augmenting set and otherwise no solution exists.  Recall
from matroid theory that $k$ edge-disjoint spanning trees in $K_{n,n}$
correspond to $k$ edge-disjoint bases in the cycle matroid
$M(K_{n,n})$ of $K_{n,n}$ which again corresponds to an independent
set of size $k(2n-1)$ in the union $M=\bigvee_{i=1}^kM(K_{n,n})$.
This means that we
can solve the problem by finding a minimum cost base $B$ of $M$ and
then either return the arcs which correspond to edges of cost 1 in $B$
or decide that no solution exists when the cost of $B$ is more than
$2kn$. We leave the details to the reader.\hfill$\diamond$\\\vspace{2mm}


\section{A matroid for antistrong connectivity}\label{matroidsec}

Having seen the equivalence between antistrong connectivity of digraph
$D$ on $n$ vertices and connectivity of its bipartite representation
$B(D)$ (see Proposition~\ref{ASchar}),
and recalling from matroid theory that $B(D)$ is connected if
and only if the cycle matroid $M(B(D))$ has rank $|V(B(D))|-1$, it is
natural to ask how antistrong connectivity can be expressed as a
matroid property on $D$ itself.

For $F\subseteq A$, we denote by $h(F)$ and $t(F)$ the numbers of
vertices that are heads, respectively tails, of one or more arcs in
$F$.

Recall that the independent sets of the cycle matroid $M(G)$ of a
graph $G=(V,E)$ are
those subsets $I\subseteq E$ for which we have $|I'| \leq
\nu(I')-1$ for all $\emptyset\neq I'\subseteq I$, where $\nu(I')$
is the number of end vertices of the edges in $I'$. Inspired by this
we define set $I$ of arcs in a digraph $D=(V,A)$ to be {\bf
independent} if
\begin{equation}
\label{goodset} |I'| \leq h(I')+t(I')-1 \hspace{3mm}\mbox{for all
}\emptyset \neq I'\subseteq I,
\end{equation}
A set $S\subseteq A$ is {\bf dependent} if it is not independent.


\begin{proposition}
\label{goodisforest} Let $D=(V,A)$ be a digraph. A subset
$I\subseteq A$ is independent if and only if the corresponding edge
set $I$ in $B(D)$ forms a forest. Every inclusion-minimal dependent
set $S\subseteq A$ corresponds to a cycle in $B(D)$ and
conversely.
\end{proposition}
{\bf Proof: } Suppose $I\subseteq A$ is independent and consider the
corresponding edge set $\tilde I$ in $B(D)$. If $\tilde I$ is not a
forest, then some subset $\tilde I'\subseteq \tilde I$ will be a
cycle $C$ in $B(D)$ with $p$ vertices in each of $V',V''$ for some
$p\geq 2$. The set $\tilde I'$ corresponds to a set $I'\subseteq I$
with $h(I')+t(I')-1=p+p-1<2p=|I'|$, contradicting that $I$ is
independent. The other direction follows from the fact that every
forest $F$ in $B(D)$ spans at least $|E(F)|+1$ vertices in $B(D)$
and every subset of a forest is again a forest. The last claim
follows from the fact that every minimal set of edges which does not
form a forest in $B(D)$ forms a cycle in $B(D)$. \hfill$\diamond$\\\vspace{2mm}


The previous proposition implies that a set of arcs of a digraph
is dependent if and only if it contains a closed trail of even
length consisting of alternating forward and backward arcs. We will
refer to such a trail as a {\bf closed antidirected trail}, or {\bf CAT}
for short.

\begin{theorem}\label{antimatroid}
Let $D=(V,A)$ be a digraph and  $\cal I$ be the family of all
independent sets of arcs in $D$. Then $M(D)=(A,{\cal I})$ is a
graphic matroid with rank equal to
the size of a largest collection of arcs containing no closed
alternating trail.
\end{theorem}
{\bf Proof: } It follows immediately from Proposition~\ref{goodisforest} that
a set $I$ belongs to ${\cal I}$ if and only if the corresponding
edge set $\tilde I$ is independent in the cycle matroid on $B(D)$.
\hfill$\diamond$\\\vspace{2mm}

\begin{theorem}
A digraph $D$ is antistrong if and only if $M(B(D))$ has rank $2|V|-1$.
\end{theorem}
{\bf Proof: } The rank of $M(B(D))$ equals the size of a largest acyclic set of
edges in $B(D)$. This has size $2|V|-1$ precisely when $B(D)$ has a
spanning tree $H$. Back in $D$, the arcs corresponding to $E(H)$
contain antidirected forward
trails between any pair of
distinct vertices. \hfill$\diamond$\\\vspace{2mm}

\section{Antistrong orientations of graphs}\label{ASorsec}

Recall that, by Robbins' theorem (see e.g.~\cite[Theorem
  1.6.1]{bang2009}) a graph $G$ has a strongly connected orientation
if and only if $G$ is 2-edge-connected. For antistrong orientations we
have the following consequence of Proposition~\ref{ASchar} which
implies that there is no lower bound to the (edge-) connectivity which guarantees
an antistrong orientation of a graph.

\begin{proposition}
\label{nobipOK}
No bipartite graph can be oriented as an antistrong digraph.
\end{proposition}

The purpose of this section is to
characterize graphs
which can be oriented as antistrong digraphs.


\begin{theorem}\label{orient}
Suppose $G=(V,E)$ and $|E|=2|V|-1$. Then $G$ has an antistrong
orientation if and only if
\begin{eqnarray}
|E(H)|&\leq& 2|V(H)|-1 \mbox{ for all nonempty subgraphs $H$ of $G$, and}\label{condition}\\
 |E(H)|&\leq& 2|V(H)|-2 \mbox{ for all nonempty bipartite subgraphs $H$ of $G$.}\label{bipcond}\\
\nonumber
\end{eqnarray}
\end{theorem}


We derive Theorem~\ref{orient} from the following characterization
of graphs which can be oriented as  digraphs with no closed
antidirected trail (CAT).


\begin{theorem}
\label{CATfree} A graph $G=(V,E)$ has an orientation with no CAT if
and only if $G$ satisfies (\ref{condition}) and (\ref{bipcond}).  In
particular no $n$ vertex graph with at least $2n$ edges and no $n$
vertex bipartite graph with at least $2n-1$ edges admits a CAT-free
orientation.
\end{theorem}

It is not hard to see that Theorem~\ref{CATfree} implies
Theorem~\ref{orient}. Assume that Theorem~\ref{CATfree} holds and
consider a graph $G=(V,E)$ with $|E|=2|V|-1$. Suppose that $G$ has an
antistrong orientation $D$. Then $B(D)$ is connected by
Proposition~\ref{ASchar}.  As $B(D)$ has $2|V|-1=|V(B(D))|-1$ edges it
is a tree. So $D$ is a CAT-free orientation of $G$ and, by
Theorem~\ref{CATfree}, conditions (\ref{condition}) and
(\ref{bipcond}) hold for $G$.  Conversely, if (\ref{condition}) and
(\ref{bipcond}) hold for $G$, then $G$ has a CAT-free orientation by
Theorem~\ref{CATfree}, and we can deduce as above that this
orientation is also an antistrong orientation of $G$.\\

We next show that (\ref{condition}) and (\ref{bipcond}) are necessary
conditions for a CAT-free orientation. For the necessity of
(\ref{condition}), suppose that some nonempty subgraph $H$ has $|E(H)|\geq
2|V(H)|$ and that $D$ is any orientation of $G$. Then $B(D)$ has at
least $2|V(H)|$ edges between $V(H)'$ and $V(H)''$, implying that it
contains a cycle. Hence $D$ is not CAT-free. The necessity of
(\ref{bipcond}) can be seen as follows. Suppose $H$ is a bipartite
subgraph on $2|V(H)|-1$ edges and let $\vec{H}$ be an arbitrary
orientation of $H$.
Since no bipartite graph has an antistrong orientation it
follows that $B(\vec{H})$ is not connected, and, as
it has $2|V(H)|-1=|V(B(\vec{H}))|-1$ edges, it
contains a cycle. This corresponds to a CAT in
$\vec{H}$.\\


Most of the remainder of this section is devoted to a proof of
sufficiency in Theorem~\ref{CATfree}. We first show that, for an
arbitrary graph $G'=(V',E')$, the edge sets of all subgraphs $G$ of
$G'$ which satisfy (\ref{condition}) and (\ref{bipcond}) are the
independent sets of a matroid on $E'$.  We then show that this matroid
is the matroid union of the cycle matroid and the `even bicircular
matroid' of $G'$ (defined below).  This allows us to partition the edge-set of a graph
$G$ which satisfies (\ref{condition}) and (\ref{bipcond}) into a
forest and an `odd pseudoforest'. We then use this partition to define
a CAT-free orientation of $G$.  We first recall some results from
matroid theory. We refer a reader unfamiliar with submodular functions
and matroids to~\cite{frank2011}.

Suppose $E$ is a set and $f:2^E\to {\mathbb{Z}}$ is a submodular, nondecreasing
set function which is nonnegative on $2^E \setminus
\{\emptyset\}$. Edmonds~\cite{E1970}, see~\cite[Theorem
  13.4.2]{frank2011}, showed that $f$ induces a matroid $M_f$ on $E$
in which $S\subseteq E$ is independent if $|S'|\leq f(S')$ for all
$\emptyset\neq S'\subseteq S$.

 The rank of a subset $S\subseteq E$ in $M_f$ is given by the min-max formula
 \begin{equation}\label{eq:minmax}
r_f(S)=\min_{\mathcal{P}}\left\{\left|S\setminus\bigcup_{T\in {\mathcal{P}}}T\right|+\sum_{T\in{\mathcal{P}}}f(T)\right\},
\end{equation}
where the minimum is taken over all subpartitions ${\mathcal{P}}$ of $S$
(where a {\bf subpartition} of $S$ is a collection of pairwise
disjoint nonempty subsets of $S$). Note that the matroid $M(D)$ defined in
the previous section is induced on the arc-set of the digraph $D$ by
the set function $h+t-1$.

Given a graph $G=(V,E)$ and $S\subseteq E$ let $G[S]$ be the {\bf
subgraph induced} by $S$ i.e. the subgraph of $G$ with edge-set $S$
and vertex-set all vertices incident to $S$. Let $\nu,\beta:2^E\to
{\mathbb{Z}}$ by putting $\nu(S)$ equal to the number of vertices incident to
$S$, and $\beta(S)$ equal to the number of bipartite components of
$G[S]$. It is well known that $\nu$ is submodular, nondecreasing,
and nonnegative on $2^E$ and that $M_{\nu-1}(G)$ is the cycle
matroid of $G$. The function $\nu-\beta$ is also
submodular, nondecreasing, and nonnegative on $2^E $ since it is the rank function of the matroid on $E$ whose independent sets  are the edge sets of the {\bf
odd pseudoforests} of
  $G$, i.~e.~subgraphs in which each connected component contains at
most one cycle, and if such a cycle exists then it is odd, see \cite[Corollary 7D.3]{Z}.
We will refer to this matroid as the {\bf
even bicircular matroid} of $G$.

The above mentioned properties of $\nu$ and $\nu-\beta$ imply that
$2\nu-1-\beta$ is submodular, nondecreasing, and nonnegative on $2^E
\setminus \{\emptyset\}$. We will show that the independent sets in
$M_{2\nu-1-\beta}(G)$ are the edge sets of the subgraphs which
satisfy (\ref{condition}) and (\ref{bipcond}).

\begin{lemma}\label{lem:mat1}
Let $G=(V,E)$ be a graph and ${\mathcal{I}}=\{I\subseteq E\,:\mbox{ $G[I]$
  satisfies (\ref{condition}) and (\ref{bipcond})}\}$. Then ${\mathcal{I}}$ is
the family of independent sets of the matroid
$M_{2\nu-1-\beta}(G)$. In addition, the rank of a subset $S\subseteq
E$ in this matroid is
$r_{2\nu-1-\beta}(S)=\min_{\mathcal{P}}\left\{|S\setminus\bigcup_{T\in
  {\mathcal{P}}}T|+\sum_{T\in {\mathcal{P}}}\left(2\nu(T)-1-\beta(T)\right)\right\}$
where the minimum is taken over all subpartitions ${\mathcal{P}}$ of $S$.
\end{lemma}
\noindent {\bf Proof. } We first suppose that some $S\subseteq E$ is not independent in
$M_{2\nu-1-\beta}(G)$. Then we may choose a nonempty $S'\subseteq S$
with $|S'|>2\nu(S')-1-\beta(S')$, and subject to this condition, such
that $|S'|$ is as small as possible. The minimality of $S'$ implies
that $H=G[S']$ is connected. So $\beta(S')=1$ if and only if $H$ is
bipartite (and 0 otherwise) and we may now deduce that that
$H\subseteq G[S]$ fails to satisfy (\ref{condition}) or
(\ref{bipcond}).

We next suppose that $G[S]$ fails to satisfy (\ref{condition}) or
(\ref{bipcond}) for some $S\subseteq E$. Then there exists a nonempty
subgraph $H$ of $G[S]$ such that either $|E(H)|>2|V(H)|-1$, or $H$
is bipartite and $|E(H)|>2|V(H)|-2$. Then $S'=E(H)$ satisfies
$|S'|>2\nu(S')-1-\beta(S')$ so $S$ is not independent in
$M_{2\nu-1-\beta}(G)$.

The expression for the rank function of $M_{2\nu-1-\beta}(G)$
follows immediately from (\ref{eq:minmax}). \hfill$\diamond$\\\vspace{2mm}






The {\bf matroid union} of two matroids $M_1=(E,{\mathcal{I}}_1)$ and
$M_2=(E,{\mathcal{I}}_2)$ on the same ground set $E$ is the matroid $M_1\vee
M_2=(E,{\mathcal{I}})$ where ${\mathcal{I}}=\{I_1\cup I_2\,:\,I_1\in {\mathcal{I}}_1\mbox{
and } I_1\in {\mathcal{I}}_1\}$. Suppose $f_1,f_2:E\to {\mathbb{Z}}$ are submodular,
nondecreasing, and nonnegative on $2^E \setminus \{\emptyset\}$.
Then $f_1+f_2$ will also be submodular, nondecreasing, and
nonnegative on $2^E \setminus \{\emptyset\}$ and hence will induce
the matroid $M_{f_1+f_2}$. Every independent set in $M_{f_1}\vee
M_{f_2}$ is independent in $M_{f_1+f_2}$, but the converse does not
hold in general. Katoh and Tanigawa~\cite[Lemma 2.2]{KT} have shown
that the equality $M_{f_1+f_2}=M_{f_1}\vee M_{f_2}$ does hold
whenever the minimum in formula (\ref{eq:minmax}) for the ranks
$r_{f_1}(S)$ and $r_{f_2}(S)$ is attained for the same subpartition
of $S$, for all $S\subset E$. This allows us to deduce

\begin{lemma} \label{lem:mat2}
For any graph $G=(V,E)$, we have $M_{2\nu-1-\beta}(G)=M_{\nu-1}(G)\vee
M_{\nu-\beta}(G)$.
\end{lemma}
\noindent {\bf Proof. } This follows from the above mentioned result of Katoh and
Tanigawa, and the facts that
$r_{\nu-1}(S)=\sum_{T\in{\mathcal{P}}}(\nu(T)-1)$  and
$r_{\nu-\beta}(S)=\sum_{T\in{\mathcal{P}}}(\nu(T)-\beta(T))$ where ${\mathcal{P}}$
is the partition of $S$ given by the connected components of $G[S]$
(since $r_{\nu-1}(S)$ and $r_{\nu-\beta}(S)$ are equal to the number
of edges in  a maximum forest and a maximum odd pseudoforest,
respectively, in $G[S]$). \hfill$\diamond$\\\vspace{2mm}

Lemma~\ref{lem:mat1} and Lemma~\ref{lem:mat2} immediately give the following.

\begin{lemma}\label{lem:mat3}
Let $G=(V,E)$ be a graph. Then $G$ satisfies
(\ref{condition}) and (\ref{bipcond}) if and only if $E$ can be
partitioned into a forest and an odd pseudoforest.
\end{lemma}

\noindent We provide an alternative graph theoretic proof of this
lemma in the appendix.

We next show that every graph whose edge set can can be partitioned
into a spanning tree and an odd pseudoforest has a CAT-free
orientation.\\


\begin{figure}[h]
\begin{center}
\includegraphics[height=85mm]{asillu2.pdf}%
\end{center}
\caption{A CAT-free orientation of the union of a spanning tree $T$
  and a spanning odd pseudoforest $P$; $T$ governs the bipartition $X,Y$
  (white/grey), its edges are drawn outside (or on) the disk spanned by the
  vertices.  The edges of $P$ are embedded in the interior of that
  disk, the root vertex is the encircled topmost one, the precious
  edge is the dashed one.}
\label{twotreesfig}
\end{figure}
\begin{theorem}
\label{tree+forest}
Let $G$ be the edge-disjoint union of a spanning tree $T$ and an odd
pseudoforest $P$.\footnote{Note that $G$ may have parallel edges, but
  no more than two copies of any edge, in which case one copy is in
  $T$ and the other in $P$} Then $G$ has a CAT-free orientation. In
addition, such an orientation can be constructed in linear time given
$T$ and $P$.
\end{theorem}
{\bf Proof: } Let $X,Y$ be the unique (up to renaming the two sets)
bipartition of $T$ and orient all edges of $T$ from $Y$ to $X$. If
$P$ has no edges we are done since there are no cycles in $G$. Let
$P_1,\ldots{},P_k$ be the connected components of $P$. We shall show
that we can orient the edges of $P_1,\ldots{},P_k$ in such a way
that none of the resulting arcs of these (now oriented)
pseudoforests
$\vec{P_1},\ldots{},\vec{P_k}$
can belong to a closed antidirected trail. Clearly this will imply
the lemma. For each $P_i$ we choose a root vertex $r_i$ of $P_i$ as
follows. If $P_i$ is a tree then we choose $r_i$ to be an arbitrary
vertex of $P_i$. If $P_i$ contains an odd cycle $C_i$ then we choose
$r_i$ to be a vertex of $C_i$ such that $r_i$ has as many neighbours on $C_i$ as possible
in the same set of the
bipartition $(X,Y)$ as $r_i$. Since $C_i$ is odd we may choose one such neighbour
$s_i$ of $r_i$.
We will refer to the edge $r_is_i$ as a {\bf precious edge} of
$P_i$. Put $T_i=P_i-r_is_i$ if $P_i$ contains a cycle and otherwise
put $T_i=P_i$.

We orient the edges of $T_i$
as follows. Every edge of $P_i$ with one end in $X$ and the
other in $Y$ is oriented from $X$ to $Y$. Every edge $uv$ of $T_i$ with $u,v\in
X$ is oriented towards $r_i$ in $T_i$
(so if $v$ is closer to $r_i$ than $u$ in $T_i$ we orient the edge
from $u$ to $v$ and otherwise we orient it from $v$ to $u$, see
Figure~\ref{twotreesfig}). Every edge $pq$ of $T_i$ with $p,q\in Y$ is
oriented away from $r_i$ in $T_i$.
Finally, if $P_i$ contains a precious edge $r_is_i$, then we orient
$r_is_i$ from $r_i$ to $s_i$ if $r_i,s_i\in X$, and from $s_i$ to
$r_i$ if $r_i,s_i\in Y$.  Let $D$ denote the resulting orientation of
$G$.  The digraph $D$ can be constructed in linear time if we traverse
each tree $T_i$ by a breath first search rooted at $r_i$.

We use induction on $|E(P)|$ to show that the above construction results in a CAT-free digraph. As noted
above, this is true for the base case when $E(P)=\emptyset$. Suppose
that $E(P)\neq \emptyset$ and choose an edge $uv$ in some $P_i$
according to the following criteria. If $P_i$ is not a cycle then
choose $v$ to be a vertex of degree one in $P_i$ distinct from $r_i$
and $u$ to be the neighbour of $v$ in $P_i$. If $P_i$ is an odd cycle
then choose $v=r_i$ and $u=s_i$. We will show that $uv$ belongs to no
CAT in $D$.  By symmetry, we may suppose that $v\in X$.

We first consider the case when $v$ is a vertex of degree one in
$P_i$. Below $d^+(v),d^-(v)$ denote the out-degree, respectively, the
in-degree of the vertex $v$ in $D$.
We have two possible subcases:
\begin{itemize}
\item $u\in Y$. Since $v\in X$, we oriented $uv$ from $v$ to $u$. All
  the other edges incident to $v$ belong to $T$ and were oriented
  towards $v$. Then $d^+(v)=1$ and the arc $vu$ cannot be part of a
  CAT.
\item $u\in X$. Since $v\in X$, we oriented $uv$ from $v$ to $u$ (as $u$
  is closer to $r_i$ than $v$ in $T_i$). As previously we have $d^+(v)=1$ and
  the arc $vu$ cannot be part of a CAT.
\end{itemize}
Since $D-uv$ is CAT-free by induction, $D$ is also CAT-free.

We next consider the case when $P_i$ is an odd circuit.
Let $t_i$ be the neighbour of $r_i$ in $P_i$ distinct from $s_i$.
We again have  two possible subcases:
\begin{itemize}
\item $t_i\in X$.  Since $r_i\in X$, we oriented the edge $t_ir_i$ from $t_i$ to
  $r_i$. Then $d^+(r_i)=1$, and the arc $r_is_i$ cannot be part of a CAT. Since $D-r_is_i$ is CAT-free by induction, $D$ is also CAT-free.
\item $t_i\in Y$. Let $q_i$ be the neighbour of $s_i$ in $P_i$ which
  is distinct from $r_i$. The choice of $r_i$ implies that $q_i\in Y$,
  and hence that $s_iq_i$ is oriented from $s_i$ to $q_i$. Then
  $d^+(s_i)=1$, and the arc $s_iq_i$ cannot be part of a CAT. Since $D-s_iq_i$ can be obtained by applying our construction to $T\cup (P-s_iq_i)$ by choosing $s_i$ as the root vertex in $P_i-s_iq_i$ rather than $r_i$, it is CAT-free by induction. Hence $D$ is also CAT-free.
\end{itemize}

\hfill$\diamond$\\\vspace{2mm}


\noindent{}{\bf Proof of Theorem~\ref{CATfree} (sufficiency):} Let
$G=(V,E)$ be a graph satisfying (\ref{condition}) and
(\ref{bipcond}). By Lemma~\ref{lem:mat3}, $E$ can be partitioned into
a forest $F$ and an odd pseudoforest $P$. By adding a suitable set of
edges to $G$, we may assume that $|E|=2|V|-1$. (This follows by
considering the matroid $M_{2\nu-1-\beta}(2K_n)$ on the edge set of
the graph $2K_n$ with vertex set $V$ in which all pairs of vertices
are joined by two parallel edges. It is easy to check that $2K_n$ has
an edge-disjoint forest and odd pseudoforest with a total of $2|V|-1$
edges. Thus the rank of $M_{2\nu-1-\beta}(2K_n)$ is $2|V|-1$. Since
$E$ is an independent set in $M_{2\nu-1-\beta}(2K_n)$, it can be
extended to an independent set with $2|V|-1$ edges.) The fact that
$|E|=2|V|-1$ implies that $F$ is a spanning tree of $G$. We can now
apply Theorem~\ref{tree+forest} to deduce that $G$ has a CAT-free
orientation.  \hfill$\diamond$\\\vspace{2mm}


We have seen that Theorem~\ref{CATfree} implies Theorem~\ref{orient},
and hence that a graph $G=(V,E)$ has an antistrong orientation if and
only if the rank of $M_{2\nu-1-\beta}(G)$ is equal to $2|V|-1$. We can
now apply the rank formula (\ref{eq:minmax}) to characterize graphs
which admit an antistrong orientation.


\begin{theorem}\label{thm:char}
A graph $G=(V,E)$ has an antistrong orientation if and only if
\begin{equation}\label{ASorchar}
e({\mathcal{Q}})\geq |{\mathcal{Q}}|-1+b({\mathcal{Q}})
\end{equation}
for all partitions ${\mathcal{Q}}$ of $V$, where $e({\mathcal{Q}})$ denotes the
number of edges of $G$ between the different parts of ${\mathcal{Q}}$ and
$b({\mathcal{Q}})$ the number of parts of ${\mathcal{Q}}$ which induce bipartite
subgraphs of $G$.
\end{theorem}

\noindent
{\bf Proof: } Suppose that $G$ has no antistrong orientation. Then the rank of
$M_{2\nu-1-\beta}(G)$ is less than $2|V|-1$ so there exists a
subpartition ${\mathcal{P}}$ of $E$ such that
\begin{equation}\label{ASorchar1}
\alpha({\mathcal{P}}):=\left|E\setminus\bigcup_{T\in
{\mathcal{P}}}T\right|+\sum_{T\in{\mathcal{P}}}\left(2\nu(T)-1-\beta(T)\right)<
2|V|-1
\end{equation}
by Lemma \ref{lem:mat1}. We may assume that ${\mathcal{P}}$ has been chosen such that:
\begin{enumerate}
\item[(i)] $\alpha({\mathcal{P}})$ is as small as possible;
\item[(ii)] subject to (i), $|{\mathcal{P}}|$ is as small as possible;
\item[(iii)] subject to (i) and (ii), $|\bigcup_{T\in
  {\mathcal{P}}}T|$ is as large as possible.
  \end{enumerate}
   Let
${\mathcal{P}}=\{E_1,E_2,\ldots,E_t\}$ and let $H_i=(V_i,E_i)$ be the
subgraph of $G$ induced by $E_i$ for all $1\leq i\leq t$.
We will show that $H_i$ is a (vertex-)induced connected subgraph of
$G$ and that $V_i\cap V_j=\emptyset$ for all $i\neq j$.

First, suppose that $H_i$ is disconnected for some $1\leq i\leq t$.
Then we have $H_i=H_i'\cup H_i''$ for some subgraphs
$H_i'=(V_i',E_i')$ and $H_i''=(V_i'',E_i'')$ with $V_i'\cap
V_i''=\emptyset$. Let ${\mathcal{P}}'=({\mathcal{P}}\setminus\{E_i\})\cup\{E_i',E_i''\}$. We
have
$$2\nu(E_i)-1-\beta(E_i)>2\nu(E_i')-1-\beta(E_i')+2\nu(E_i'')-1-\beta(E_i'')$$ since
$\nu(E_i)=\nu(E_i')+\nu(E_i'')$ and $\beta(E_i)=
\beta(E_i')+\beta(E_i'')$. This implies that
$\alpha({\mathcal{P}}')<\alpha({\mathcal{P}})$ and contradicts (i). Hence $H_i$ is
connected and $\beta(E_i)\in \{0,1\}$ for all $1\leq i \leq t$.


Next, suppose that $V_i\cap V_j\neq \emptyset$ for some $1\leq
i<j\leq t$. Let ${\mathcal{P}}'=({\mathcal{P}}\setminus\{E_i,E_j\})\cup\{E_i\cup E_j\}$. We
have
$$2\nu(E_i)-1-\beta(E_i)+2\nu(E_j)-1-\beta(E_j)\geq 2\nu(E_i\cup
E_j)-1-\beta(E_i\cup E_j)$$ since, if $|V_i\cap V_j|=1$, then
$\nu(E_i)+\nu(E_j)= \nu(E_i\cup E_j)+1$ and
$\beta(E_i)+\beta(E_j)\leq \beta(E_i\cup E_j)+1$,
and, if $|V_i\cap V_j|\ge 2$, then $\nu(E_i)+\nu(E_j)\geq
\nu(E_i\cup E_j)+2$ and $\beta(E_i)+\beta(E_j)\leq 2$.
This implies that $\alpha({\mathcal{P}}')\leq\alpha({\mathcal{P}})$. Since
$|{\mathcal{P}}'|<|{\mathcal{P}}|$ this contradicts (i) or (ii). Hence $V_i\cap
V_j=\emptyset$ for all $i\neq j$.

Finally, suppose that $H_i\neq G[V_i]$. Then some $e\in
E\setminus\bigcup_{T\in
  {\mathcal{P}}}T$ has both end vertices in $E_i$. Let $E_i'=E_i+e$ and
${\mathcal{P}}'={\mathcal{P}} - E_i +E_i'$. This implies that
$\alpha({\mathcal{P}}')\leq\alpha({\mathcal{P}})$. Since $|{\mathcal{P}}'|=|{\mathcal{P}}|$ and
$|\bigcup_{T\in
  {\mathcal{P}}'}T|>|\bigcup_{T\in
  {\mathcal{P}}}T|$,
this contradicts (i) or (iii). Hence $H_i=G[V_i]$.


Let ${\mathcal{Q}}$ be the partition of $V$ obtained from
$\{V_1,V_2,\ldots,V_t\}$ by adding the remaining vertices of $G$ as
singletons. Then $\left|E\setminus\bigcup_{T\in {\mathcal{P}}}T\right|=e({\mathcal{Q}})$
and
$\sum_{T\in{\mathcal{P}}}\left(2\nu(T)-1-\beta(T)\right)=2|V|-|{\mathcal{Q}}|-b({\mathcal{Q}})$.
We can now use (\ref{ASorchar1}) to deduce that $e({\mathcal{Q}})<
|{\mathcal{Q}}|-1+b({\mathcal{Q}})$.

\smallskip

For the converse, suppose that $e({\mathcal{Q}})< |{\mathcal{Q}}|-1+b({\mathcal{Q}})$ for
some partition ${\mathcal{Q}}=\{V_1,V_2,\ldots,V_s\}$ of $V$. We may assume that $G[V_i]$ is connected for all $1\leq i \leq s$ since we can replace $V_i$ by the vertex sets of the components of $G[V_i]$ in ${\mathcal{Q}}$ and maintain this inequality. Let
$G[V_i]=(V_i,E_i)$ for $1\leq i\leq s$ and  ${\mathcal{P}}=\{E_i\,:\,E_i\neq
\emptyset,\,1\leq i\leq s\}$.

 Then $\left|E\setminus\bigcup_{T\in
{\mathcal{P}}}T\right|=e({\mathcal{Q}})$ and
$\sum_{T\in{\mathcal{P}}}\left(2\nu(T)-1-\beta(T)\right)=2|V|-|{\mathcal{Q}}|-b({\mathcal{Q}})$. (Note that a set $V_i\in {\mathcal{Q}}$ with $|V_i|=1$ has no corresponding edge set in ${\mathcal{P}}$ and contributes $2-1-1$ to the right hand side of the last equation.)
This implies that
$$\left|E\setminus\bigcup_{T\in
{\mathcal{P}}}T\right|+\sum_{T\in{\mathcal{P}}}\left(2\nu(T)-1-\beta(T)\right)=
e({\mathcal{Q}})+\sum_{T\in{\mathcal{P}}}\left(2\nu(T)-1-\beta(T)\right)<
2|V|-1$$ and hence $G$ has no antistrong orientation. \hfill$\diamond$\\\vspace{2mm}
\\[2mm]
\iffalse
OR
\\[2mm]

Suppose, on the other hand, that $G$ has an antistrong orientation.
Then $G$ contains an edge-disjoint spanning tree $T$ and odd
pseudoforest $P$ with $|E(P)|=|V(G)$|. Let
${\mathcal{Q}}=\{V_1,V_2,\ldots,V_s\}$ be a partition of $V$ and let $H$ be
 the graph obtained by contracting each set $V_i$ to a single vertex
 $v_i$ and then adding a loop at $v_i$ whenever $G[V_i]$ is not
 bipartite. Then there must be at least $|{\mathcal{Q}}|-1$ edges of $T$
 and at least $b({\mathcal{Q}})$ edges of $P$ joining the vertices of $H$.
 Hence $e({\mathcal{Q}})\geq |{\mathcal{Q}}|-1+b({\mathcal{Q}})$.
\fi


\begin{corollary} Every $4$-edge-connected nonbipartite graph has an
antistrong orientation.
\end{corollary}
{\bf Proof: } Suppose $G=(V,E)$ is $4$-edge-connected and not bipartite and
let ${\mathcal{Q}}$ be a partition of $V$. If ${\mathcal{Q}}=\{V\}$ then
$e({\mathcal{Q}})=0=|{\mathcal{Q}}|-1+b({\mathcal{Q}})$ since $G$ is not bipartite, and if
${\mathcal{Q}}\neq \{V\}$ then $e({\mathcal{Q}})\geq 2|{\mathcal{Q}}|\geq
|{\mathcal{Q}}|-1+b({\mathcal{Q}})$ since $G$ is $4$-edge-connected. Hence $G$ has
an antistrong orientation by Theorem~\ref{thm:char}. \hfill$\diamond$\\\vspace{2mm}

\begin{corollary}
\label{cor:3trees-antistrong}
Every nonbipartite graph with three edge-disjoint spanning trees has
an antistrong orientation.
\end{corollary}
{\bf Proof: } We give two proofs of this corollary.

 Suppose $G=(V,E)$ is a
nonbipartite graph with three edge-disjoint spanning trees and let
${\mathcal{Q}}$ be a partition of $V$.  If ${\mathcal{Q}}=\{V\}$ then
$e({\mathcal{Q}})=0=|{\mathcal{Q}}|-1+b({\mathcal{Q}})$ since $G$ is not bipartite, and if
${\mathcal{Q}}\neq \{V\}$ then $e({\mathcal{Q}})\geq 3(|{\mathcal{Q}}|-1)$ since $G$ has
three edge-disjoint spanning trees.
Since $|{\mathcal{Q}}|\ge 2$,
$2(|{\mathcal{Q}}|-1)\ge |{\mathcal{Q}}| \ge b({\mathcal{Q}})$ and $e({\mathcal{Q}})\geq
|{\mathcal{Q}}|-1+b({\mathcal{Q}})$. Hence $G$ has an antistrong orientation by
Theorem~\ref{thm:char}.

 We could also remark that if $T_1$, $T_2$
and $T_3$ denote three edge-disjoint spanning trees of $G$, then there
exists $e\in G$ such that $T_1+e$ is not bipartite. Then depending if
$e\in T_2$ or not, $\{T_1+e,T_3\}$ or $\{T_1+e,T_2\}$ is an
edge-disjoint pair of a spanning odd pseudo-tree and a spanning tree
of $G$. Let $H$ denote this subgraph of $G$. Then using
Theorem~\ref{tree+forest}, $H$ has a CAT-free orientation which is also
an antistrong orientation of $H$ since $|E(H)|=2|V(H)|-1$. So $G$ has also an
antistrong orientation.
\hfill$\diamond$\\\vspace{2mm}

Corollary \ref{cor:3trees-antistrong} is tight in the sense that
there exist graphs with many edge-disjoint trees, two spanning and
the others missing just three vertices, which have no antistrong
orientation. Consider the graph $G$ obtained by identifying one
vertex of a complete bipartite graph $K_{k,k}$ and a complete graph
$K_4$. Then $G$ has no antistrong orientation. Indeed, consider the
partition ${\mathcal{Q}}$ of $V(G)$ into four parts: the copy of $K_{k,k}$,
and one part for each remaining vertex of $K_4$.  We have
$e({\mathcal{Q}})=6 < |{\mathcal{Q}}|-1+b({\mathcal{Q}})= 4-1+4$ and then $G$ has no
antistrong orientation by Theorem~\ref{thm:char}.


\medskip

Since $M_{2\nu-1-\beta}(G)=M_{\nu-1}(G)\vee M_{\nu-\beta}(G)$, we
can use Edmonds' matroid partition algorithm~\cite{edmondsJRNBS69}
to determine the rank of $M_{2\nu-1-\beta}(G)$ in polynomial time,
and hence determine whether $G$ has an antistrong orientation.
Moreover, when such an orientation exists, we can use Edmonds'
algorithm to construct an edge-disjoint spanning tree and
pseudoforest with a total of $2|V|-1$ edges, and then use the
construction from the proof of Theorem~\ref{tree+forest} to obtain
the desired antistrong orientation in polynomial time. This gives
\begin{corollary}
There exists a polynomial time algorithm which finds, for a given
input graph $G$, either an antistrong orientation $D$ of $G$, or a
certificate, in terms of a subpartition $\cal P$ which violates
(\ref{ASorchar}), that $G$ has no such orientation.
\end{corollary}


\section{Connected bipartite 2-detachments of graphs}\label{detachsec}

We now show a connection between antistrong orientations of a graph
$G$ and so-called detachments of $G$. We need only the special case of
2-detachments (see e.g.~\cite{nashwilliamsJLMS31} for results on
detachments).

A {\bf 2-detachment} of a graph $G=(V,E)$ is any graph $H=(V'\cup
V'',E')$
which can be obtained from $G$
by replacing every vertex $v\in V$ with two new vertices $v',v''$
and then for each original edge $uv$ adding precisely one of the
four edges $u'v',u'v'',u''v',u''v''$ to $E'$.

\begin{lemma}\label{detach}
A graph $G=(V,E)$ has an antistrong orientation if and only if $G$ has
a 2-detachment $H=(V'\cup V'',E')$ which is connected and bipartite
with bipartition $V',V''$ (we call such a 2-detachment {\bf good}).
\end{lemma}
{\bf Proof: } Suppose $G$ has a good 2-detachment $H=(V'\cup V'',E')$. Then
there are no edges of the form $u'v'$ and no edges of the form
$u''v''$. Hence the orientation $D$ that we get by orienting the edges
of the form $u'v''$ from $u$ to $v$ will be an antistrong orientation
of $G$ by Proposition~\ref{ASchar}.  Conversely, if $D$ is an
antistrong orientation of $G$, then $B(D)$ is a good 2-detachment of
$G$. \hfill$\diamond$\\\vspace{2mm}

We can now use Theorem~\ref{thm:char} and the subsequent remark to deduce the following.
\begin{theorem}
\label{good2detach} A graph $G=(V,E)$  has a good 2-detachment if
and only if
\begin{equation}
\label{detachcond}
e({\mathcal{Q}})\geq |{\mathcal{Q}}|-1+b({\mathcal{Q}})
\end{equation}
for all partitions ${\mathcal{Q}}$ of $V$. Furthermore, there exists a
polynomial time algorithm which returns such a $2$-detachment when it
exists and otherwise returns a certificate, in terms of a partition violating (\ref{detachcond}), that no such detachment exists.
\end{theorem}

\section{Non-separating antistrong spanning subdigraphs}\label{nosepsec}

While there are polynomial time algorithms for checking the existence of
two edge-disjoint spanning trees~\cite{edmondsJRNBS69}, or two
arc-disjoint branchings (spanning out-trees) in a digraph (see
e.g.~\cite[Corollary 9.3.2]{bang2009}), checking whether we can delete
a strong spanning subdigraph and still have a connected digraph is
difficult. Let $U\!G(D)$ denote the underlying undirected graph of a digraph $D$.

\begin{theorem}\cite{bangTCS438}
\label{nondisconstrong}
It is NP-complete to decide whether a given digraph $D$ contains a
spanning strong subdigraph $H$ such that $U\!G(D-A(H))$ is connected.
\end{theorem}

If we replace ``strong'' by ``antistrong'' above, the problem becomes
solvable in polynomial time.


\begin{theorem}
\label{deleteanticon}
We can decide in polynomial time for a given digraph $D=(V,A)$ on $n$
vertices whether $D$ contains a spanning antistrong subdigraph
$H=(V,A')$ such that $U\!G(D-A')$ is connected.
\end{theorem}
{\bf Proof: } We may assume that $D$ is antistrong, since this can be checked in
linear time by verifying that $B(D)$ is connected.  Let $M_1=(A,{\cal
  I})$ be the cycle matroid of of the underlying graph $U\!G(D)$ of $D$ and let $M_2=M(D)=(A,{\cal
  I}(D))$ be the matroid from Section~\ref{matroidsec} whose bases are
the antistrong sets consisting of $2n-1$ arcs. Let $M=M_1\vee{}M_2$ be
the union of the matroids $M_1,M_2$, that is, a set $X$ of arcs is
independent in $M$ if and only we can partition $X$ into $X_1, X_2$
such that $X_i$ is independent in $M_i$.
For each of the
matroids $M_1, M_2$ we can check in polynomial time whether a given
subset $X$ of arcs is independent in $M_1$ and $M_2$ (for $M_1$ we
need to check that there is no cycle in $U\!G(D)[X]$ and for $M_2$ we
need to check that there is no cycle in the subgraph of $B(D)[E_X]$
induced by the edges $E_X$ corresponding to $X$ in $B(D)$%
). Thus it follows from
Edmonds' algorithm for matroid partitioning~\cite{edmondsJRNBS69} that
we can find a base of $M$ in polynomial time using the independence
oracles of $M_1,M_2$. The desired digraph $H$ exists if and only if
the size of a base in $M$ is $(2n-1)+(n-1)=3n-2$. \hfill$\diamond$\\\vspace{2mm}

A similar proof gives the following.

\begin{theorem}
We can decide in polynomial time whether a digraph $D$ contains
$k+\ell$ arc-disjoint spanning subdigraphs
$D_1,\ldots{},D_{k+\ell}$ such that
$D_1,\ldots{},D_k$ are antistrong and $U\!G(D_{k+1}),\ldots{},U\!G(D_{k+\ell})$
are connected.
\end{theorem}






\section{Remarks and open problems}

We saw in Theorem~\ref{twospstrongD} that it is NP-complete to decide whether a
given digraph contains two arc-disjoint spanning strong subdigraphs.  We
would be interested to know what happens if we modify the problem as
follows.



\begin{question}
Can we decide in polynomial time whether a digraph $D$ contains arc-disjoint
spanning subdigraphs $D_1,D_2$ such that $D_1$ is antistrong and $D_2$
is strongly connected?
\end{question}

Inspired by Theorem~\ref{deleteanticon} it is natural to ask the
following intermediate question.

\begin{question}
\label{anti+2con}
Can we decide in polynomial time whether a digraph $D$ contains arc-disjoint
spanning subdigraphs $D_1,D_2$ such that $D_1$ is antistrong and
$U\!G(D_2)$ is 2-edge-connected?
\end{question}

The following conjecture was raised in~\cite{bangC24}.

\begin{conjecture}\cite{bangC24}
There exists a natural number $k$ such that every $k$-arc-strong
digraph has arc-disjoint strong spanning subdigraphs $D_1,D_2$.
\end{conjecture}

\noindent
Perhaps the following special case may be easier to study.

\begin{conjecture}
There exists a natural number $k$ such that every digraph $D$ which is
both $k$-arc-strong and $k$-arc-antistrong has arc-disjoint strong
spanning subdigraphs $D_1,D_2$.
\end{conjecture}

\begin{problem}
Does there exist a polynomial algorithm for deciding whether a given undirected graph $G$ has an orientation $D$ which is both strong and antistrong?
\end{problem}

\bigskip

\centerline{*}

\bigskip

{\bf Acknowledgement.}
Bang-Jensen and Jackson wish to thank Jan van den Heuvel for
stimulating discussions about antistrong connectivity.  They also
thank the Mittag-Leffler Institute for providing an excellent working
environment.


2016-05-26T02:09:23.000
1605
1605.07832
en
https://arxiv.org/abs/1605.07832
An antidirected trail in a digraph is a trail (a walk with no arc repeated) in which the arcs alternate between forward and backward arcs. An antidirected path is an antidirected trail where no vertex is repeated. We show that it is NP-complete to decide whether two vertices $x,y$ in a digraph are connected by an antidirected path, while one can decide in linear time whether they are connected by an antidirected trail. A digraph $D$ is antistrong if it contains an antidirected $(x,y)$-trail starting and ending with a forward arc for every choice of $x,y\in V(D)$. We show that antistrong connectivity can be decided in linear time. We discuss relations between antistrong connectivity and other properties of a digraph and show that the arc-minimal antistrong spanning subgraphs of a digraph are the bases of a matroid on its arc-set. We show that one can determine in polynomial time the minimum number of new arcs whose addition to $D$ makes the resulting digraph the arc-disjoint union of $k$ antistrong digraphs. In particular, we determine the minimum number of new arcs which need to be added to a digraph to make it antistrong. We use results from matroid theory to characterize graphs which have an antistrong orientation and give a polynomial time algorithm for constructing such an orientation when it exists. This immediately gives analogous results for graphs which have a connected bipartite 2-detachment. Finally, we study arc-decompositions of antistrong digraphs and pose several problems and conjectures.
Combinatorics (math.CO)
Antistrong digraphs
Qwen/Qwen-72B
1. YES
2. YES