Given an oriented graph $D$, the inversion of a subset $X$ of vertices consists in reversing the orientation of all arcs with both endpoints in $X$. When the subset $X$ is of size $p$ (resp. at most $p$), this operation is called an $(=p)$-inversion (resp. $(\leq p)$-inversion). Then, an oriented graph is $(=p)$-invertible if it can be made acyclic by a sequence of $p$-inversions. We observe that, for $n=|V(D)|$, deciding whether $D$ is $(=n-1)$-invertible is equivalent to deciding whether $D$ is acyclically pushable, and thus NP-complete. In all other cases, when $p \neq n-1$, we construct a polynomial-time algorithm to decide $(=p)$-invertibility. We then consider the $(= p)$-inversion number, $\text{inv}^{= p}(D)$ (resp. $(\leq p)$-inversion number, $\text{inv}^{\leq p}(D)$), defined as the minimum number of $(=p)$-inversions (resp. $(\leq p)$-inversions) rendering $D$ acyclic. We show that every $(=p)$-invertible digraph $D$ satisfies $\text{inv}^{= p}(D) \leq |A(D)|$ for every integer $p\geq 2$. When $p$ is even, we bound $\text{inv}^{= p}$ by a (linear) function of the feedback arc set number, and rule out the existence of any bounding function for odd $p$. Finally, we study the complexity of deciding whether the $(= p)$-inversion number, or the $(\leq p)$-inversion number, of a given oriented graph is at most a given integer $k$. For any fixed positive integer $p \geq 2$, when $k$ is part of the input, we show that both problems are NP-hard even in tournaments. In general oriented graphs, we prove $W[1]$-hardness for both problems when parameterized by $p$, even for $k=1$. In contrast, we exhibit polynomial kernels in $p + k$ for both problems in tournaments.

A digraph is semicomplete if it has no pair of non-adjacent vertices. It is complete if every pair of distinct vertices induces a 2-cycle. A digraph is semicomplete multipartite if it can be obtained from a semicomplete digraph D by choosing a collection of vertex-disjoint subsets X1,…,Xc of V(D) and then deleting all arcs both of whose end-vertices lie inside some Xi. We can also think of a semicomplete digraph as being obtained from a semicomplete multipartite digraph on the same vertex set and partite sets V1,…,Vc by adding the arcs of a semicomplete digraph Di on Vi for each partite set Vi. It is well known that both the hamiltonian path and the hamiltonian cycle problem can be solved in polynomial time for semicomplete multipartite digraphs. In this paper we study the complexity of finding a hamiltonian path or cycle in a semicomplete digraph S which is obtained as above from a semicomplete multipartite digraph D and semicomplete digraphs Di=(Vi,Ai), i∈[c] such that the path or cycle uses as few arcs of A1∪…Ac as possible. We obtain a number of results for the case when each Di is a complete digraph. Already this case is highly nontrivial in the cycle case and the complexity is still open. We show how to find a Hamiltonian path which uses as few arcs from the Di’s as possible in polynomial time and obtain a number of results, both structural and algorithmic on hamiltonian cycles that use the minimum or close to the minimum number of arcs from the Di’s. Our results imply the polynomial solvability of some special cases of the NP-complete {0,1}-TSP problem. Finally we show that two natural questions about properties of quasi-hamiltonian cycles, that is, cycles meeting all partite sets in semicomplete multipartite digraphs are NP-complete.

In the Vertex Connectivity Survivable Network Design (VC-SNDP) problem, the input is a graph G and a function d: V(G) × V(G) → ℕ that encodes the vertex-connectivity demands between pairs of vertices. The objective is to find the smallest subgraph H of G that satisfies all these demands. It is a well-studied NP-complete problem that generalizes several network design problems. We consider the case of uniform demands, where for every vertex pair (u,v) the connectivity demand d(u,v) is a fixed integer κ. It is an important problem with wide applications. We study this problem in the realm of Parameterized Complexity. In this setting, in addition to G and d we are given an integer 𝓁 as the parameter and the objective is to determine if we can remove at least 𝓁 edges from G without violating any connectivity constraints. This was posed as an open problem by Bang-Jansen et.al. [SODA 2018], who studied the edge-connectivity variant of the problem under the same settings. Using a powerful classification result of Lokshtanov et al. [ICALP 2018], Gutin et al. [JCSS 2019] recently showed that this problem admits a (non-uniform) FPT algorithm where the running time was unspecified. Further they also gave an (uniform) FPT algorithm for the case of κ = 2. In this paper we present a (uniform) FPT algorithm any κ that runs in time 2^{O(κ² 𝓁⁴ log 𝓁)}⋅ |V(G)|^O(1). Our algorithm is built upon new insights on vertex connectivity in graphs. Our main conceptual contribution is a novel graph decomposition called the Wheel decomposition. Informally, it is a partition of the edge set of a graph G, E(G) = X₁ ∪ X₂ … ∪ X_r, with the parts arranged in a cyclic order, such that each vertex v ∈ V(G) either has edges in at most two consecutive parts, or has edges in every part of this partition. The first kind of vertices can be thought of as the rim of the wheel, while the second kind form the hub. Additionally, the vertex cuts induced by these edge-sets in G have highly symmetric properties. Our main technical result, informally speaking, establishes that "nearly edge-minimal’’ κ-vertex connected graphs admit a wheel decomposition - a fact that can be exploited for designing algorithms. We believe that this decomposition is of independent interest and it could be a useful tool in resolving other open problems.

As usual λ(G) denotes the edge-connectivity of the graph G. It was shown in [2] that every graph G contains a spanning (λ(G)+1)-partite subgraph H such that λ(H)=λ(G) and one can find such a spanning subgraph in polynomial time. We determine the complexity of deciding, for given positive integers r,k whether a graph contains a spanning r-colourable subgraph which is k-edge-connected. We show that the problem is polynomially solvable when r>k and NP-complete otherwise. In fact, combined with the result from [2] above, this means that the problem is polynomially solvable precisely when r is such that every k-edge-connected graph has a spanning r-colourable subgraph which is k-edge-connected. One can show that all graphs whose edge set decomposes into k edge-disjoint spanning trees are 2k-colourable. We consider the problem of deciding whether a given graph G has a collection of k edge-disjoint spanning trees whose union forms an r-colourable spanning subgraph H of G. We show that this problem is polynomially solvable when r≥2k and NP-complete for all other values of r. We also determine the complexity of the analogous problem of deciding whether a digraph D has a collection of k arc-disjoint out-branchings such that the spanning subdigraph formed by the union of the arcs in the branchings is r-colourable.

Abstract A directed graph D is semicomplete if for every pair x, y of vertices of D, there is at least one arc between x and y. Thus, a tournament is a semicomplete digraph. In the Directed Component Order Connectivity (DCOC) problem, given a digraph $$D=(V,A)$$ D = ( V , A ) and a pair of natural numbers k and $$\ell $$ ℓ , we are to decide whether there is a subset X of V of size k such that the largest strongly connected component in $$D-X$$ D - X has at most $$\ell $$ ℓ vertices. Note that DCOC reduces to the Directed Feedback Vertex Set problem for $$\ell =1.$$ ℓ = 1 . We study the parameterized complexity of DCOC for general and semicomplete digraphs with the following parameters: $$k, \ell ,\ell +k$$ k , ℓ , ℓ + k and $$n-\ell $$ n - ℓ . In particular, we prove that DCOC with parameter k on semicomplete digraphs can be solved in time $$O^*(2^{16k})$$ O ∗ ( 2 16 k ) but not in time $$O^*(2^{o(k)})$$ O ∗ ( 2 o ( k ) ) unless the Exponential Time Hypothesis (ETH) fails. The upper bound $$O^*(2^{16k})$$ O ∗ ( 2 16 k ) implies the upper bound $$O^*(2^{16(n-\ell )})$$ O ∗ ( 2 16 ( n - ℓ ) ) for the parameter $$n-\ell .$$ n - ℓ . We complement the latter by showing that there is no algorithm of time complexity $$O^*(2^{o({n-\ell })})$$ O ∗ ( 2 o ( n - ℓ ) ) unless ETH fails. Finally, we improve (in dependency on $$\ell $$ ℓ ) the upper bound of Göke, Marx and Mnich (2019) for the time complexity of DCOC with parameter $$\ell +k$$ ℓ + k on general digraphs from

Let $D$ be a digraph, let $p \geq 1$ be an integer, and let $f: V(D) \to \mathbb{N}_0^p$ be a vector function with $f=(f_1,f_2,\ldots,f_p)$. We say that $D$ has an $f$-partition if there is a partition $(V_1,V_2,\ldots,V_p)$ of the vertex set of $D$ such that, for all $i \in [1,p]$, the digraph $D_i=D[V_i]$ is weakly $f_i$-degenerate, that is, in every nonempty subdigraph $D'$ of $D_i$ there is a vertex $v$ such that $\min\{d_{D'}^+(v), d_{D'}^-(v)\} < f_i(v)$. In this paper, we prove that the condition $f_1(v) + f_2(v) + \cdots + f_p(v) \geq \max \{d_D^+(v),d_D^-(v)\}$ for all $v \in V(D)$ is almost sufficient for the existence of an $f$-partition and give a full characterization of the bad pairs $(D,f)$. Among other applications, this leads to a generalization of Brooks' theorem as well as the list-version of Brooks' theorem for digraphs, where a coloring of a digraph is a partition of the digraph into acyclic induced subdigraphs. We furthermore obtain a result bounding the $s$-degenerate chromatic number of a digraph in terms of the maximum of maximum in-degree and maximum out-degree.

We study the complexity of deciding whether a given digraph D=(V,A) admits a partition (A1,A2) of its arc set such that each of the corresponding digraphs D1=(V,A1) and D2=(V,A2) satisfy some given prescribed property. We mainly focus on the following 15 properties: being bipartite, being connected, being strongly connected, being acyclic (spanning or not necessarily spanning), containing an in-branching, containing an out-branching, having some in-degree (or out-degree) conditions, satisfying some conditions on the number of arcs, being balanced (connected or not) or being a cycle. Combined with previous research, our work leads to a complete classification (in terms of being polynomial or NP-complete) of the complexity of 120 arc-partitioning problems on digraphs.

A directed graph D is semicomplete if for every pair x,y of vertices of D, there is at least one arc between x and y. Thus, a tournament is a semicomplete digraph. In the Directed Component Order Connectivity (DCOC) problem, given a digraph D = (V,A) and a pair of natural numbers k and 𝓁, we are to decide whether there is a subset X of V of size k such that the largest strong connectivity component in D-X has at most 𝓁 vertices. Note that DCOC reduces to the Directed Feedback Vertex Set problem for 𝓁 = 1. We study parameterized complexity of DCOC for general and semicomplete digraphs with the following parameters: k, 𝓁, 𝓁+k and n-𝓁. In particular, we prove that DCOC with parameter k on semicomplete digraphs can be solved in time O^*(2^(16k)) but not in time O^*(2^o(k)) unless the Exponential Time Hypothesis (ETH) fails. The upper bound O^*(2^(16k)) implies the upper bound O^*(2^(16(n-𝓁))) for the parameter n-𝓁. We complement the latter by showing that there is no algorithm of time complexity O^*(2^o(n-𝓁)) unless ETH fails. Finally, we improve (in dependency on 𝓁) the upper bound of Göke, Marx and Mnich (2019) for the time complexity of DCOC with parameter 𝓁+k on general digraphs from O^*(2^O(k𝓁 log (k𝓁))) to O^*(2^O(klog (k𝓁))). Note that Drange, Dregi and van 't Hof (2016) proved that even for the undirected version of DCOC on split graphs there is no algorithm of running time O^*(2^o(klog 𝓁)) unless ETH fails and it is a long-standing problem to decide whether Directed Feedback Vertex Set admits an algorithm of time complexity O^*(2^o(klog k)).

In the Survivable Network Design Problem (SNDP), the input is an edge-weighted (di)graph G and an integer ruυ for every pair of vertices u, υ ∊ V(G). The objective is to construct a subgraph H of minimum weight which contains ruυ edge-disjoint (or node-disjoint) u-υ paths. This is a fundamental problem in combinatorial optimization that captures numerous well-studied problems in graph theory and graph algorithms. Consequently, there is a long line of research into exact-polynomial time algorithms as well as approximation algorithms for various restrictions of this problem. An important restriction of this problem is one where the connectivity demands are the same for every pair of vertices. In this paper, we first consider the edge-connectivity version of this problem which we call λ-Edge Connected Subgraph (λ-ECS). In this problem, the input is a λ-edge connected (di)graph G and an integer k and the objective is to check whether G contains a spanning subgraph H that is also λ-edge connected and H excludes at least k edges of G. In other words, we are asked to compute a maximum subset of edges, of cardinality at least k, which may be safely deleted from G without affecting its connectivity. If we replace λ-edge connectivity with λ-vertex connectivity we get the λ-Vertex Connected Subgraph (λ-VCS) problem. We show that λ-ECS is fixed-parameter tractable (FPT) for both graphs and digraphs even if the (di)graph has nonnegative real weights on the edges and the objective is to exclude from H, some edges of G whose total weight exceeds a prescribed value. In particular, we design an algorithm for the weighted variant of the problem with running time 2O(k log k) |V(G)|O(1). We follow up on this result and obtain a polynomial compression for λ-ECS on unweighted graphs. As a direct consequence of our results, we obtain the first FPT algorithm for the parameterized version of the classical Minimum Equivalent Graph (MEG) problem. We also show that λ-Ves is FPT on digraphs; however the problem on undirected graphs remains open. Finally, we complement our algorithmic findings by showing that SNDP is W[1]-hard for both arc and vertex connectivity versions on digraphs. The core of our algorithms is composed of new combinatorial results on connectivity in digraphs and undirected graphs.

We consider the 2-edge-connectivity augmentation problem: given a graph S = (V,E) which is not 2-edge-connected and a set of new edges E′ ⊆ V × V with nonnegative weights, find a minimum cost subset X of E′ such that adding the edges of X to S results in a 2-edge-connected graph. A practical application is the extension of an existing telecommunication network to become robust against single link failures. We compare, experimentally, different algorithms for solving general and large-scale instances. This includes exact methods based on mathematical programming, simple construction heuristics, and metaheuristics. As part of the design of heuristics, we consider different neighborhood structures for local search, among which is a very large scale neighborhood. In all cases, we exploit approaches through the graph formulation as well as through an equivalent set covering formulation. The results indicate that exact solutions by means of a basic integer programming model can be obtained in reasonably short time even on networks with 800 vertices and around 287,000 edges. Alternatively, an advanced heuristic algorithm based on subgradient optimization and iterated greedy often finds the optimal solution and is very fast. All previous benchmark instances are easily solved to optimality and new, larger instances are introduced and studied. © 2010 Wiley Periodicals, Inc. NETWORKS, 2010

Abstract The concept of persistent directed graphs was introduced by Hendrickx et al. to help analyze the stability of autonomous agent systems. They provided a combinatorial characterization for persistence but the complexity of testing persistence remained open. In this note we show that for directed graphs D with ∑vεV(D) min{δD(v), 2} ≤ 2∣V(D)∣ − 3 persistence can be tested in polynomial time, where δD(v) denotes the out‐degree of vertex v in D. This family of directed graphs includes acyclic digraphs (for which an efficient algorithm was known) as well as all digraphs with a leader‐follower structure. We also discuss some related orientation problems. Among others we point out that the existence of an acyclic persistent orientation can be tested in polynomial time for all graphs. © 2008 Wiley Periodicals, Inc. NETWORKS, 2008

We consider the problem of finding a strongly connected spanning subdigraph with the minimum number of arcs in a strongly connected digraph. This problem is NP-hard for general digraphs since it generalizes the Hamiltonian cycle problem. We show that the problem is polynomially solvable for quasi-transitive digraphs. We describe the minimum number of arcs in such a spanning subdigraph of a quasi-transitive digraph in terms of the path covering number. Our proofs are based on a number of results (some of which are new and interesting in their own right) on the structure of cycles and paths in quasi-transitive digraphs and in extended semicomplete digraphs. In particular, we give a new characterization of the longest cycle in an extended semicomplete digraph. Finally, we point out that our proofs imply that the MSSS problem is solvable in polynomial time for all digraphs that can be obtained from strong semicomplete digraphs on at least two vertices by replacing each vertex with a digraph belonging to a family of digraphs whose path covering number can be decided in polynomial time.

We introduce two new classes of graphs which we call convex-round, respectively concave-round graphs. Convex-round (concave-round) graphs are those graphs whose vertices can be circularly enumerated so that the (closed) neighborhood of each vertex forms an interval in the enumeration. Hence the two classes transform into each other by taking complements. We show that both classes of graphs have nice structural properties. We observe that the class of concave-round graphs properly contains the class of proper circular arc graphs and, by a result of Tucker [ Pacific J. Math., 39 (1971), pp. 535--545], is properly contained in the class of general circular arc graphs. We point out that convex-round and concave-round graphs can be recognized in O(n+m) time (here n denotes the number of vertices and m the number of edges of the graph in question). We show that the chromatic number of a graph which is convex-round (concave-round) can be found in time O(n+m) (O(n 2 )). We describe optimal O(n+m) time algorithms for finding a maximum clique, a maximum matching, and a Hamiltonian cycle (if one exists) for the class of convex-round graphs. Finally, we pose a number of open problems and conjectures concerning the structure and algorithmic properties of the two new classes and a related third class of graphs.

In the well-solved edge-connectivity augmentation problem we must find a minimum cardinality set F of edges to add to a given undirected graph to make it k-edge-connected. This paper solves the generalization where every edge of F must go between two different sets of a given partition of the vertex set. A special case of this partition-constrained problem, previously unsolved, is increasing the edge-connectivity of a bipartite graph to k while preserving bipartiteness. Based on this special case we present an application of our results in statics. Our solution to the general partition-constrained problem gives a min-max formula for |F| which includes as a special case the original min-max formula of Cai and Sun [Networks, 19 (1989), pp. 151--172] for the problem without partition constraints. When k is even the min-max formula for the partition-constrained problem is a natural generalization of the unconstrained version. However, this generalization fails when k is odd. We show that at most one more edge is needed when k is odd and we characterize the graphs that require such an extra edge. We give a strongly polynomial algorithm that solves our problem in time O(n(m + nlog n)log n). Here n and m denote the number of vertices and distinct edges of the given graph, respectively. This bound is identical to the best-known time bound for the problem without partition constraints. Our algorithm is based on the splitting off technique of Lovász, like several known efficient algorithms for the unconstrained problem. However, unlike previous splitting algorithms, when k is odd our algorithm must handle obstacles that prevent all edges from being split off. Our algorithm is of interest even when specialized to the unconstrained problem, because it produces an asymptotically optimum number of distinct splits.

Given a simple graph G=(V,E), our goal is to find a smallest set F of new edges such that G=(V,E\cup F) is k-edge-connected and simple. Recently this problem was shown to be NP-complete. In this paper we prove that if OPT_P^k$ is high enough---depending on k only---then OPT _S^k= OPT_P^k$ holds, where OPT_S^k$ (OPT_P^k$) is the size of an optimal solution of the augmentation problem with (without) the simplicity-preserving requirement, respectively. Furthermore, OPT_S^k- OPT _P^k\leq g(k) holds for a certain (quadratic) function of k. Based on these facts an algorithm is given which computes an optimal solution in time O(n4) for any fixed k. Some of these results are extended to the case of nonuniform demands as well.

Given a simple graph G=(V, E), the goal is to find a smallest set F of new edges such that G=(V, E/spl cup/F) is /spl kappa/ edge connected and simple. Very recently this problem was shown to be NP hard by T. Jordan (1997). We prove that if OPT/sub P//sup /spl kappa// is high enough-depending on /spl kappa/ only-then OPT/sub S//sup /spl kappa//=OPT/sub P//sup /spl kappa// holds, where OPT/sub S//sup /spl kappa// (OPT/sub P//sup /spl kappa//) is the size of an optimal solution of the augmentation problem with (without) the simplicity preserving requirement, respectively. Furthermore, OPT/sub S//sup /spl kappa//-OPT/sub P//sup /spl kappa///spl les/g(/spl kappa/) holds for a certain (quadratic) function of /spl kappa/. Based on these results an algorithm is given which computes an optimal solution in time O(n/sup 4/) for any fixed /spl kappa/. Most of these results are extended to the case of non-uniform demands, as well.

Generalizing and unifying earlier results of W. Mader, and A. Frank and B. Jackson, we prove two splitting theorems concerning mixed graphs. By invoking these theorems we obtain min-max formulae for the minimum number of new edges to be added to a mixed graph so that the resulting graph satisfies local edge-connectivity prescriptions. An extension of Edmonds’s theorem on disjoint arborescences is also deduced along with a new sufficient condition for the solvability of the edge-disjoint paths problem in digraphs. The approach gives rise to strongly polynomial algorithms for the corresponding optimization problems.

This paper presents polynomially bounded algorithms for finding a cycle through any two prescribed arcs in a semicomplete digraph and for finding a cycle through any two prescribed vertices in a complete k-partite oriented graph. It is also shown that the problem of finding a maximum transitive subtournament of a tournament and the problem of finding a cycle through a prescribed arc set in a tournament are both NP-complete.

The following problem, known as the H-colouring problem, is studied. An H-colouring of a directed graph D is a mapping $f:V( D ) \to V( H )$ such that $( f( x ),f( y ) )$ is an edge of H whenever $( x,y )$ is an edge of D. The H-colouring problem is the following. Instance: A directed graph D. Question: Does there exist an H-colouring of D? In this paper it is shown that for semicomplete digraphs T the T-colouring problem is NP-complete when T has more than one directed cycle, and polynomially decidable otherwise.