Tournament immersion and cutwidth |
| |
Authors: | Maria Chudnovsky Alexandra FradkinPaul Seymour |
| |
Institution: | a Columbia University, New York, NY 10027, United States b Princeton University, Princeton, NJ 08544, United States |
| |
Abstract: | 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. |
| |
Keywords: | Tournament Immersion Cutwidth |
本文献已被 ScienceDirect 等数据库收录! |
|