Finding a minimum path cover of a distance-hereditary graph in polynomial time

A path cover of a graph G=(V,E) is a set of pairwise vertex-disjoint paths such that the disjoint union of the vertices of these paths equals the vertex set V of G. The path cover problem is, given a graph, to find a path cover having the minimum number of paths. The path cover problem contains the Hamiltonian path problem as a special case since finding a path cover, consisting of a single path, corresponds directly to the Hamiltonian path problem. A graph is a distance-hereditary graph if each pair of vertices is equidistant in every connected induced subgraph containing them. The complexity of the path cover problem on distance-hereditary graphs has remained unknown. In this paper, we propose the first polynomial-time algorithm, which runs in O(|V|⁹) time, to solve the path cover problem on distance-hereditary graphs.     

Rainbow paths

A k-rainbow path in a graph with colored edges is a path of length k where each edge has a different color. In this note, we settle the problem of obtaining a constructive k-coloring of the edges of K_n in which one may find, between any pair of vertices, a large number of internally disjoint k-rainbow paths. In fact, our construction obtains the largest possible number of paths. This problem was considered in a less general setting by Chartrand et al. (2007) [6].     

On the structure of k-connected graphs without Kk-minor

Suppose G is a k-connected graph that does not contain K_k as a minor. What does G look like? This question is motivated by Hadwiger’s conjecture (Vierteljahrsschr. Naturforsch. Ges. Zürich 88 (1943) 133) and a deep result of Robertson and Seymour (J. Combin. Theory Ser. B. 89 (2003) 43).It is easy to see that such a graph cannot contain a (k−1)-clique, but could contain a (k−2)-clique, as K_k−5+G′, where G′ is a 5-connected planar graph, shows. In this paper, however, we will prove that such a graph cannot contain three “nearly” disjoint (k−2)-cliques. This theorem generalizes some early results by Robertson et al. (Combinatorica 13 (1993) 279) and Kawarabayashi and Toft (Combinatorica (in press)).     

Induced Circuits in Planar Graphs

In McDiarmid, B. Reed, A. Schrijver, and B. Shepherd (Univ. of Waterloo Tech. Rep., 1990) a polynomial-time algorithm is given for the problem of finding a minimum cost circuit without chords (induced circuit) traversing two given vertices of a planar graph. The algorithm is based on the ellipsoid method. Here we give an O(n²) combinatorial algorithm to determine whether two nodes in a planar graph lie on an induced circuit. We also give a min-max relation for the problem of finding a maximum number of paths connecting two given vertices in a planar graph so that each pair of these paths forms an induced circuit.     

On the complexity of recognizing directed path families

A Directed Path Family is a family of subsets of some finite ground set whose members can be realized as arc sets of simple directed paths in some directed graph. In this paper we show that recognizing whether a given family is a Directed Path family is an NP-Complete problem, even when all members in the family have at most two elements. If instead of a family of subsets, we are given a collection of words from some finite alphabet, then deciding whether there exists a directed graph G such that each word in the language is the set of arcs of some path in G, is a polynomial-time solvable problem.     

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.     

Some complexity problems on single input double output controllers

We investigate the time complexity of constructing single input double output state feedback controller structures, given the directed structure graph G of a system. Such a controller structure defines a restricted type of P₃-partition of the graph G. A necessary condition (∗) is described and some classes of graphs are identified where the search problem of finding a feasible P₃-partition is polynomially solvable and, in addition, (∗) is not only necessary but also sufficient for the existence of a P₃-partition. It is also proved that the decision problem on two particular graph classes — defined in terms of forbidden subgraphs — remains NP-complete, but is polynomially solvable on the intersection of those two classes. The polynomial-time solvability of some further related problems is shown, too.     

On the approximability of the minimum strictly fundamental cycle basis problem

We consider the problem of finding a strictly fundamental cycle basis of minimum weight in the cycle space associated with an undirected connected graph G, where a nonnegative weight is assigned to each edge of G and the total weight of a basis is defined as the sum of the weights of all the cycles in the basis. Several heuristics have been proposed to tackle this NP-hard problem, which has some interesting applications. In this paper we show that this problem is APX-hard, even when restricted to unweighted graphs, and hence does not admit a polynomial-time approximation scheme, unless P=NP. Using a recent result on the approximability of lower-stretch spanning trees (Elkin et al. (2005) [7]), we obtain that the problem is approximable within O(log²nloglogn) for arbitrary graphs. We obtain tighter approximability bounds for dense graphs. In particular, the problem restricted to complete graphs admits a polynomial-time approximation scheme.     

Independence equivalence classes of paths

The independence equivalence class of a graph G is the set of graphs that have the same independence polynomial as G. A graph whose independence equivalence class contains only itself, up to isomorphism, is independence unique. Beaton, Brown and Cameron [2] showed that paths with an odd number of vertices are independence unique and raised the problem of finding the independence equivalence class of paths with an even number of vertices. The problem is completely solved in this paper.     

The k‐piece packing problem

A k‐piece of a graph G is a connected subgraph of G all of whose nodes have degree at most k and at least one node has degree equal to k. We consider the problem of covering the maximum number of nodes of a graph by node disjoint k‐pieces. When k = 1 this is the maximum matching problem, and when k = 2 this is the problem, recently studied by Kaneko [ 19 [, of covering the maximum number of nodes by disjoint paths of length greater than 1. We present a polynomial time algorithm for the problem as well as a Tutte‐type existence theorem and a Berge‐type min‐max formula. We also solve the problem in the more general situation where the “pieces” are defined in terms of lower and upper bounds on the degrees. © 2006 Wiley Periodicals, Inc. J Graph Theory     

On a relation between the domination number and a strongly connected bidirection of an undirected graph

As a generalization of directed and undirected graphs, Edmonds and Johnson [J. Edmonds, E.L. Johnson, Matching: A well-solved class of linear programs, in: R. Guy, H. Hanani, N. Sauer, J. Schönheim (Eds.), Combinatorial Structures and their Applications, Gordon and Breach, New York, 1970, pp. 88-92] introduced bidirected graphs. A bidirected graph is a graph each arc of which has either two positive end-vertices (tails), two negative end-vertices (heads), or one positive end-vertex (tail) and one negative end-vertex (head). We extend the notion of directed paths, distance, diameter and strong connectivity from directed to bidirected graphs and characterize those undirected graphs that allow a strongly connected bidirection. Considering the problem of finding the minimum diameter of all strongly connected bidirections of a given undirected graph, we generalize a result of Fomin et al. [F.V. Fomin, M. Matamala, E. Prisner, I. Rapaport, Bilateral orientations in graphs: Domination and AT-free classes, in: Proceedings of the Brazilian Symposium on Graphs, Algorithms and Combinatorics, GRACO 2001, in: Electronics Notes in Discrete Mathematics, vol. 7, Elsevier Science Publishers, 2001] about directed graphs and obtain an upper bound for the minimum diameter which depends on the minimum size of a dominating set and the number of bridges in the undirected graph.     

A Note on Directed Genera of Some Tournaments

An embedding of a digraph in an orientable surface is an embedding as the underlying graph and arcs in each region force a directed cycle. The directed genus is the minimum genus of surfaces in which the digraph can be directed embedded. Bonnington, Conder, Morton and McKenna [J. Combin. Theory Ser. B, 85(2002) 1-20] gave the problem that which tournaments on n vertices have the directed genus ?(n?3)(n?4)/12 ?, the genus of K_n. In this paper, we use the current graph method to show that there exists a tournament, which has the directed genus ?(n?3)(n?4)/12 ?, on n vertices if and only if n ≡ 3 or 7 (mod 12).     

A note on k‐shortest paths problem

It is well‐known that in a directed graph, if deleting any edge will not affect the shortest distance between two specific vertices s and t, then there are two edge‐disjoint paths from s to t and both of them are shortest paths. In this article, we generalize this to shortest k edge‐disjoint s‐t paths for any positive integer k. © 2010 Wiley Periodicals, Inc. J Graph Theory 67: 34‐37, 2011     

Density of the circular chromatic numbers of series‐parallel graphs

In this paper we show that every simple cubic graph on n vertices has a set of at least ? n/4 ? disjoint 2‐edge paths and that this bound is sharp. Our proof provides a polynomial time algorithm for finding such a set in a simple cubic graph. © 2003 Wiley Periodicals, Inc. J Graph Theory 45: 57–79, 2003     

Finding minimum clique capacity

Let C be a clique of a graph G. The capacity of C is defined to be (|V (G)\C|+|D|)/2, where D is the set of vertices in V (G)\C that have both a neighbour and a non-neighbour in C. We give a polynomial-time algorithm to find the minimum clique capacity in a graph G. This problem arose in the study [1] of packing vertex-disjoint induced three-vertex paths in a graph with no stable set of size three, which in turn was motivated by Hadwiger’s conjecture.     

A Bijection Between Partially Directed Paths in the SymmetricWedge and Matchings

We give a bijection between partially directed paths in the symmetric wedge y =  ±x and matchings, which sends north steps to nestings. This gives a bijective proof of a result of Janse van Rensburg, Prellberg, and Rechnitzer that was first discovered through the corresponding generating functions: The number of partially directed paths starting at the origin confined to the symmetric wedge y = ±x with k north steps is equal to the number of matchings on [2n] with k nestings.     

Coloring all directed paths in a symmetric tree,with an application to optical networks*

Let T be a symmetric directed tree, i.e., an undirected tree with each edge viewed as two opposite arcs. We prove that the minimum number of colors needed to color the set of all directed paths in T, so that two paths of the same color never use the same directed arc of T, is equal to the maximum number of different paths that contain the same arc of T. The proof implies a polynomial time algorithm for actually coloring the paths with the minimum number of colors. When only a subset of the directed paths is to be colored, the problem is known to be NP‐complete; we describe certain instances of the problem which can be efficiently solved. These results are applied to WDM (wavelength‐division multiplexing) routing in all‐optical networks. In particular, we solve the all‐to‐all gossiping problem in optical networks. © 2001 John Wiley & Sons, Inc. J Graph Theory 38: 183–196, 2001     

Minimum-weight cycle covers and their approximability

A cycle cover of a graph is a set of cycles such that every vertex is part of exactly one cycle. An L-cycle cover is a cycle cover in which the length of every cycle is in the set L⊆N.We investigate how well L-cycle covers of minimum weight can be approximated. For undirected graphs, we devise non-constructive polynomial-time approximation algorithms that achieve constant approximation ratios for all sets L. On the other hand, we prove that the problem cannot be approximated with a factor of 2−ε for certain sets L.For directed graphs, we devise non-constructive polynomial-time approximation algorithms that achieve approximation ratios of O(n), where n is the number of vertices. This is asymptotically optimal: We show that the problem cannot be approximated with a factor of o(n) for certain sets L.To contrast the results for cycle covers of minimum weight, we show that the problem of computing L-cycle covers of maximum weight can, at least in principle, be approximated arbitrarily well.