Abstract
We prove that a number of natural problems concerning the existence of arc-disjoint directed and "undirected" (spanning) subdigraphs in a digraph are NP-complete. Among these are the following of which the first settles an open problem due to Thomassé (see e.g. Bang-Jensen and Gutin (2009) [1, Problem 9.9.7] and Bang-Jensen and Kriesell (2009) [5,4]) and the second settles an open problem posed in Bang-Jensen and Kriesell (2009) [5]. Given a directed graph D and a vertex s of D; does D contain an out-branching Bs+ rooted at s such that the digraph remains connected (in the underlying sense) after removing all arcs of Bs+?Given a strongly connected directed graph D; does D contain a spanning strong subdigraph D′ such that the digraph remains connected (in the underlying sense) after removing all arcs of D′?
| Original language | English |
|---|---|
| Pages (from-to) | 48-54 |
| Number of pages | 7 |
| Journal | Theoretical Computer Science |
| Volume | 438 |
| DOIs | |
| Publication status | Published - 22 Jun 2012 |
| Externally published | Yes |
Keywords
- Arc-disjoint subdigraphs
- Branchings
- NP-completeness
- Paths and cycles
- Spanning trees
ASJC Scopus subject areas
- Theoretical Computer Science
- General Computer Science