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.     

A Combinatorial Algorithm for the Minimum (2, r)-Metric Problem and Some Generalizations

be a graph with nonnegative integer capacities c(e) of the edges , and let μ be a metric that establishes distances on the pairs of elements of a subset . In the minimum 0-extension problem (*), one is asked for finding a (semi)metric m on V such that m coincides with μ within T, each is at zero distance from some , and the value is as small as possible. This is the classical minimum (undirected) cut problem when and , and the minimum (2, r)-metric problem when μ is the path metric of the complete bipartite graph . It is known that the latter problem can be solved in strongly polynomial time by use of the ellipsoid method. We develop a polynomial time algorithm for the minimum (2, r)-metric problem, using only ``purely combinatorial' means. The algorithm simultaneously solves a certain associated integer multiflow problem. We then apply this algorithm to solve (*) for a wider class of metrics μ, present other results and raise open questions. Received: June 11, 1998     

Algorithms for graph partitioning on the planted partition model

The NP‐hard graph bisection problem is to partition the nodes of an undirected graph into two equal‐sized groups so as to minimize the number of edges that cross the partition. The more general graph l‐partition problem is to partition the nodes of an undirected graph into l equal‐sized groups so as to minimize the total number of edges that cross between groups. We present a simple, linear‐time algorithm for the graph l‐partition problem and we analyze it on a random “planted l‐partition” model. In this model, the n nodes of a graph are partitioned into l groups, each of size n/l; two nodes in the same group are connected by an edge with some probability p, and two nodes in different groups are connected by an edge with some probability r<p. We show that if p−r≥n^−1/2+ϵ for some constant ϵ, then the algorithm finds the optimal partition with probability 1− exp(−n^Θ(ε)). © 2001 John Wiley & Sons, Inc. Random Struct. Alg., 18: 116–140, 2001     

A Lower Bound On The Integrality Gap For Minimum Multicut In Directed Networks

Given a directed edge-weighted graph and k source-sink pairs, the Minimum Directed Multicut Problem is to find an edge subset with minimal weight, that separates each source-sink pair. Determining the minimum multicut in directed or undirected graphs is NP-hard. The fractional version of the minimum multicut problem is dual to the maximum multicommodity flow problem. The integrality gap for an instance of this problem is the ratio of the minimum weight multicut to the minimum weight fractional multicut; trivially this gap is always at least 1 and it is easy to show that it is at most k. In the analogous problem for undirected graphs this upper bound was improved to O(log k).In this paper, for each k an explicit family of examples is presented each with k source-sink pairs for which the integrality gap can be made arbitrarily close to k. This shows that for directed graphs, the trivial upper bound of k can not be improved.* This work was supported in part by NSF grant CCR-9700239 and by DIMACS. This work was done while a postdoctoral fellow at DIMACS.     

On antimagic directed graphs

An antimagic labeling of an undirected graph G with n vertices and m edges is a bijection from the set of edges of G to the integers {1, …, m} such that all n vertex sums are pairwise distinct, where a vertex sum is the sum of labels of all edges incident with that vertex. A graph is called antimagic if it admits an antimagic labeling. In (N. Hartsfield and G. Ringel, Pearls in Graph Theory, Academic Press, Boston, 1990, pp. 108–109), Hartsfield and Ringel conjectured that every simple connected graph, other than K₂, is antimagic. Despite considerable effort in recent years, this conjecture is still open. In this article we study a natural variation; namely, we consider antimagic labelings of directed graphs. In particular, we prove that every directed graph whose underlying undirected graph is “dense” is antimagic, and that almost every undirected d‐regular graph admits an orientation which is antimagic. © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 219–232, 2010     

Complexity and exact algorithms for vertex multicut in interval and bounded treewidth graphs

Multicut is a fundamental network communication and connectivity problem. It is defined as: given an undirected graph and a collection of pairs of terminal vertices, find a minimum set of edges or vertices whose removal disconnects each pair. We mainly focus on the case of removing vertices, where we distinguish between allowing or disallowing the removal of terminal vertices. Complementing and refining previous results from the literature, we provide several NP-completeness and (fixed-parameter) tractability results for restricted classes of graphs such as trees, interval graphs, and graphs of bounded treewidth.     

On the complexity of the planar edge-disjoint paths problem with terminals on the outer boundary

It is shown that both the undirected and the directed edge-disjoint paths problem are NP-complete, if the supply graph is planar and all edges of the demand graph are incident with vertices lying on the outer boundary of the supply graph. In the directed case, the problem remains NP-complete, if in addition the supply graph is acyclic. The undirected case solves open problem no. 56 of A. Schrijver’s book Combinatorial Optimization.     

On some balanced, totally balanced and submodular delivery games

This paper studies a class of delivery problems associated with the Chinese postman problem and a corresponding class of delivery games. A delivery problem in this class is determined by a connected graph, a cost function defined on its edges and a special chosen vertex in that graph which will be referred to as the post office. It is assumed that the edges in the graph are owned by different individuals and the delivery game is concerned with the allocation of the traveling costs incurred by the server, who starts at the post office and is expected to traverse all edges in the graph before returning to the post office. A graph G is called Chinese postman-submodular, or, for short, CP-submodular (CP-totally balanced, CP-balanced, respectively) if for each delivery problem in which G is the underlying graph the associated delivery game is submodular (totally balanced, balanced, respectively). For undirected graphs we prove that CP-submodular graphs and CP-totally balanced graphs are weakly cyclic graphs and conversely. An undirected graph is shown to be CP-balanced if and only if it is a weakly Euler graph. For directed graphs, CP-submodular graphs can be characterized by directed weakly cyclic graphs. Further, it is proven that any strongly connected directed graph is CP-balanced. For mixed graphs it is shown that a graph is CP-submodular if and only if it is a mixed weakly cyclic graph. Finally, we note that undirected, directed and mixed weakly cyclic graphs can be recognized in linear time. Received May 20, 1997 / Revised version received August 18, 1998?Published online June 11, 1999     

Two-Connected Augmentation Problems in Planar Graphs

Given a weighted undirected graph G and a subgraph S of G, we consider the problem of adding a minimum-weight set of edges of G to S so that the resulting subgraph satisfies specified (edge or vertex) connectivity requirements between pairs of nodes of S. This has important applications in upgrading telecommunication networks to be invulnerable to link or node failures. We give a polynomial algorithm for this problem when S is connected, nodes are required to be at most 2-connected, and G is planar. Applications to network design and multicommodity cut problems are also discussed.     

The non-approximability of bicriteria network design problems

Let G be an undirected graph with two edge costs (c-cost and d-cost). We want to minimize the diameter of a spanning subgraph S (under d-cost) subject to the constraint that the total cost of the edges in S (with respect to c) does not exceed a given budget. We prove that this problem is non-approximable, even in some special cases. Similar results are proved if the stretch factor or the root stretch factor is considered instead of the diameter.     

Scale‐free graphs of increasing degree

We study a scale‐free random graph process in which the number of edges added at each step increases. This differs from the standard model in which a fixed number, m, of edges are added at each step. Let f(t) be the number of edges added at step t. In the standard scale‐free model, f(t) = m constant, whereas in this paper we consider f(t) = [t^c],c > 0. Such a graph process, in which the number of edges grows non‐linearly with the number of vertices is said to have accelerating growth. We analyze both an undirected and a directed process. The power law of the degree sequence of these processes exhibits widely differing behavior. For the undirected process, the terminal vertex of each edge is chosen by preferential attachment based on vertex degree. When f(t) = m constant, this is the standard scale‐free model, and the power law of the degree sequence is 3. When f(t) = [t^c],c < 1, the degree sequence of the process exhibits a power law with parameter x = (3 ? c)/(1 ? c). As c → 0, x → 3, which gives a value of x = 3, as in standard scale‐free model. Thus no more slowly growing monotone function f(t) alters the power law of this model away from x = 3. When c = 1, so that f(t) = t, the expected degree of all vertices is t, the vertex degree is concentrated, and the degree sequence does not have a power law. For the directed process, the terminal vertex is chosen proportional to in‐degree plus an additive constant, to allow the selection of vertices of in‐degree zero. For this process when f(t) = m is constant, the power law of the degree sequence is x = 2 + 1/m. When f(t) = [t^c], c > 0, the power law becomes x = 1 + 1/(1 + c), which naturally extends the power law to [1,2]. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 38, 396–421, 2011     

Fast parallel strong orientation of mixed graphs and related augmentation problems

The strong orientation problem is: Given an undirected graph, G, assign orientations to its edges so that the resulting directed graph is strongly connected. Robbins showed when such an orientation exists. A generalization of this problem is when the input graph is mixed (i.e., contains some directed and some undirected edges). Boesch and Tindell gave necessary and sufficient conditions for a strong orientation to exist in a mixed graph. In this paper we give an NC algorithm for constructing a strong orientation for a given mixed graph after determining if it exists. We also give an NC algorithm for adding a minimum set of arcs to a mixed graph to make it strongly orientable. We give simplified NC algorithms for the following special cases: find minimum augmentations to make a digraph strongly connected and to make an undirected graph bridge-connected. All the algorithms presented run within the time and processor bounds required for computing the transitive closure of a digraph.     

Minimum cost multiflows in undirected networks

LetN = (G, T, c, a) be a network, whereG is an undirected graph,T is a distinguished subset of its vertices (calledterminals), and each edgee ofG has nonnegative integer-valuedcapacity c(e) andcost a(e). Theminimum cost maximum multi(commodity)flow problem (*) studied in this paper is to find ac-admissible multiflowf inG such that: (i)f is allowed to contain partial flows connecting any pairs of terminals, (ii) the total value off is as large as possible, and (iii) the total cost off is as small as possible, subject to (ii). This generalizes, on one hand, the undirected version of the classical minimum cost maximum flow problem (when |T| = 2), and, on the other hand, the problem of finding a maximum fractional packing ofT-paths (whena 0). Lovász and Cherkassky independently proved that the latter has a half-integral optimal solution.A pseudo-polynomial algorithm for solving (*) has been developed earlier and, as its consequence, the theorem on the existence of a half-integral optimal solution for (*) was obtained. In the present paper we give a direct, shorter, proof of this theorem. Then we prove the existence of a half-integral optimal solution for the dual problem. Finally, we show that half-integral optimal primal and dual solutions can be designed by a combinatorial strongly polynomial algorithm, provided that some optimal dual solution is known (the latter can be found, in strongly polynomial time, by use of a version of the ellipsoid method).This work was partially supported by Chaire municipale, Mairie de Grenoble, France.     

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.     

Bounds and Heuristics for the Shortest Capacitated Paths Problem

Given a graph G, the Shortest Capacitated Paths Problem (SCPP) consists of determining a set of paths of least total length, linking given pairs of vertices in G, and satisfying capacity constraints on the arcs of G.We formulate the SCPP as a 0-1 linear program and study two Lagrangian relaxations for getting lower bounds on the optimal value. We then propose two heuristic methods. The first one is based on a greedy approach, while the second one is an adaptation of the tabu search meta-heuristic.     

Half-Transitive Graphs of Prime-Cube Order

We call an undirected graph X half-transitive if the automorphism group Aut X of X acts transitively on the vertex set and edge set but not on the set of ordered pairs of adjacent vertices of X. In this paper we determine all half-transitive graphs of order p ³ and degree 4, where p is an odd prime; namely, we prove that all such graphs are Cayley graphs on the non-Abelian group of order p ³ and exponent p ², and up to isomorphism there are exactly (p – 1)/2 such graphs. As a byproduct, this proves the uniqueness of Holt's half-transitive graph with 27 vertices.     

A parallel algorithm for the maximal path problem

In this paper we present anO (log⁵ n) time parallel algorithm for constructing a Maximal Path in an undirected graph. We also give anO (log^1/2+ε) time parallel algorithm for constructing a depth first search tree in an undirected graph. This work was supported in part by an IBM Faculty Development Award, an NSF Graduate Fellowship, and NSF grant DCR-8351757.     

Relations between the Local Chromatic Number and Its Directed Version

The local chromatic number is a coloring parameter defined as the minimum number of colors that should appear in the most colorful closed neighborhood of a vertex under any proper coloring of the graph. Its directed version is the same when we consider only outneighborhoods in a directed graph. For digraphs with all arcs being present in both directions the two values are obviously equal. Here, we consider oriented graphs. We show the existence of a graph where the directed local chromatic number of all oriented versions of the graph is strictly less than the local chromatic number of the underlying undirected graph. We show that for fractional versions the analogous problem has a different answer: there always exists an orientation for which the directed and undirected values coincide. We also determine the supremum of the possible ratios of these fractional parameters, which turns out to be e, the basis of the natural logarithm.     

Excluding a Simple Good Pair Approach to Directed Cuts

In 1972, Mader proved that every undirected graph has a good pair, that is, an ordered pair (u,v) of nodes such that the star of v is a minimum cut separating u and v. In 1992, Nagamochi and Ibaraki gave a simple procedure to find a good pair as the basis of an elegant and very efficient algorithm to find minimum cuts in graphs. This paper rules out the simple good pair approach for the problem of finding a minimum directed cut in a digraph and for the more general problem of minimizing submodular functions. In fact, we construct a digraph with no good pair. Note that if a graph has no good pair, then it may not possess a so-called cut-equivalent tree. Benczúr constructed a digraph with no cut-equivalent tree; our counterexample thus extends Benczúr's one. Received: March 12, 1999 Final version received: June 19, 2000