Arc-disjoint spanning sub(di)graphs in digraphs

Research output: Contribution to journalArticlepeer-review

18 Citations (Scopus)

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 languageEnglish
Pages (from-to)48-54
Number of pages7
JournalTheoretical Computer Science
Volume438
DOIs
Publication statusPublished - 22 Jun 2012
Externally publishedYes

Keywords

  • Arc-disjoint subdigraphs
  • Branchings
  • NP-completeness
  • Paths and cycles
  • Spanning trees

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Arc-disjoint spanning sub(di)graphs in digraphs'. Together they form a unique fingerprint.

Cite this