Name
Abstract | ||
|---|---|---|
We consider the problem of deciding whether a given network with integer capacities has two feasible flows x and y with prescribed balance vectors such that the arcs that carry flow in x are arc-disjoint from the arcs that carry flow in y. This generalizes a number of well-studied problems such as the existence of arc-disjoint out-branchings B"s^+, B"t^+ where the roots s, t may be the same vertex, existence of arc-disjoint spanning subdigraphs D"1, D"2 with prescribed degree sequences in a digraph (e.g. arc-disjoint cycle factors), the weak-2-linkage problem, the number partitioning problem, etc. Hence the problem is NP-complete in general. We show that the problem remains hard even for very restricted cases such as two arc-disjoint (s,t)-flows each of value 2 in a network with capacities 1 and 2 on the arcs. On the positive side, we prove that the above problem is polynomially solvable if the network is acyclic and the arc capacities as well as the desired flow values are bounded. Our algorithm for this case generalizes the algorithm (by Perl and Shiloach [14] for k=2 and Fortune, Hopcroft and Wyllie [11] for k=3) for the k-linkage problem in acyclic digraphs. Besides, the problem is polynomial in general digraphs if all capacities are 1 and the two flows have the same balance for all vertices in N, but remains NP-complete if the network contains at least one arc with capacity 2 (and the others have capacity 1). Finally, we also show that the following properties are NP-complete to decide on digraphs: the existence of a spanning connected Eulerian subdigraph, the existence of a cycle factor in which all cycles have even length and finally the existence of a cycle factor in which all cycles have odd length. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1016/j.tcs.2014.01.011 | Theor. Comput. Sci. |
Keywords | DocType | Volume |
arc-disjoint cycle factor,flow value,weak-2-linkage problem,arc capacity,cycle factor,disjoint flow,acyclic digraph,feasible flow,arc-disjoint out-branchings B,k-linkage problem,well-studied problem | Journal | 526, |
ISSN | Citations | PageRank |
0304-3975 | 4 | 0.53 |
References | Authors | |
5 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jørgen Bang-Jensen | 1 | 573 | 68.96 |
| Stéphane Bessy | 2 | 117 | 19.68 |