TY - JOUR

T1 - Complexity of (arc)-connectivity problems involving arc-reversals or deorientations

AU - Bang-Jensen, Jørgen

AU - Hörsch, Florian

AU - Kriesell, Matthias

N1 - Funding Information:
Research supported by the Independent Research Fund Denmark under grant number DFF 7014-00037B .
Publisher Copyright:
© 2023 Elsevier B.V.

PY - 2023/9/21

Y1 - 2023/9/21

N2 - By a well known theorem of Robbins, a graph G has a strongly connected orientation if and only if G is 2-edge-connected and it is easy to find, in linear time, either a cut edge of G or a strong orientation of G. A result of Durand de Gevigney shows that for every k≥3 it is NP-hard to decide if a given graph G has a k-strong orientation. Thomassen showed that one can check in polynomial time whether a given graph has a 2-strong orientation. This implies that for a given digraph D we can determine in polynomial time whether we can reorient (=reverse) some arcs of D=(V,A) to obtain a 2-strong digraph D′=(V,A′). This naturally leads to the question of determining the minimum number of such arcs to reverse before the resulting graph is 2-strong. In this paper we show that finding this number is NP-hard. If a 2-connected graph G has no 2-strong orientation, we may ask how many of its edges we may orient so that the resulting mixed graph is still 2-strong. Similarly, we may ask for a 2-edge-connected graph G how many of its edges we can orient such that the resulting mixed graph remains 2-arc-strong. We prove that when restricted to graphs satisfying suitable connectivity conditions, both of these problems are equivalent to finding the minimum number of edges we must double in a 2-edge-connected graph in order to obtain a 4-edge-connected graph. Using this, we show that all these three problems are NP-hard. Finally, we consider the operation of deorienting an arc uv of a digraph D meaning replacing it by an undirected edge between the same vertices. In terms of connectivity properties, this is equivalent to adding the opposite arc vu to D. We prove that for every ℓ≥3 it is NP-hard to find the minimum number of arcs to deorient in a digraph D in order to obtain an ℓ-strong digraph D′.

AB - By a well known theorem of Robbins, a graph G has a strongly connected orientation if and only if G is 2-edge-connected and it is easy to find, in linear time, either a cut edge of G or a strong orientation of G. A result of Durand de Gevigney shows that for every k≥3 it is NP-hard to decide if a given graph G has a k-strong orientation. Thomassen showed that one can check in polynomial time whether a given graph has a 2-strong orientation. This implies that for a given digraph D we can determine in polynomial time whether we can reorient (=reverse) some arcs of D=(V,A) to obtain a 2-strong digraph D′=(V,A′). This naturally leads to the question of determining the minimum number of such arcs to reverse before the resulting graph is 2-strong. In this paper we show that finding this number is NP-hard. If a 2-connected graph G has no 2-strong orientation, we may ask how many of its edges we may orient so that the resulting mixed graph is still 2-strong. Similarly, we may ask for a 2-edge-connected graph G how many of its edges we can orient such that the resulting mixed graph remains 2-arc-strong. We prove that when restricted to graphs satisfying suitable connectivity conditions, both of these problems are equivalent to finding the minimum number of edges we must double in a 2-edge-connected graph in order to obtain a 4-edge-connected graph. Using this, we show that all these three problems are NP-hard. Finally, we consider the operation of deorienting an arc uv of a digraph D meaning replacing it by an undirected edge between the same vertices. In terms of connectivity properties, this is equivalent to adding the opposite arc vu to D. We prove that for every ℓ≥3 it is NP-hard to find the minimum number of arcs to deorient in a digraph D in order to obtain an ℓ-strong digraph D′.

KW - Arc-connectivity

KW - Arc-reversal

KW - Deorientation

KW - Orientation

KW - Vertex-connectivity

U2 - 10.1016/j.tcs.2023.114097

DO - 10.1016/j.tcs.2023.114097

M3 - Journal article

AN - SCOPUS:85167593097

SN - 0304-3975

VL - 973

JO - Theoretical Computer Science

JF - Theoretical Computer Science

M1 - 114097

ER -