Search

A 2-edge-coloured graph G is supereulerian if G contains a spanning closed trail in which the edges alternate in colours. We show that for general 2-edge-coloured graphs it is NP-complete to decide whether the graph is supereulerian. An eulerian factor of a 2-edge-coloured graph is a collection of vertex-disjoint induced subgraphs which cover all the vertices of G such that each of these subgraphs is supereulerian. We give a polynomial algorithm to test whether a 2-edge-coloured graph has an eulerian factor and to produce one when it exists. A 2-edge-coloured graph is (trail-)colour-connected if it contains a pair of alternating (u, v)-paths ((u, v)-trails) whose union is an alternating closed walk for every pair of distinct vertices u, v. We prove that a 2-edge-coloured complete bipartite graph is supereulerian if and only if it is colour-connected and has an eulerian factor. A 2-edge-coloured graph is M-closed if xz is an edge of G whenever some vertex u is joined to both x and z by edges of the same colour. M-closed 2-edge-coloured graphs, introduced in Contreras-Balbuena et al. (Discret Math Theoret Comput Sci 21:1, 2019), form a rich generalization of 2-edge-coloured complete graphs. We show that if G is obtained from an M-closed 2-edge-coloured graph H by substituting independent sets for the vertices of H, then G is supereulerian if and only if G is trail-colour-connected and has an eulerian factor. Finally we discuss 2-edge-coloured complete multipartite graphs and show that such a graph may not be supereulerian even if it is trail-colour-connected and has an eulerian factor.

A digraph D is k-linked if it satisfies that for every choice of disjoint sets {x1,…,xk} and {y1,…,yk} of vertices of D there are vertex disjoint paths P1,…,Pk such that Pi is an (xi,yi)-path. Confirming a conjecture by Kühn et al., Pokrovskiy proved in 2015 that every 452k-strong tournament is k-linked and asked for a better linear bound. Very recently Meng et al. proved that every (40k−31)-strong tournament is k-linked. In this note we use an important lemma from their paper to give a short proof that every (13k−6)-strong tournament of minimum out-degree at least 28k−13 is k-linked.

Given a network modeled by a directed graph D = ( V , A ) , it is natural to ask whether we can partition the vertex set of D into two disjoint subsets V 1 , V 2 (called a 2-partition), such that the digraphs D [ V 1 ] , D [ V 2 ] induced by each of these has one of the two properties of interest. This question gives rise to a rich realm of combinatorial problems. The complexity of many such problems was determined in [2] , [3] . We analyze a subset of those problems from the viewpoint of parameterized complexity, and present a complete dichotomy of basic, natural properties. More precisely, given a directed graph D = ( V , A ) and two non-negative integers k 1 and k 2 , we seek a 2-partition ( V 1 , V 2 ) of the vertex set V such that | V 1 | ≥ k 1 , | V 2 | ≥ k 2 , and each of the subdigraphs induced by V 1 and V 2 has a structural property as defined by the problem at hand—for example, D [ V 1 ] is acyclic and D [ V 2 ] is strongly connected. Specifically, we consider the following eight structural properties: being strongly connected; being connected; having an out-branching; having an in-branching; having minimum degree at least one; having minimum semi-degree at least one; being acyclic; and being complete.

The weak 2-linkage problem for digraphs asks for a given digraph and vertices s 1 , s 2 , t 1 , t 2 whether D contains a pair of arc-disjoint paths P 1 , P 2 such that P i is an ( s i , t i ) -path. This problem is NP-complete for general digraphs but polynomially solvable for acyclic digraphs [8] . Recently it was shown [3] that if D is equipped with a weight function w on the arcs which satisfies that all edges have positive weight, then there is a polynomial algorithm for the variant of the weak-2-linkage problem when both paths have to be shortest paths in D. In this paper we consider the unit weight case and prove that for every pair of constants k 1 , k 2 , there is a polynomial algorithm which decides whether the input digraph D has a pair of arc-disjoint paths P 1 , P 2 such that P i is an ( s i , t i ) -path of length no more than d ( s i , t i ) + k i , for i = 1 , 2 , where d ( s i , t i ) denotes the length of the shortest ( s i , t i ) -path. We prove that, unless the exponential time hypothesis (ETH) fails, there is no polynomial algorithm for deciding the existence of a solution P 1 , P 2 to the weak 2-linkage problem where each path P i has length at most d ( s i , t i ) + c log 1 + ϵ ⁡ n for some constant c.

The dichromatic number $\overrightarrow{\chi}(D)$ of a digraph $D$ is the minimum number of colors needed to color the vertices of $D$ such that each color class induces an acyclic subdigraph of $D$. A digraph $D$ is $k$-critical if $\overrightarrow{\chi}(D) = k$ but $\overrightarrow{\chi}(D') < k$ for all proper subdigraphs $D'$ of $D$. We examine methods for creating infinite families of critical digraphs, the Dirac join and the directed and bidirected Hajós join. We prove that a digraph $D$ has dichromatic number at least $k$ if and only if it contains a subdigraph that can be obtained from bidirected complete graphs on $k$ vertices by directed Hajós joins and identifying non-adjacent vertices. Building upon that, we show that a digraph $D$ has dichromatic number at least $k$ if and only if it can be constructed from bidirected $K_k$'s by using directed and bidirected Hajós joins and identifying non-adjacent vertices (so called Ore joins), thereby transferring a well-known result of Urquhart to digraphs. Finally, we prove a Gallai-type theorem that characterizes the structure of the low vertex subdigraph of a critical digraph, that is, the subdigraph, which is induced by the vertices that have in-degree $k-1$ and out-degree $k-1$ in $D$.

We give an FPT algorithm for deciding whether the vertex set of a digraph D can be partitioned into two disjoint sets V 1 , V 2 such that the digraph D [ V 1 ] induced by V 1 has a vertex that can reach all other vertices by directed paths, the digraph D [ V 2 ] has no vertex of in-degree zero and | V i | ≥ k i , where k 1 , k 2 are part of the input. This settles an open problem from [1] , [4] .

A 2-partition of a digraph D is a partition ( V 1 , V 2 ) of V ( D ) into two disjoint non-empty sets V 1 and V 2 such that V 1 ∪ V 2 = V ( D ) . A semicomplete digraph is a digraph with no pair of non-adjacent vertices. We consider the complexity of deciding whether a given semicomplete digraph has a 2-partition such that each part of the partition induces a (semicomplete) digraph with some specified property. In [4] and [5] Bang-Jensen, Cohen and Havet determined the complexity of 120 such 2-partition problems for general digraphs. Several of these problems are NP-complete for general digraphs and thus it is natural to ask whether this is still the case for well-structured classes of digraphs, such as semicomplete digraphs. This is the main topic of the paper. More specifically, we consider 2-partition problems where the set of properties are minimum out-, minimum in- or minimum semi-degree. Among other results we prove the following: • For all integers k 1 , k 2 ≥ 1 and k 1 + k 2 ≥ 3 it is NP-complete to decide whether a given digraph D has a 2-partition ( V 1 , V 2 ) such that D 〈 V i 〉 has out-degree at least k i for i = 1 , 2 . • For every fixed choice of integers α , k 1 , k 2 ≥ 1 there exists a polynomial algorithm for deciding whether a given digraph of independence number at most α has a 2-partition ( V 1 , V 2 ) such that D 〈 V i 〉 has out-degree at least k i for i = 1 , 2 . • For every fixed integer k ≥ 1 there exists a polynomial algorithm for deciding whether a given semicomplete digraph has a 2-partition ( V 1 , V 2 ) such that D 〈 V 1 〉 has out-degree at least one and D 〈 V 2 〉 has in-degree at least k. • It is NP-complete to decide whether a given semicomplete digraph D has a 2-partition ( V 1 , V 2 ) such that D 〈 V i 〉 is a strong tournament.

A $(\delta\geq k_1,\delta\geq k_2)$-partition of a graph $G$ is a vertex-partition $(V_1,V_2)$ of $G$ satisfying that $\delta(G[V_i])\geq k_i$ for $i=1,2$. We determine, for all positive integers $k_1,k_2$, the complexity of deciding whether a given graph has a $(\delta\geq k_1,\delta\geq k_2)$-partition. We also address the problem of finding a function $g(k_1,k_2)$ such that the $(\delta\geq k_1,\delta\geq k_2)$-partition problem is ${\cal NP}$-complete for the class of graphs of minimum degree less than $g(k_1,k_2)$ and polynomial for all graphs with minimum degree at least $g(k_1,k_2)$. We prove that $g(1,k)=k$ for $k\ge 3$, that $g(2,2)=3$ and that $g(2,3)$, if it exists, has value 4 or 5., Comment: 13 pages, 2 figures

International audience; 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 ∈ 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.

A digraph is {\bf eulerian} if it is connected and every vertex has its in-degree equal to its out-degree. Having a spanning eulerian subdigraph is thus a weakening of having a hamiltonian cycle. A digraph is {\bf semicomplete} if it has no pair of non-adjacent vertices. A {\bf tournament} is a semicomplete digraph without directed cycles of length 2. Fraise and Thomassen \cite{fraisseGC3} proved that every $(k+1)$-strong tournament has a hamiltonian cycle which avoids any prescribed set of $k$ arcs. In \cite{bangsupereuler} the authors demonstrated that a number of results concerning vertex-connectivity and hamiltonian cycles in tournaments and have analogues when we replace vertex connectivity by arc-connectivity and hamiltonian cycles by spanning eulerian subdigraphs. They showed the existence of a smallest function $f(k)$ such that every $f(k)$-arc-strong semicomplete digraph has a spanning eulerian subdigraph which avoids any prescribed set of $k$ arcs. They proved that $f(k)\leq \frac{(k+1)^2}{4}+1$ and also proved that $f(k)=k+1$ when $k=2,3$. Based on this they conjectured that $f(k)=k+1$ for all $k\geq 0$. In this paper we prove that $f(k)\leq (\lceil\frac{6k+1}{5}\rceil)$.

We study out-branchings rooted at a given vertex s with the extra requirement that these satisfy certain balance conditions, such as balancing the number of arcs out of s, the number of vertices in each subtree of the branching etc. We obtain polynomial algorithms for several of the problems and study the borderline between polynomial and NP-complete special cases of the problems.

The multicut problem with respect to the fixed pattern (di)graph Q is the following: given a (di)graph G, an integer k and a 1-1 mapping @p of the vertices of Q to a subset X of V(G); determine whether there exists a set S of at most k edges (arcs) of G such that G-S has no (@p(q),@p(q^'))-path for every edge (arc) qq^' of Q. We first prove a dichotomy result for the complexity (they are all either polynomial or NP-complete) for multicut problems in (di)graphs in terms of the pattern Q. Then we consider a variant where the pattern is a mixed graph M; the input is a digraph D, an integer k and a 1-1 mapping @p from V(M) to some subset of V(D) and the goal is to decide whether there exists a set S of at most k arcs of D that meets every (@p(q),@p(q^'))-path in D for every arc qq^' of M and every (@p(p),@p(p^'))-path in the underlying undirected graph of D for every edge pp^' of M. Again we prove a dichotomy result for the complexity of such mixed multicut problems in terms of the pattern M. It turns out that the only polynomial cases are those where the pattern is either a polynomial graph pattern or a polynomial digraph pattern. As soon as M contains both edges and arcs, the M-mixed cut problem becomes NP-complete. Finally, we prove that the directed feedback arc set problem is NP-complete, even in the class of digraphs which have a feedback vertex set of size 2.

A star in an undirected graph is a tree in which at most one vertex has degree larger than one. A star forest is a collection of vertex disjoint stars. An out-star (in-star) in a digraph D is a star in the underlying undirected graph of D such that all edges are directed out of (into) the center. The problem of partitioning the edges of the underlying graph of a digraph D into two star forests F 0 and F 1 is known to be NP-complete. On the other hand, with the additional requirement for F0 and F 1 to be forests of out-stars the problem becomes polynomial (via an easy reduction to 2-SAT). In this article we settle the complexity of problems lying in between these two problems. Namely, we study the complexity of the related problems where we require each F i to be a forest of stars in the underlying sense and require (in different problems) that in D, F i is either a forest of out-stars, in-stars, out- or in-stars or just stars in the underlying sense.

International audience; We continue the study, initiated in [3], of the complexity of deciding whether a given digraph D has a vertex-partition into two disjoint subdigraphs with given structural properties and given minimum cardinality. Let EE be the following set of properties of digraphs: E=E={strongly connected, connected, minimum out-degree at least 1, minimum in-degree at least 1, minimum semi-degree at least 1, minimum degree at least 1, having an out-branching, having an in-branching}. In this paper we determine, for all choices of P1,P2P1,P2 from EE and all pairs of fixed positive integers k1,k2k1,k2, the complexity of deciding whether a digraph has a vertex partition into two digraphs D1,D2D1,D2 such that DiDi has property PiPi and |V(Di)|≥ki|V(Di)|≥ki, i=1,2i=1,2. We also classify the complexity of the same problems when restricted to strongly connected digraphs. The complexity of the analogous problems when P1∈HP1∈H and P2∈H∪EP2∈H∪E, where H=H={acyclic, complete, arc-less, oriented (no 2-cycle), semicomplete, symmetric, tournament} were completely characterized in [3].

International audience; We consider the following problem for oriented graphs and digraphs: Given an oriented graph (digraph) G, does it contain an induced subdivision of a prescribed digraph D? The complexity of this problem depends on D and on whether G must be an oriented graph or is allowed to contain 2-cycles. We give a number of examples of polynomial instances as well as several NP-completeness proofs.

We prove that a number of natural problems concerning the existence of arc-disjoint directed and ''undirected'' (spanning) subdigraphs in a digraph are NP-complete. Among these are the following of which the first settles an open problem due to Thomasse (see e.g. Bang-Jensen and Gutin (2009) [1, Problem 9.9.7] and Bang-Jensen and Kriesell (2009) [5,4]) and the second settles an open problem posed in Bang-Jensen and Kriesell (2009) [5]. *Given a directed graph D and a vertex s of D; does D contain an out-branching B"s^+ rooted at s such that the digraph remains connected (in the underlying sense) after removing all arcs of B"s^+? *Given a strongly connected directed graph D; does D contain a spanning strong subdigraph D^' such that the digraph remains connected (in the underlying sense) after removing all arcs of D^'?

We prove that every 3-strong semicomplete digraph on at least 5 vertices contains a spanning 2-strong tournament. Our proof is constructive and implies a polynomial algorithm for finding a spanning 2-strong tournament in a given 3-strong semicomplete digraph. We also show that there are infinitely many (2k−2)-strong semicomplete digraphs which contain no spanning k-strong tournament and conjecture that every(2k−1)-strong semicomplete digraph which is not the complete digraph K2k∗ on 2k vertices contains a spanning k-strong tournament.

We study the complexity of deciding whether a given digraph D has a vertex-partition into two disjoint subdigraphs with given structural properties. Let H and E denote the following two sets of natural properties of digraphs: H = {acyclic, complete, arcless, oriented (no 2-cycle), semicomplete, symmetric, tournament} and E = {strongly connected, connected, minimum out-degree at least 1, minimum in-degree at least 1, minimum semi-degree at least 1, minimum degree at least 1, having an out-branching, having an in-branching}. In this paper, we determine the complexity of deciding, for any fixed pair of positive integers k 1 , k 2 , whether a given digraph has a vertex partition into two digraphs D 1 , D 2 such that | V ( D i ) | ź k i and D i has property P i for i = 1 , 2 when P 1 ź H and P 2 ź H ź E . We also classify the complexity of the same problems when restricted to strongly connected digraphs.The complexity of the 2-partition problems where both P 1 and P 2 are in E is determined in the companion paper 2.

We consider the problem of finding a minimum cost cycle in a digraph with real-valued costs on the vertices. This problem generalizes the problem of finding a longest cycle and hence is NP-hard for general digraphs. We prove that the problem is solvable in polynomial time for extended semicomplete digraphs and for quasi-transitive digraphs, thereby generalizing a number of previous results on these classes. As a byproduct of our method we develop polynomial algorithms for the following problem: Given a quasi-transitive digraph D with real-valued vertex costs, find, for each j=1,2,…,|V(D)|, j disjoint paths P1,P2,…,Pj such that the total cost of these paths is minimum among all collections of j disjoint paths in D.

Arc-locally semicomplete digraphs were introduced in (Preprint, No. 10, 1993, Department of Mathematics and Computer Science, University of Southern Denmark) as a common generalization of semicomplete digraphs and semicomplete bipartite digraphs. In this note, we prove that the structure of these digraphs is very closely related to that of semicomplete and semicomplete bipartite digraphs. In fact, we show that if a strong arc-locally semicomplete digraph is neither semicomplete nor semicomplete bipartite, then it is obtained from a directed cycle by substituting independent sets of vertices for each vertex of the cycle. We also identify a new class of digraphs for which the hamiltonian cycle problem seems tractable and non-trivial. As it is the case for arc-locally semicomplete digraphs, this new class of digraphs contains all semicomplete digraphs and all semicomplete bipartite digraphs.

Splitting off a pair of edges su , sv in a graph G means replacing these two edges by a new edge uv . This operation is well known in graph theory. Let G =( V + s , E + F ) be a graph which is k -edge-connected in V and suppose that | F | is even. Here F denotes the set of edges incident with s . Lovasz (Combinatorial Problems and Exercises, North-Holland, Amsterdam, 1979) proved that if k ⩾2 then the edges in F can be split off in pairs preserving the k -edge-connectivity in V . This result was recently extended to the case where a bipartition R ∪ Q = V is given and every split edge must connect R and Q (SIAM J. Discrete Math. 12 (2) (1999) 160). In this paper, we investigate an even more general problem, where two disjoint subsets R , Q ⊂ V are given and the goal is to split off (the largest possible subset of) the edges of F preserving k -edge-connectivity in V in such a way that every split edge incident with a vertex from R has the other end-vertex in Q . Motivated by connectivity augmentation problems, we introduce another extension, the so-called split completion version of our problem. Here, the smallest set F ∗ of edges incident to s has to be found for which all the edges of F+F ∗ can be split off in the augmented graph G=(V+s, E+F+F ∗ ) preserving k -edge-connectivity and in such a way that every split edge incident with a vertex from R has the other end-vertex in Q . We solve each of the above extensions when k is even: we give min–max formulae and polynomial algorithms to find the optima. For the case when k is odd we show how to find a solution to the split completion problem using at most two edges more than the optimum.

We consider vertex colorings of edge-weighted graphs.We give tight upper and lower bounds on the chromatic number in terms of degree parameters.The results have implications for wireless scheduling in physical models of interference. A coloring of a digraph with non-negative edge weights is a partition of the vertex set into independent sets, where a set is independent if the weighted in-degree of each node within the set is less than 1. We give constructive optimal bounds on the chromatic number in terms of maximum in-degree and inductiveness of the graph.

International audience; We consider the following problem for oriented graphs and digraphs: Given a directed graph D, does it contain a subdivision of a prescribed digraph F? We give a number of examples of polynomial instances, several NP-completeness proofs as well as a number of conjectures and open problems.

We consider two generalizations of tournaments, locally semicomplete digraphs introduced in Bang-Jensen (1990) and quasi-transitive digraphs introduced in Bang-Jensen and Huang (1995). We show that results by Thomassen (1984) on linkings in highly connected tournaments are also valid for these much larger classes of digraphs. We describe a polynomial algorithm for the 2-linkage problem in quasi-transitive digraphs. We do this by reducing the problem to the case of semicomplete digraphs for which the problem was solved in Bang-Jensen and Thomassen (1992). We obtain best possible sufficient conditions in terms of connectivity for a quasi-transitive digraph to be 2-linked as well as for a quasi-transitive digraph to have a cycle through two given arcs. Finally, we point out that some of our results are valid for classes of digraphs that are much more general than locally semicomplete digraphs and quasi-transitive digraphs. In particular, there is a polynomial algorithm for the 2-linkage problem for all digraphs that can be obtained from strong semicomplete digraphs by substituting arbitrary digraphs for vertices.

We consider the problem of deciding whether a given network with integer capacities has two feasible flows x and y with prescribed balance vectors such that the arcs that carry flow in x are arc-disjoint from the arcs that carry flow in y. This generalizes a number of well-studied problems such as the existence of arc-disjoint out-branchings B"s^+, B"t^+ where the roots s, t may be the same vertex, existence of arc-disjoint spanning subdigraphs D"1, D"2 with prescribed degree sequences in a digraph (e.g. arc-disjoint cycle factors), the weak-2-linkage problem, the number partitioning problem, etc. Hence the problem is NP-complete in general. We show that the problem remains hard even for very restricted cases such as two arc-disjoint (s,t)-flows each of value 2 in a network with capacities 1 and 2 on the arcs. On the positive side, we prove that the above problem is polynomially solvable if the network is acyclic and the arc capacities as well as the desired flow values are bounded. Our algorithm for this case generalizes the algorithm (by Perl and Shiloach [14] for k=2 and Fortune, Hopcroft and Wyllie [11] for k>=3) for the k-linkage problem in acyclic digraphs. Besides, the problem is polynomial in general digraphs if all capacities are 1 and the two flows have the same balance for all vertices in N, but remains NP-complete if the network contains at least one arc with capacity 2 (and the others have capacity 1). Finally, we also show that the following properties are NP-complete to decide on digraphs: the existence of a spanning connected Eulerian subdigraph, the existence of a cycle factor in which all cycles have even length and finally the existence of a cycle factor in which all cycles have odd length.

The dicycle transversal number t(D) of a digraph D is the minimum size of a dicycle transversal of D, i. e. a set T of vertices of D such that D-T is acyclic. We study the following problem: Given a digraph D, decide if there is a dicycle B in D and a cycle C in the underlying undirected graph of D such such that B,C are disjoint. It is known that there is a polynomial time algorithm for this problem when restricted to strongly connected graphs, which actually finds B,C if they exist. We generalize this to any class of digraphs D with either t(D) not equal to 1 or t(D)=1 and a bounded number of dicycle transversals, and show that the problem is NP-complete for a special class of digraphs D with t(D)=1 and, hence, in general., IMADA-preprint-math, 20 pages

Thomassen [6] conjectured that if I is a set of k−1 arcs in a k-strong tournament T, then T−I has a Hamiltonian cycle. This conjecture was proved by Fraisse and Thomassen [3]. We prove the following stronger result. Let T=(V, A) be a k-strong tournament on n vertices and let X1, X2, [ctdot ], Xl be a partition of the vertex set V of T such that [mid ]X1[mid ][les ][mid ]X2[mid ] [les ][ctdot ][les ][mid ]Xl[mid ]. If k[ges ][sum ] l−1i=1[lfloor ] [mid ]Xi[mid ]/2[rfloor ]+[mid ]Xl[mid ], then T−∪li=1 {xy∈A[ratio ]x, y∈Xi} has a Hamiltonian cycle. The bound on k is sharp.

A path or cycle in an edge-coloured multigraph is called alternating if its successive edges differ in colour. We survey results of both theoretical and algorithmic character concerning alternating cycles and paths in edge-coloured multigraphs. We also show useful connections between the theory of paths and cycles in bipartite digraphs and the theory of alternating paths and cycles in edge-coloured graphs.

We consider digraphs — called extended locally semicomplete digraphs, or extended LSD's, for short — that can be obtained from locally semicomplete digraphs by substituting independent sets for vertices. We characterize Hamiltonian extended LSD's as well as extended LSD's containing Hamiltonian paths. These results as well as some additional ones imply polynomial algorithms for finding a longest path and a longest cycle in an extended LSD. Our characterization of Hamiltonian extended LSD's provides a partial solution to a problem posed by Haggkvist (1993). Combining results from this paper with some general results derived for the so-called totally Φ 0 -decomposable digraphs in Bang-Jensen and Gutin (1996) we prove that the longest path problem is polynomially solvable for totally Φ 0 -decomposable digraphs — a fairly wide family of digraphs which is a common generalization of acyclic digraphs, semicomplete multipartite digraphs, extended LSD's and quasi-transitive digraphs. Similar results are obtained for the longest cycle problem and other problems on cycles in subfamilies of totally Φ 0 -decomposable digraphs. These polynomial algorithms are a natural and fairly deep generalization of algorithms obtained for quasi-transitive digraphs in Bang-Jensen and Gutin (1996) in order to solve a problem posed by N. Alon.

Thomassen (1991) proved that there is no degree of strong connectivity which guarantees a cycle through two given vertices in a digraph. In this paper we consider a large family of digraphs, including symmetric digraphs (i.e. digraphs obtained from undirected graphs by replacing each edge by a directed cycle of length two), semicomplete bipartite digraphs, locally semicomplete digraphs and all digraphs that can be obtained from acyclic digraphs and those mentioned above, by repeated substitutions of digraphs from one of these classes for vertices. We prove that for every natural number k , every k -strong digraph D from the family above is k -cyclic, i.e. for every set X of k vertices of D , there exists a cycle of D containing all the vertices of X . In particular, this implies that every k -strong quasi-transitive digraph is k -cyclic. We prove that if X is a set of vertices in a k -strong digraph D such that the maximum size of an independent set in the digraph induced by X is at most k , then D has a collection of disjoint cycles (possibly one) covering all the vertices of X . This generalizes a previous result by Jackson and Ordaz (1985). Finally, we consider k -cyclic semicomplete multipartite digraphs (SMD). We conjecture that every k -strong SMD is k -cyclic and provide some support for this conjecture.

We characterize weakly Hamiltonian-connected ordinary multipartite tournaments. Our result generalizes such a characterization for tournaments by Thomassen and implies a polynomial algorithm to decide the existence of a Hamiltonian path connecting two given vertices in an ordinary multipartite tournament and finds one, if it exists.

We prove that the arc set of every 2-arc-strong locally semicomplete digraph D=(V,A) which is not the second power of an even cycle can be partitioned into two sets A"1,A"2 such that both of the spanning subdigraphs D"1=(V,A"1) and D"2=(V,A"2) are strongly connected. Moreover, we show that such a partition (if it exists) can be obtained in polynomial time. This generalizes a result from Bang-Jensen and Yeo (2004) [5] on semicomplete digraphs and implies that every 2-arc-strong locally semicomplete digraph D=(V,A) has a pair of arc-disjoint branchings B"u^-,B"v^+ such that B"u^- is an in-branching rooted at u and B"v^+ is an out-branching rooted at v where u,v@?V can be chosen arbitrarily. This generalizes results from Bang-Jensen (1991) [2] for tournaments and Bang-Jensen and Yeo (2004) [5] for semicomplete digraphs.

Wegner proved that a chordal graph is a proper interval graph if and only if it is claw-free, net-free and tent-free. We observe that in fact the characterization can be refined to say that a chordal graph is a proper interval graph if and only if it is claw-free, net-free and not a multiple of the tent. This observation implies that a chordal graph is a proper circular arc graph if and only if it is claw-free and net-free. A further implication of this result is that a chordal graph can be oriented as a local tournament - an oriented raph in which the predecessors as well as the successors of any vertex induce a tournament - if and only if it is claw-free and net-free.

In this paper we introduce a generalization of digraphs that are locally tournaments (and hence of tournaments). This is the class of in-tournament digraphs-the set of predecessors of every vertex induces a tournament. We show that many properties of local tournament digraphs can be extended even to in-tournament digraphs. For instance, any strongly connected in-tournament digraph has a directed hamiltonian cycle. We prove that the underlying graph of any in-tournament digraph is l-homotopic. We investigate the problem of which graphs are orientable as in-tournament digraphs and prove that any graph representable as an intersection subgraph of a unicyclic graph can be so oriented. It is shown that there is a polynomial algorithm for recognizing those graphs that can be oriented as in-tournament digraphs.

Let H be a directed graph whose vertices are called colours. An H-colouring of a digraph G is an assignment of these colours to the vertices of G so that if g is adjacent to g ′ in G then colour( g ) is adjacent to colour( g ′) in H (i.e., a homomorphism G → H ). In this paper we continue the study of the H-colouring problem , that is, the decision problem ‘Is there an H -colouring of a given digraph G ?’ It follows from a result of Hell and Nesetřil that this problem is NP-complete whenever H contains a symmetric odd cycle. We consider digraphs for which the symmetric part of H is bipartite, that is, digraphs H which can be constructed from the equivalence digraph of an undirected bipartite graph by adding some arcs. We establish some sufficient conditions for these H -colouring problems to be NP-complete. A complete classification is established for the subclass of ‘partitionable digraphs’, which we introduce.

A problem session was held during the Julius Petersen Graph TheoryConference, Hindsgavl, Denmark, July 1-6, 1990. The following is a list of theproblems presented in connection with the meeting. We thank all contributors.Special thanks to Herbert Fleischner, who chaired the problem session and latercollected the problems in writing from the participants.

In this paper we continue the study, started by J. Bang-Jensen (1989), of locally semicomplete digraphs, a generalization of tournaments, to which many well-known tournament results extend. The underlying undirected graphs of the locally semicomplete digraphs are precisely the proper circular-arc graphs. We give new results on the structure of locally semicomplete digraphs, as well as several examples of properties of tournaments and semicomplete digraphs that do not extend to the class of locally semicomplete digraphs.

The concept of connectivity is one of the most fundamental concepts in (directed) graph theory. There are numerous practical problems which can be formulated as (local) connectivity problems for digraphs and hence a significant part of this theory is also important from a practical point of view. Results on connectivity are often quite difficult and a deep insight may be required before one can obtain results in the area. Because of the very large number of important results on connectivity, we will devote this chapter as well as Chapters 10, 11, 12 and 14 to this area. Several connectivity problems, such as the connectivity augmentation problems in Sections 14.2 and 14.3, are of significant practical interest. These chapters illustrate several important topics as well as techniques that have been successful in solving local or global connectivity problems.

In this paper we collect a substantial number of challenging open problems and conjectures on connectivity, paths, trees and cycles in tournaments and classes of digraphs which contain tournaments as a subclass. The list is by no means exhaustive but is meant to show that the area has a large number of interesting open problems. We also mention problems for general digraphs when they are relevant in the context.

We show that the following problem is NP-complete: Given a digraph D and distinct vertices s,t of D, decide whether the underlying graph of D contains two internally disjoint (s,t)-paths P and Q such that P is a directed (s,t)-path in D. Using this result we characterize those mixed linkage problems which are polynomially solvable (assuming P≠NP). This complements the classical dichotomy by Fortune, Hopcroft, and Wyllie classifying those directed linkage problems that are polynomially solvable. We furthermore show that, contrary to the case of directed linkages in digraphs, the mixed problem remains NP-complete for acyclic digraphs.

We give good characterizations in Edmonds' sense for the following problems for tournaments. 1. (1) Given a tournament T and v 1 , v 2 ∈ V ( T ), possibly v 1 = v 2 , when do there exist edge-disjoint branchings F v 1 + , F v 2 − , such that F v 1 + is an out-branching rooted at v 1 and F v 2 − is an in-branching rooted at v 2 ? 2. (2) Given a strong tournament T and x 1 , x 2 , y 1 , y 2 ∈ V ( T ) all different, when do there exist edge-disjoint ( x 1 , y 1 )-, ( x 2 , y 2 )-paths in T ? 3. (3) Given a strong tournament T and a , b , c ∈ V ( T ) all different, when do there exist edge-disjoint ( a, b )-, ( b, c )-paths in T ? Problem (2) is known to be NP-complete for digraphs in general and we give a proof by C. Thomassen that problem (1) is NP-complete for digraphs in general.

We consider the minimum cycle factor problem: given a digraph D, find the minimum number kmin(D) of vertex disjoint cycles covering all vertices of D or verify that D has no cycle factor. There is an analogous problem for paths, known as the minimum path factor problem. Both problems are NP-hard for general digraphs as they include the Hamilton cycle and path problems, respectively.In 1994 Gutin [G. Gutin, Polynomial algorithms for finding paths and cycles in quasi-transitive digraphs, Australas. J. Combin. 10 (1994) 231–236] proved that the minimum path factor problem is solvable in polynomial time, for the class of quasi-transitive digraphs, and so is the Hamilton cycle problem.As the minimum cycle factor problem is analogous to the minimum path factor problem and is a generalization of the Hamilton cycle problem, it is therefore a natural question whether this problem is also polynomially solvable, for quasi-transitive digraphs.We conjecture that the problem of deciding, for a fixed k, whether a quasi-transitive digraph D has a cycle factor with at most k cycles is polynomial, and we verify this conjecture for k=3.We introduce the notion of an irreducible cycle factor and show how to convert a given cycle factor into an irreducible one in polynomial time when the input digraph is quasi-transitive. Finally, we show that even though this process will often reduce the number of cycles considerably, it does not always yield a minimum cycle factor.

We provide a characterization of the cases when the greedy algorithm may produce the unique worst possible solution for the problem of finding a minimum weight base in an independence system when the weights are taken from a finite range. We apply this theorem to TSP and the minimum bisection problem. The practical message of this paper is that the greedy algorithm should be used with great care, since for many optimization problems its usage seems impractical even for generating a starting solution (that will be improved by a local search or another heuristic).

The purpose of this chapter is to describe basic elements of the theory and applications of network flows. This topic is probably the most important single tool for applications of digraphs and perhaps even of graphs as a whole. At the same time, from a theoretical point of view, flow problems constitute a beautiful common generalization of shortest path problems and problems such as finding internally (arc)-disjoint paths from a given vertex to another. The theory of flows is well understood and fairly simple. This, combined with the enormous applicability to real-life problems, makes flows a very attractive topic to study. From a theoretical point of view, flows are well understood as far as the basic questions, such as finding a maximum flow from a given source to a given sink or characterizing the size of such a flow, are concerned. However, the topic is still a very active research field and there are challenging open problems such as deciding whether an O(nm) algorithm exists for the general maximum flow problem.

Let T be a semicomplete digraph on n vertices. Let ak(T) denote the minimum number of arcs whose addition to T results in a k-connected semicomplete digraph and let rk(T) denote the minimum number of arcs whose reversal in T results in a k-connected semicomplete digraph. We prove that if n[ges ]3k−1, then ak(T)=rk(T). We also show that this bound on n is best possible.

Recently, Huang (1995) gave a characterization of local tournaments. His characterization involves arc-reversals and therefore may not be easily used to solve other structural problems on locally semicomplete digraphs (where one deals with a fixed locally semicomplete digraph). In this paper we derive a classification of locally semicomplete digraphs which is very useful for studying structural properties of locally semicomplete digraphs and which does not depend on Huang's characterization. An advantage of this new classification of locally semicomplete digraphs is that it allows one to prove results for locally semicomplete digraphs without reproving the same statement for tournaments. We use our result to characterize pancyclic and vertex pancyclic locally semicomplete digraphs and to show the existence of a polynomial algorithm to decide whether a given locally semicomplete digraph has a kernel.

A multipartite tournament is an orientation of a complete k-partite graph for some k ⩾ 2. A factor of a digraph D is a collection of vertex disjoint cycles covering all the vertices of D. We show that there is no degree of strong connectivity which together with the existence of a factor will guarantee that a multipartite tournament is Hamiltonian. Our main result is a sufficient condition for a multipartite tournament to be Hamiltonian. We show that this condition is general enough to provide easy proofs of many existing results on paths and cycles in multipartite tournaments. Using this condition, we obtain a best possible lower bound on the length of a longest cycle in any strongly connected multipartite tournament.

We consider the so-called Path Partition Conjecture for digraphs which states that for every digraph, D, and every choice of positive integers, @l"1,@l"2, such that @l"1+@l"2 equals the order of a longest directed path in D, there exists a partition of D into two digraphs, D"1 and D"2, such that the order of a longest path in D"i is at most @l"i, for i=1,2. We prove that certain classes of digraphs, which are generalizations of tournaments, satisfy the Path Partition Conjecture and that some of the classes even satisfy the conjecture with equality.