Structural and Algorithmic Properties Concerning Packing, Covering and Partitioning of Digraphs

In this thesis we give a complete classification of semicomplete digraphs which have an out-branching with root u which is arc-disjoint from some in-branching with root v where u, v are prescribed vertices. Such a pair of branchings is called a good (u, v)-pair. Using this characterization, we completely solve the problem of deciding whether a given digraph obtained by substituting the vertices of a semicomplete digraph with arbitrary digraphs has a good (u, v)-pair for given vertices u, v. This solves an open problem by Bang-Jensen and Gutin for quasi-transitive digraphs from 1998. We also describe several results concerning the existence of good pairs in digraphs whose complement is bipartite.

In addition, we study the problem of decomposing the arcs of a split digraph D into two arc-disjoint subsets such that both of which induce a strongly connected spanning digraph of D. In particular, we prove that every 3-arc-strong split digraph has such an arc-decomposition. This confirms a conjecture of Bang-Jensen and Yeo on decomposing digraphs with high arc-connectivity into strongly connected spanning subdigraphs for the special case where the digraph is a split digraph. We also provide infinite classes of 2- strong split digraphs with no good (u, v)-pairs for some given u and v. Moreover, our results imply that Thomassen’s Conjecture on good (u, v)-pairs in digraphs with high arcconnectivity holds for the five classes of digraphs mentioned above with arc-connectivity 3.

If a digraph D has a good (u, v)-pair, then for every vertex w of D it is the case that D has a (w, v)-path which is arc-disjoint from some out-branching rooted at u. It turns out that this partial problem also has a very natural characterization for semicomplete digraphs. In the characterization of semicomplete digraphs with a good (u, v)-pair for given roots u, v, the existence of arc-disjoint (s1, t1)- and (s2, t2)-paths plays an important role. Motivated by this, in the thesis we also study the problem of finding arc-disjoint paths with specified end-vertices in semicomplete digraphs and extend this result to mixed graphs.

Another topic in this thesis is structural and algorithmic properties of generalized paths and cycles in semicomplete multipartite digraphs. We show how these results allow us to identify classes of directed 0-1 TSP instances that can be solved in polynomial time as well as others for which we can get very close to the optimum in polynomial time. All our arguments in the thesis leading to the proofs of our results are constructive and can be converted to polynomial algorithms.