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

DOI10.1016/J.TCS.2023.114097MaRDI QIDQ6093584zbMATH OpenOpenAlexFDO

Authors Jørgen Bang-Jensen, Florian Hoersch, Matthias Kriesell

Publication date 7 September 2023

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2303.03296

zbMATH Keywords

orientationvertex-connectivityarc-connectivityarc-reversaldeorientation

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Connectivity (05C40)

Abstract: 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 Gevigny shows that for every $kgeq3$ 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^{\prime }=(V,A^{\prime })$. 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 $ellgeq3$ it is NP-hard to find the minimum number of arcs to deorient in a digraph $D$ in order to obtain an $ell$-strong digraph $D^{\prime }$.

Recommendations

• The complexity of 2-vertex-connected orientation in mixed graphs
• Making a tournament \(k\)-arc-strong by reversing or deorienting arcs.
• Connectivity of orientations of 3-edge-connected graphs
• Orienting graphs to optimize reachability

Cites work

• scientific article; zbMATH DE number 3685495 (Why is no real title available?)
• scientific article; zbMATH DE number 3580570 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 863470 (Why is no real title available?)
• A Minimax Theorem for Directed Graphs
• A Strongly Polynomial Algorithm for Minimum Cost Submodular Flow Problems
• A Theorem on Graphs, with an Application to a Problem of Traffic Control
• Augmenting Graphs to Meet Edge-Connectivity Requirements
• Bridging the gap between tree and connectivity augmentation: unified and stronger approaches
• Checking the admissibility of odd-vertex pairings is hard
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Combinatorial optimization. Theory and algorithms
• Computing Edge-Connectivity in Multigraphs and Capacitated Graphs
• Digraphs
• Making a tournament \(k\)-arc-strong by reversing or deorienting arcs.
• Minimal edge-coverings of pairs of sets
• On Frank's conjecture on \(k\)-connected orientations
• On Orientations, Connectivity and Odd-Vertex-Pairings in Finite Graphs
• On the orientation of graphs and hypergraphs
• Primal-dual approach for directed vertex connectivity augmentation and generalizations
• Simultaneous well-balanced orientations of graphs
• Some APX-completeness results for cubic graphs
• Strongly 2-connected orientations of graphs

This page was built for publication: Complexity of (arc)-connectivity problems involving arc-reversals or deorientations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6093584)