Multiflow Feasibility: An Annotated Tableau
We provide a tableau of 189 entries and some annotations presenting the computational complexity of integer multiflow feasibility problems; 21 entries remain open. The tableau is followed by an introduction to the field, providing more problems, reproving
- PDF / 323,307 Bytes
- 23 Pages / 439.37 x 666.142 pts Page_size
- 12 Downloads / 210 Views
Summary. We provide a tableau of 189 entries and some annotations presenting the computational complexity of integer multiflow feasibility problems; 21 entries remain open. The tableau is followed by an introduction to the field, providing more problems, reproving some results with new insights, simple proofs, or slight sharpenings motivated by the tableau, paying particular attention to planar (di)graphs with terminals on the boundary. Last, the key-theorems and key-problems of the tableau are listed.
12.1 Introduction Finding a set of (vertex- or edge-) disjoint paths in (directed or undirected) graphs between given pairs of terminals is one of the most ancestral and most studied themes of graph theory, with important applications such as routing problems of VLSI design (Korte et al. 1990). The scope of the methods and objectives is large and spread in time: Menger’s theorems or more generally network flows are among the first consistent results of combinatorial optimization (Schrijver 2003), whereas finding edge- or vertex-disjoint paths between a given (fixed) number of terminal pairs in polynomial time is a deep pure graph theory result (Robertson and Seymour 1995). A multiflow is the packing of one of the simplest objects in graphs: paths. At the same time it is an integer point in a naturally defined polyhedral cone. The field has been developed in parallel with the tools of optimization, polyhedral combinatorics and graph theory. Some branches were and are still the subject of extensive studies both by the inner stimulus of the theory and the request of the applications. In honor of Bernhard Korte’s 70-th birthday and in memory of the determining impact of the Institut für Diskrete Mathematik, Ökonometrie und Operations Research and its successors on research in the field of Combinatorial Optimization, and in particular on results that have been achieved in the subject of routing, VLSI design, or simply, disjoint paths problems. The second author learnt the subject, proved and wrote down his first results in the subject during his stays in Bonn, had the opportunity to work with students having an excellent training by Professor Korte, and acknowledges gratitude to him for his multiple, generous contribution. Supported by the Marie Curie Training Network “ADONET” of the European community.
262
G. Naves and A. Seb˝o Table 12.1.
|E(H )| r
G
arb
gen
fix
2
arb
plan
fix
2
arb
G+H fix plan
2 1 2 3 4 5 6 7 8 9 10 11 12
directed directed acyclic undirected arc-disjoint vertex- arc-disjoint vertex- edge-disjoint vertexgen Euler disjoint gen Euler disjoint gen Euler disjoint
bin un bin un fix bin un fix 2
NPC NPC NPC NPC NPC NPC NPC NPC NPC2
NPC NPC NPC NPC NPC NPC NPC NPC NPC NPC ???3 P P10 NPC 1 P NPC2 NPC P P P P
NPC NPC NPC NPC 2 NPC19 P P P P P P P
NPC NPC NPC NPC P NPC NPC1 P P
NPC NPC4 NPC NPC 12 NPC P P P13 P P P P
bin un bin un fix bin un fix 2
NPC NPC NPC NPC ??? NPC NPC9 ??? ???
NPC NPC NPC ??? 14 ??? P ??? P P P P P
NPC NPC19 NPC NPC16 P NPC NPC11 P P
NPC NPC NPC20 ??? P ??? P P
Data Loading...
