Length-bounded disjoint paths in planar graphs

The following problem is considered: given: an undirected planar graph G=(V,E) embedded in , distinct pairs of vertices {r₁,s₁},…,{r_k,s_k} of G adjacent to the unbounded face, positive integers b₁,…,b_k and a function ; find: pairwise vertex-disjoint paths P₁,…,P_k such that for each i=1,…,k, P_i is a r_i−s_i-path and the sum of the l-length of all edges in P_i is at most b_i. It is shown that the problem is NP-hard in the strong sense. A pseudo-polynomial-time algorithm is given for the case of k=2.     

On shortest disjoint paths in planar graphs

For a graph G and a collection of vertex pairs {(s₁,t₁),…,(s_k,t_k)}, the k disjoint paths problem is to find k vertex-disjoint paths P₁,…,P_k, where P_i is a path from s_i to t_i for each i=1,…,k. In the corresponding optimization problem, the shortest disjoint paths problem, the vertex-disjoint paths P_i have to be chosen such that a given objective function is minimized. We consider two different objectives, namely minimizing the total path length (minimum sum, or short: Min-Sum), and minimizing the length of the longest path (Min-Max), for k=2,3.Min-Sum: We extend recent results by Colin de Verdière and Schrijver to prove that, for a planar graph and for terminals adjacent to at most two faces, the Min-Sum 2 Disjoint Paths Problem can be solved in polynomial time. We also prove that, for six terminals adjacent to one face in any order, the Min-Sum 3 Disjoint Paths Problem can be solved in polynomial time.Min-Max: The Min-Max 2 Disjoint Paths Problem is known to be NP-hard for general graphs. We present an algorithm that solves the problem for graphs with tree-width 2 in polynomial time. We thus close the gap between easy and hard instances, since the problem is weakly NP-hard for graphs with tree-width 3.     

Induced disjoint paths problem in a planar digraph

As an extension of the disjoint paths problem, we introduce a new problem which we call the induced disjoint paths problem. In this problem we are given a graph G and a collection of vertex pairs {(s₁,t₁),…,(s_k,t_k)}. The objective is to find k paths P₁,…,P_k such that P_i is a path from s_i to t_i and P_i and P_j have neither common vertices nor adjacent vertices for any distinct i,j.The induced disjoint paths problem has several variants depending on whether k is a fixed constant or a part of the input, whether the graph is directed or undirected, and whether the graph is planar or not. We investigate the computational complexity of several variants of the induced disjoint paths problem. We show that the induced disjoint paths problem is (i) solvable in polynomial time when k is fixed and G is a directed (or undirected) planar graph, (ii) NP-hard when k=2 and G is an acyclic directed graph, (iii) NP-hard when k=2 and G is an undirected general graph.As an application of our first result, we show that we can find in polynomial time certain structures called a “hole” and a “theta” in a planar graph.     

Disjoint paths in sparse graphs

We generalize all the results obtained for maximum integer multiflow and minimum multicut problems in trees by Garg, Vazirani and Yannakakis [N. Garg, V.V. Vazirani, M. Yannakakis, Primal-dual approximation algorithms for integral flow and multicut in trees, Algorithmica 18 (1997) 3–20] to graphs with a fixed cyclomatic number, while this cannot be achieved for other classical generalizations of trees. We also introduce thek-edge-outerplanar graphs, a class of planar graphs with arbitrary (but bounded) tree-width that generalizes the cacti, and show that the integrality gap of the maximum edge-disjoint paths problem is bounded in these graphs.     

Disjoint paths in symmetric digraphs

Given a number of requests ?, we propose a polynomial-time algorithm for finding ? disjoint paths in a symmetric directed graph. It is known that the problem of finding ?≥2 disjoint paths in a directed graph is NP-hard [S. Fortune, J. Hopcroft, J. Wyllie, The directed subgraph homeomorphism problem, Journal of Theoretical Computer Science 10 (2) (1980) 111-121]. However, by studying minimal solutions it turns out that only a finite number of configurations are possible in a symmetric digraph. We use Robertson and Seymour’s polynomial-time algorithm [N. Robertson, P. D. Seymour, Graph minors xiii. The disjoint paths problem, Journal of Combinatorial Theory B (63) (1995) 65-110] to check the feasibility of each configuration.     

The undirected two disjoint shortest paths problem

The $k$ disjoint shortest paths problem ($k$-DSPP) on a graph with $k$ source–sink pairs $(s_i,t_i)$ asks if there exist $k$ pairwise edge- or vertex-disjoint shortest $s_i$–$t_i$-paths. It is known to be NP-complete if $k$ is part of the input. Restricting to $2$-DSPP with strictly positive lengths, it becomes solvable in polynomial time. We extend this result by allowing zero edge lengths and give a polynomial-time algorithm based on dynamic programming for $2$-DSPP on undirected graphs with non-negative edge lengths.     

A theorem on paths in planar graphs

We prove a theorem on paths with prescribed ends in a planar graph which extends Tutte's theorem on cycles in planar graphs [9] and implies the conjecture of Plummer [5] asserting that every 4-connected planar graph is Hamiltonian-connected.     

A theorem on paths in planar graphs

C. Thomassen extended Tutte's theorem on cycles in planar graphs in the paper “A Theorem on Paths in Planar Graphs”. This note corrects a flaw in his proof.     

Disjoint paths in tournaments

Given k   pairs of vertices (_si,_ti)$(s_i,t_i)$(1≤i≤k)$(1\le i\le k)$ of a digraph G, how can we test whether there exist k   vertex-disjoint directed paths from _si$s_i$ to _ti$t_i$ for 1≤i≤k$1\le i\le k$? This is NP-complete in general digraphs, even for k=2$k=2$ [2], but for k=2$k=2$ there is a polynomial-time algorithm when G is a tournament (or more generally, a semicomplete digraph), due to Bang-Jensen and Thomassen [1]. Here we prove that for all fixed k there is a polynomial-time algorithm to solve the problem when G is semicomplete.     

Multiflows and disjoint paths of minimum total cost

In this paper we discuss a number of recent and earlier results in the field of combinatorial optimization that concerns problems on minimum cost multiflows (multicommodity flows) and edge-disjoint paths. More precisely, we deal with an undirected networkN consisting of a supply graphG, a commodity graphH and nonnegative integer-valued functions of capacities and costs of edges ofG, and consider the problems of minimizing the total cost among (i) all maximum multiflows, and (ii) all maximuminteger multiflows. For problem (i), we discuss the denominators behavior in terms ofH. The main result is that ifH is complete (i.e. flows between any two terminals are allowed) then (i) has ahalf-integer optimal solution. Moreover, there are polynomial algorithms to find such a solution. For problem (ii), we give an explicit combinatorial minimax relation in case ofH complete. This generalizes a minimax relation, due to Mader and, independently, Lomonosov, for the maximum number of edge-disjoint paths whose ends belong to a prescribed subset of nodes of a graph. Also there exists a polynomial algorithm when the capacities are all-unit. The minimax relation for (ii) withH complete allows to describe the dominant for the set of (T, d)-joins (extending the notion ofT-join) and the dominant for the set of maximum multi-joins of a graph. Also other relevant results are reviewed and open questions are raised. © 1997 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.     

A note on monotone paths in labeled graphs

We characterize countable graphs with the property that every one-to-one labeling of edges by positive integers admits a monotone path.     

Packing paths in planar graphs

A generalization of P. Seymour's theorem on planar integral 2-commodity flows is given when the underlying graphG together with the demand graphH (a graph having edges that connect the corresponding terminal pairs) form a planar graph and the demand edges are on two faces ofG.     

Short containers in Cayley graphs

The star diameter of a graph measures the minimum distance from any source node to several other target nodes in the graph. For a class of Cayley graphs from abelian groups, a good upper bound for their star diameters is given in terms of the usual diameters and the orders of elements in the generating subsets. This bound is tight for several classes of graphs including hypercubes and directed n-dimensional tori. The technique used is the so-called disjoint ordering for a system of subsets, due to Gao, Novick and Qiu [S. Gao, B. Novick, K. Qiu, From Hall’s matching theorem to optimal routing on hypercubes, J. Comb. Theory B 74 (1998) 291-301].     

On paths in planar graphs

This paper generalizes a theorem of Thomassen on paths in planar graphs. As a corollary, it is shown that every 4-connected planar graph has a Hamilton path between any two specified vertices x, y and containing any specified edge other than xy. © 1997 John Wiley & Sons, Inc.     

Edge-disjoint paths in planar graphs

Given a planar graph G = (V, E), find k edge-disjoint paths in G connecting k pairs of terminals specified on the outer face of G. Generalizing earlier results of Okamura and Seymour (J. Combin. Theory Ser. B31 (1981), 75–81) and of the author (Combinatorica2, No. 4 (1982), 361–371), we solve this problem when each node of G not on the outer face has even degree. The solution involves a good characterization for the solvability and the proof gives rise to an algorithm of complexity O(|V|³log|V|). In particular, the integral multicommodity flow problem is proved to belong to the problem class P when the underlying graph is outerplanar.     

The extremal function for 3-linked graphs

A graph is k-linked if for every set of 2k distinct vertices {s₁,…,s_k,t₁,…,t_k} there exist disjoint paths P₁,…,P_k such that the endpoints of P_i are s_i and t_i. We prove every 6-connected graph on n vertices with 5n−14 edges is 3-linked. This is optimal, in that there exist 6-connected graphs on n vertices with 5n−15 edges that are not 3-linked for arbitrarily large values of n.     

Spanning paths in infinite planar graphs

Let G be a 4-connected infinite planar graph such that the deletion of any finite set of vertices of G results in at most one infinite component. We prove a conjecture of Nash-Williams that G has a 1-way infinite spanning path. © 1996 John Wiley & Sons, Inc.     

Hamiltonian paths in Cayley graphs

The classical question raised by Lovász asks whether every Cayley graph is Hamiltonian. We present a short survey of various results in that direction and make some additional observations. In particular, we prove that every finite group G has a generating set of size at most log₂|G|, such that the corresponding Cayley graph contains a Hamiltonian cycle. We also present an explicit construction of 3-regular Hamiltonian expanders.     

A note on edge-graceful spectra of the square of paths

For a simple path P_r on r vertices, the square of P_r is the graph on the same set of vertices of P_r, and where every pair of vertices of distance two or less in P_r is connected by an edge. Given a (p,q)-graph G with p vertices and q edges, and a nonnegative integer k, G is said to be k-edge-graceful if the edges can be labeled bijectively by k,k+1,…,k+q−1, so that the induced vertex sums are pairwise distinct, where the vertex sum at a vertex is the sum of the labels of all edges incident to such a vertex, modulo the number of vertices p. We call the set of all such k the edge-graceful spectrum of G, and denote it by egI(G). In this article, the edge-graceful spectrum for the square of paths is completely determined for odd r.