Arc-disjoint paths and trees in 2-regular digraphs

DOI10.1016/J.DAM.2013.04.018zbMATH Open1285.05075arXiv1203.4705OpenAlexW2044338318MaRDI QIDQ2444565FDOQ2444565

Authors: Sven Simonsen, Jørgen Bang-Jensen 

Publication date: 10 April 2014

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Abstract: An out-(in-)branching B_s^+ (B_s^-) rooted at s in a digraph D is a connected spanning subdigraph of D in which every vertex x != s has precisely one arc entering (leaving) it and s has no arcs entering (leaving) it. We settle the complexity of the following two problems: 1) Given a 2-regular digraph $D$, decide if it contains two arc-disjoint branchings B^+_u, B^-_v. 2) Given a 2-regular digraph D, decide if it contains an out-branching B^+_u such that D remains connected after removing the arcs of B^+_u. Both problems are NP-complete for general digraphs. We prove that the first problem remains NP-complete for 2-regular digraphs, whereas the second problem turns out to be polynomial when we do not prescribe the root in advance. We also prove that, for 2-regular digraphs, the latter problem is in fact equivalent to deciding if $D$ contains two arc-disjoint out-branchings. We generalize this result to k-regular digraphs where we want to find a number of pairwise arc-disjoint spanning trees and out-branchings such that there are k in total, again without prescribing any roots.

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

Recommendations

• Arc-disjoint spanning sub(di)graphs in digraphs
• Edge-disjoint in- and out-branchings in tournaments and related path problems
• Arc-disjoint in- and out-branchings with the same root in locally semicomplete digraphs
• The complexity of finding arc-disjoint branching flows
• Arc‐disjoint in‐ and out‐branchings in digraphs of independence number at most 2

zbMATH Keywords

polynomial timespanning treeout-branchingmixed problemconnected spanning subgraphin-branching2-regular digraph

Mathematics Subject Classification ID

Trees (05C05) Directed graphs (digraphs), tournaments (05C20)

Cites Work

• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• On the Problem of Decomposing a Graph into n Connected Factors
• Digraphs
• Title not available (Why is that?)
• Edge-disjoint in- and out-branchings in tournaments and related path problems
• Arc-disjoint spanning sub(di)graphs in digraphs
• Title not available (Why is that?)
• The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two
• Disjoint directed and undirected paths and cycles in digraphs
• On the problem of finding disjoint cycles and dicycles in a digraph
• Small degree out‐branchings
• Title not available (Why is that?)
• A linear-time algorithm to find a pair of arc-disjoint spanning in-arborescence and out-arborescence in a directed acyclic graph
• Arc-disjoint in- and out-branchings with the same root in locally semicomplete digraphs

Cited In (13)

• Arc‐disjoint in‐ and out‐branchings in digraphs of independence number at most 2
• Arc-disjoint paths in decomposable digraphs
• Arc-disjoint in- and out-branchings with the same root in locally semicomplete digraphs
• \(k\)-distinct in- and out-branchings in digraphs
• Non-separating spanning trees and out-branchings in digraphs of independence number 2
• The complexity of finding arc-disjoint branching flows
• Good orientations of unions of edge‐disjoint spanning trees
• Title not available (Why is that?)
• Parameterized algorithms for non-separating trees and branchings in digraphs
• Arc-disjoint spanning sub(di)graphs in digraphs
• Edge-disjoint in- and out-branchings in tournaments and related path problems
• Balanced branchings in digraphs
• Complexity of some arc-partition problems for digraphs

This page was built for publication: Arc-disjoint paths and trees in 2-regular digraphs

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