Edge-disjoint in- and out-branchings in tournaments and related path problems.

*(English)*Zbl 0659.05052We 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.

(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.

Reviewer: J.Bang-Jensen

##### Keywords:

branchings; tournament; edge-disjoint paths; NP-completeness; polynomial algorithms; semicomplete digraphs
PDF
BibTeX
XML
Cite

\textit{J. Bang-Jensen}, J. Comb. Theory, Ser. B 51, No. 1, 1--23 (1991; Zbl 0659.05052)

Full Text:
DOI

##### References:

[1] | Bang-Jensen, J, A note on a special case of the 2-path problem for semicomplete digraphs, () · Zbl 0841.05053 |

[2] | Bang-Jensen, J, On the 2-linkage problem for semicomplete digraphs, Ann. discrete math., 41, 23-38, (1989) · Zbl 0664.05034 |

[3] | \scJ. Bang-Jensen and C. Thomassen, A polynomial algorithm for the 2-path problem for semicomplete digraphs, submitted for publication. · Zbl 0759.05041 |

[4] | Edmonds, J, Edge-disjoint branchings, (), 91-96 |

[5] | Edmonds, J, Paths, trees and flowers, Canad. J. math., 17, 449-467, (1965) · Zbl 0132.20903 |

[6] | Fortune, S; Hopcroft, J; Wyllie, J, The directed subgraph homeomorphism problem, Theoret. cimput. sci., 10, 111-121, (1980) · Zbl 0419.05028 |

[7] | Lovász, L, On two minimax theorems in graphs, J. combin. theory ser. B, 21, 96-103, (1976) · Zbl 0337.05115 |

[8] | Chung-fan, Ma; Mao-cheng, Cai, The maximum number of arc-disjoint arborescences in a tournament, J. graph theory, 6, 295-302, (1982) · Zbl 0458.05037 |

[9] | \scC. Thomassen, Private communication. |

[10] | Thomassen, C, Configurations in graphs of large minimum degree, connectivity or chromatic number, (), 402-412 |

[11] | Thomassen, C, Hamiltonian-connected tournaments, J. combin. theory ser. B, 28, 142-163, (1980) · Zbl 0435.05026 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.