کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
434820 | 689809 | 2012 | 7 صفحه PDF | دانلود رایگان |

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 rooted at s such that the digraph remains connected (in the underlying sense) after removing all arcs of ?
• 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′?
Journal: Theoretical Computer Science - Volume 438, 22 June 2012, Pages 48-54