TY - JOUR

T1 - Tournament immersion and cutwidth

AU - Chudnovsky, Maria

AU - Fradkin, Alexandra

AU - Seymour, Paul

N1 - Funding Information:
E-mail address: [email protected] (P. Seymour). 1 Supported by NSF grants DMS-0758364 and DMS-1001091. 2 Supported by ONR grant N00014-04-1-0062 and NSF grant DMS-0901075.

PY - 2012/1

Y1 - 2012/1

N2 - A (loopless) digraph H is strongly immersed in a digraph G if the vertices of H are mapped to distinct vertices of G, and the edges of H are mapped to directed paths joining the corresponding pairs of vertices of G, in such a way that the paths used are pairwise edge-disjoint, and do not pass through vertices of G that are images of vertices of H. A digraph has cutwidth at most k if its vertices can be ordered {v1,...,vn} in such a way that for each j, there are at most k edges uv such that u∈{v1,...,vj-1} and v∈{vj,...,vn}.We prove that for every set S of tournaments, the following are equivalent: •there is a digraph H such that H cannot be strongly immersed in any member of S,•there exists k such that every member of S has cutwidth at most k,•there exists k such that every vertex of every member of S belongs to at most k edge-disjoint directed cycles. This is a key lemma towards two results that will be presented in later papers: first, that strong immersion is a well-quasi-order for tournaments, and second, that there is a polynomial time algorithm for the k edge-disjoint directed paths problem (for fixed k) in a tournament.

AB - A (loopless) digraph H is strongly immersed in a digraph G if the vertices of H are mapped to distinct vertices of G, and the edges of H are mapped to directed paths joining the corresponding pairs of vertices of G, in such a way that the paths used are pairwise edge-disjoint, and do not pass through vertices of G that are images of vertices of H. A digraph has cutwidth at most k if its vertices can be ordered {v1,...,vn} in such a way that for each j, there are at most k edges uv such that u∈{v1,...,vj-1} and v∈{vj,...,vn}.We prove that for every set S of tournaments, the following are equivalent: •there is a digraph H such that H cannot be strongly immersed in any member of S,•there exists k such that every member of S has cutwidth at most k,•there exists k such that every vertex of every member of S belongs to at most k edge-disjoint directed cycles. This is a key lemma towards two results that will be presented in later papers: first, that strong immersion is a well-quasi-order for tournaments, and second, that there is a polynomial time algorithm for the k edge-disjoint directed paths problem (for fixed k) in a tournament.

KW - Cutwidth

KW - Immersion

KW - Tournament

UR - http://www.scopus.com/inward/record.url?scp=81455141527&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=81455141527&partnerID=8YFLogxK

U2 - 10.1016/j.jctb.2011.05.001

DO - 10.1016/j.jctb.2011.05.001

M3 - Article

AN - SCOPUS:81455141527

SN - 0095-8956

VL - 102

SP - 93

EP - 101

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

IS - 1

ER -