Edge-disjoint in- and out-branchings in tournaments and related path problems (Q1112061)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Edge-disjoint in- and out-branchings in tournaments and related path problems |
scientific article |
Statements
Edge-disjoint in- and out-branchings in tournaments and related path problems (English)
0 references
1991
0 references
We show that the following problems, are all polynomially solvable for tournaments: (1) Given a tournament T and \(u,v\in V(T)\), when do there exist edge- disjoint branchings \(F^+_ u\), \(F^-_ u\), such that \(F^+_ u\) is an out-branching rooted at u and \(F^-_ v\) is an in-branching rooted at v? An out-branching rooted at u is a spanning tree which is directed in such a way that each \(x\neq v\) has exactly one edge comming in. An in- branching is defined analogously. (2) Given a strong tournament T and distinct vertices \(x_ 1\), \(x_ 2\), \(y_ 1\), \(y_ 2\) of V(T), when do there exist edge-disjoint paths \(P_ 1\), \(P_ 2\) connecting \(x_ 1\) to \(y_ 1\) and \(x_ 2\) to \(y_ 2?\) (3) Given a strong tournament T and distinct vertices a, b, c of V(T), when do there exist edge disjoint paths P, Q, such that P connects a to b and Q connects b to c? It is well-known that (2) and (3) are NP-complete for general digraphs and we give a proof by C. Thomassen that (1) is also NP-complete for general digraphs. Perhaps a little surprisingly it turns out that problems (1) and (2) are far from trivial, even in the case of tournaments.
0 references
branchings
0 references
tournament
0 references
edge-disjoint paths
0 references
NP-completeness
0 references
polynomial algorithms
0 references
semicomplete digraphs
0 references