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

    Identifiers