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

DOI10.1016/J.TCS.2023.114097arXiv2303.03296OpenAlexW4385336697MaRDI QIDQ6093584FDOQ6093584

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

Publication date: 7 September 2023

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

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 }$.

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

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

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)

Cites Work

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

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)