Edge-disjoint in- and out-branchings in tournaments and related path problems
type: Item
instance of: scholarly article
title: Edge-disjoint in- and out-branchings in tournaments and related path problems
zbMATH Open document ID: 0659.05052
DOI: 10.1016/0095-8956(91)90002-2
published in: Journal of Combinatorial Theory. Series B
publication date: 1991-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 4077258
zbMATH Keywords: branchings
zbMATH Keywords: tournament
zbMATH Keywords: edge-disjoint paths
zbMATH Keywords: NP-completeness
zbMATH Keywords: polynomial algorithms
zbMATH Keywords: semicomplete digraphs
author: Jørgen Bang-Jensen
reviewed by: Jørgen Bang-Jensen
MaRDI profile type: Publication
full work available at URL: 0095-8956(91)90002-2
OpenAlex ID: W2038926198
cites work: Q4873791
cites work: Q3815328
cites work: A Polynomial Algorithm for the 2-Path Problem for Semicomplete Digraphs
cites work: Paths, Trees, and Flowers
cites work: The directed subgraph homeomorphism problem
cites work: On two minimax theorems in graph
cites work: The maximum number of arc-disjoint arborescences in a tournament
cites work: Q3491608
cites work: Hamiltonian-connected tournaments
description: scientific article; zbMATH DE number 4077258