Solving some NP-complete problems using split decomposition

We show how to use the split decomposition to solve some NP-hard optimization problems on graphs. We give algorithms for clique problem and domination-type problems. Our main result is an algorithm to compute a coloration of a graph using its split decomposition. Finally we show that the clique-width of a graph is bounded if and only if the clique-width of each representative graph in its split decomposition is bounded.     

Dynamically maintaining split graphs

We present an algorithm that supports operations for modifying a split graph by adding edges or vertices and deleting edges, such that after each modification the graph is repaired to become a split graph in a minimal way. In particular, if the graph is not split after the modification, the algorithm computes a minimal, or if desired even a minimum, split completion or deletion of the modified graph. The motivation for such operations is similar to the motivation for fully dynamic algorithms for particular graph classes. In our case we allow all modifications to the graph and repair, rather than allowing only the modifications that keep the graph split. Fully dynamic algorithms of the latter kind are known for split graphs [L. Ibarra, Fully dynamic algorithms for chordal graphs and split graphs, Technical Report DCS-262-IR, University of Victoria, Canada, 2000].Our results can be used to design linear time algorithms for some recognition and completion problems, where the input is supplied in an on-line fashion.     

Distance-Hereditary Comparability Graphs

We study the class of the distance-hereditary comparability graphs, that is, those graphs which admit a transitive orientation and are completely decomposable with respect to the split decomposition. We provide a characterization in terms of forbidden subgraphs. We also provide further characterizations and one of them, based on the split decomposition, is used to devise a recognizing algorithm working in linear time. Finally, we show how to build distance-hereditary comparability graphs.     

Circular-arc graph coloring: On chords and circuits in the meeting graph

In compilers register allocation in loops is usually performed by coloring a corresponding circular-arc graph. Generally, the problem of finding the chromatic number of circular-arc graphs is known to be NP-complete. Thus, approximation algorithms should be considered. In this paper we propose heuristics based on decomposition of a so called meeting graph into a set of circuits. We explain the importance of the meeting graph for our solutions and prove properties of our decomposition of the graph into circuits. We derive inequalities relating the number of circuits in the decomposition to the size of the maximum stable set of chords, and present experimental results. Finally, we discuss the quality of our heuristics for circular-arc graph coloring.     

Planar graphs: Random walks and bipartiteness testing

We initiates the study of property testing in arbitrary planar graphs. We prove that bipartiteness can be tested in constant time, improving on the previous bound of for graphs on n vertices. The constant‐time testability was only known for planar graphs with bounded degree. Our algorithm is based on random walks. Since planar graphs have good separators, that is, bad expansion, our analysis diverges from standard techniques that involve the fast convergence of random walks on expanders. We reduce the problem to the task of detecting an odd‐parity cycle in a multigraph induced by constant‐length cycles. We iteratively reduce the length of cycles while preserving the detection probability, until the multigraph collapses to a collection of easily discoverable self‐loops. Our approach extends to arbitrary minor‐free graphs. We also believe that our techniques will find applications to testing other properties in arbitrary minor‐free graphs.     

Scheduling orders for multiple product types to minimize total weighted completion time

We consider the problem of scheduling orders for multiple different product types in an environment with m dedicated machines in parallel. The objective is to minimize the total weighted completion time. Each product type is produced by one and only one of the m dedicated machines; that is, each machine is dedicated to a specific product type. Each order has a weight and may also have a release date. Each order asks for certain amounts of various different product types. The different products for an order can be produced concurrently. Preemptions are not allowed. Even when all orders are available at time 0, the problem has been shown to be strongly NP-hard for any fixed number (?2) of machines. This paper focuses on the design and analysis of efficient heuristics for the case without release dates. Occasionally, however, we extend our results to the case with release dates. The heuristics considered include some that have already been proposed in the literature as well as several new ones. They include various static and dynamic priority rules as well as two more sophisticated LP-based algorithms. We analyze the performance bounds of the priority rules and of the algorithms and present also an in-depth comparative analysis of the various rules and algorithms. The conclusions from this empirical analysis provide insights into the trade-offs with regard to solution quality, speed, and memory space.     

The one-to-one shortest-path problem: An empirical analysis with the two-tree Dijkstra algorithm

Four new shortest-path algorithms, two sequential and two parallel, for the source-to-sink shortest-path problem are presented and empirically compared with five algorithms previously discussed in the literature. The new algorithm, S22, combines the highly effective data structure of the S2 algorithm of Dial et al., with the idea of simultaneously building shortest-path trees from both source and sink nodes, and was found to be the fastest sequential shortest-path algorithm. The new parallel algorithm, PS22, is based on S22 and is the best of the parallel algorithms. We also present results for three new S22-type shortest-path heuristics. These heuristics find very good (often optimal) paths much faster than the best shortest-path algorithm.     

A parallel clustering technique for the vehicle routing problem with split deliveries and pickups

In this paper, a parallel clustering technique and route construction heuristic have been developed for the vehicle routing problem (VRP) with split deliveries and pickups. An MILP formulation for determining the exact solution to the problem has also been included. It has been shown through extensive experimentation that the algorithm proposed in this paper statistically produces better results than the only heuristic existing for this class of problems in literature. We also form a basis of comparison between this class of problems and the VRP with simultaneous deliveries and pickups. We note that while heuristics for simultaneous deliveries and pickups cannot be applied in situations where customers' delivery or pickup demands exceed the vehicle capacity, heuristics allowing split deliveries and pickups can, in fact, be applied in every situation, even producing superior results under the combined objective of minimization of the fixed charge and mileage associated with vehicle routes. A guideline as to which heuristic could be used under what parametric conditions and objective functions, has also been provided.     

A graph-theoretic approach to interval scheduling on dedicated unrelated parallel machines

We study the problem of scheduling n non-preemptive jobs on m unrelated parallel machines. Each machine can process a specified subset of the jobs. If a job is assigned to a machine, then it occupies a specified time interval on the machine. Each assignment of a job to a machine yields a value. The objective is to find a subset of the jobs and their feasible assignments to the machines such that the total value is maximized. The problem is NP-hard in the strong sense. We reduce the problem to finding a maximum weight clique in a graph and survey available solution methods. Furthermore, based on the peculiar properties of graphs, we propose an exact solution algorithm and five heuristics. We conduct computer experiments to assess the performance of our and other existing heuristics. The computational results show that our heuristics outperform the existing heuristics.     

Decomposition of 3-connected graphs

Cunningham and Edmonds [4[ have proved that a 2-connected graphG has a unique minimal decomposition into graphs, each of which is either 3-connected, a bond or a polygon. They define the notion of a good split, and first prove thatG has a unique minimal decomposition into graphs, none of which has a good split, and second prove that the graphs that do not have a good split are precisely 3-connected graphs, bonds and polygons. This paper provides an analogue of the first result above for 3-connected graphs, and an analogue of the second for minimally 3-connected graphs. Following the basic strategy of Cunningham and Edmonds, an appropriate notion of good split is defined. The first main result is that ifG is a 3-connected graph, thenG has a unique minimal decomposition into graphs, none of which has a good split. The second main result is that the minimally 3-connected graphs that do not have a good split are precisely cyclically 4-connected graphs, twirls (K _3,n for somen3) and wheels. From this it is shown that ifG is a minimally 3-connected graph, thenG has a unique minimal decomposition into graphs, each of which is either cyclically 4-connected, a twirl or a wheel.Research partially supported by Office of Naval Research Grant N00014-86-K-0689 at Purdue University.     

NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs

We present NC-approximation schemes for a number of graph problems when restricted to geometric graphs including unit disk graphs and graphs drawn in a civilized manner. Our approximation schemes exhibit the same time versus performance trade-off as the best known approximation schemes for planar graphs. We also define the concept of λ-precision unit disk graphs and show that for such graphs the approximation schemes have a better time versus performance trade-off than the approximation schemes for arbitrary unit disk graphs. Moreover, compared to unit disk graphs, we show that for λ-precision unit disk graphs many more graph problems have efficient approximation schemes.Our NC-approximation schemes can also be extended to obtain efficient NC-approximation schemes for several PSPACE-hard problems on unit disk graphs specified using a restricted version of the hierarchical specification language of Bentley, Ottmann, and Widmayer. The approximation schemes for hierarchically specified unit disk graphs presented in this paper are among the first approximation schemes in the literature for natural PSPACE-hard optimization problems.     

Even and odd holes in cap‐free graphs

It is an old problem in graph theory to test whether a graph contains a chordless cycle of length greater than three (hole) with a specific parity (even, odd). Studying the structure of graphs without odd holes has obvious implications for Berge's strong perfect graph conjecture that states that a graph G is perfect if and only if neither G nor its complement contain an odd hole. Markossian, Gasparian, and Reed have proven that if neither G nor its complement contain an even hole, then G is β‐perfect. In this article, we extend the problem of testing whether G(V, E) contains a hole of a given parity to the case where each edge of G has a label odd or even. A subset of E is odd (resp. even) if it contains an odd (resp. even) number of odd edges. Graphs for which there exists a signing (i.e., a partition of E into odd and even edges) that makes every triangle odd and every hole even are called even‐signable. Graphs that can be signed so that every triangle is odd and every triangle is odd and every hole is odd are called odd‐signable. We derive from a theorem due to Truemper co‐NP characterizations of even‐signable and odd‐signable graphs. A graph is strongly even‐signable if it can be signed so that every cycle of length ≥ 4 with at most one chord is even and every triangle is odd. Clearly a strongly even‐signable graph is even‐signable as well. Graphs that can be signed so that cycles of length four with one chord are even and all other cycles with at most one chord are odd are called strongly odd‐signable. Every strongly odd‐signable graph is odd‐signable. We give co‐NP characterizations for both strongly even‐signable and strongly odd‐signable graphs. A cap is a hole together with a node, which is adjacent to exactly two adjacent nodes on the hole. We derive a decomposition theorem for graphs that contain no cap as induced subgraph (cap‐free graphs). Our theorem is analogous to the decomposition theorem of Burlet and Fonlupt for Meyniel graphs, a well‐studied subclass of cap‐free graphs. If a graph is strongly even‐signable or strongly odd‐signable, then it is cap‐free. In fact, strongly even‐signable graphs are those cap‐free graphs that are even‐signable. From our decomposition theorem, we derive decomposition results for strongly odd‐signable and strongly even‐signable graphs. These results lead to polynomial recognition algorithms for testing whether a graph belongs to one of these classes. © 1999 John Wiley & Sons, Inc. J Graph Theory 30: 289–308, 1999     

Minimal split completions

We study the problem of adding an inclusion minimal set of edges to a given arbitrary graph so that the resulting graph is a split graph, called a minimal split completion of the input graph. Minimal completions of arbitrary graphs into chordal and interval graphs have been studied previously, and new results have been added recently. We extend these previous results to split graphs by giving a linear-time algorithm for computing minimal split completions. We also give two characterizations of minimal split completions, which lead to a linear time algorithm for extracting a minimal split completion from any given split completion.We prove new properties of split graph that are both useful for our algorithms and interesting on their own. First, we present a new way of partitioning the vertices of a split graph uniquely into three subsets. Second, we prove that split graphs have the following property: given two split graphs on the same vertex set where one is a subgraph of the other, there is a sequence of edges that can be removed from the larger to obtain the smaller such that after each edge removal the modified graph is split.     

Crossing minimization in extended level drawings of graphs

The most popular method of drawing directed graphs is to place vertices on a set of horizontal or concentric levels, known as level drawings. Level drawings are well studied in Graph Drawing due to their strong application for the visualization of hierarchy in graphs. There are two drawing conventions: Horizontal drawings use a set of parallel lines and radial drawings use a set of concentric circles.In level drawings, edges are only allowed between vertices on different levels. However, many real world graphs exhibit hierarchies with edges between vertices on the same level. In this paper, we initiate the new problem of extended level drawings of graphs, which was addressed as one of the open problems in social network visualization, in particular, displaying centrality values of actors. More specifically, we study minimizing the number of edge crossings in extended level drawings of graphs. The main problem can be formulated as the extended one-sided crossing minimization problem between two adjacent levels, as it is folklore with the one-sided crossing minimization problem in horizontal drawings.We first show that the extended one-sided crossing minimization problem is NP-hard for both horizontal and radial drawings, and then present efficient heuristics for minimizing edge crossings in extended level drawings. Our extensive experimental results show that our new methods reduce up to 30% of edge crossings.     

Hereditary Efficiently Dominatable Graphs

An efficient dominating set (or perfect code) in a graph is a set of vertices the closed neighborhoods of which partition the graph's vertex set. We introduce graphs that are hereditary efficiently dominatable in that sense that every induced subgraph of the graph contains an efficient dominating set. We prove a decomposition theorem for (bull, fork, C₄)‐free graphs, based on which we characterize, in terms of forbidden induced subgraphs, the class of hereditary efficiently dominatable graphs. We also give a decomposition theorem for hereditary efficiently dominatable graphs and examine some algorithmic aspects of such graphs. In particular, we give a polynomial time algorithm for finding an efficient dominating set (if one exists) in a class of graphs properly containing the class of hereditary efficiently dominatable graphs by reducing the problem to the maximum weight independent set problem in claw‐free graphs.     

Parallel and fast sequential algorithms for undirected edge connectivity augmentation

1 ,E₂,..., such that ⋃_i≤τE_i optmially increases the connectivity by τ, for any integer τ. The main result of the paper is that this sequence of edge sets can be divided into O(n) groups such that within one group, all E_i are basically the same. Using this result, we improve on the running time of edge connectivity augmentation, as well as we give the first parallel (RNC) augmentation algorithm. We also present new efficient subroutines for finding the so-called extreme sets and the cactus representation of min-cuts required in our algorithms. Augmenting the connectivity of hypergraphs with ordinary edges is known to be structurally harder than that of ordinary graphs. In a weaker version when one exceptional hyperedge is allowed in the augmenting edge set, we derive similar results as for ordinary graphs. Received November 1995 / Revised version received July 1998 Published online March 16, 1999     

Rollout Algorithms for Stochastic Scheduling Problems

Stochastic scheduling problems are difficult stochastic control problems with combinatorial decision spaces. In this paper we focus on a class of stochastic scheduling problems, the quiz problem and its variations. We discuss the use of heuristics for their solution, and we propose rollout algorithms based on these heuristics which approximate the stochastic dynamic programming algorithm. We show how the rollout algorithms can be implemented efficiently, with considerable savings in computation over optimal algorithms. We delineate circumstances under which the rollout algorithms are guaranteed to perform better than the heuristics on which they are based. We also show computational results which suggest that the performance of the rollout policies is near-optimal, and is substantially better than the performance of their underlying heuristics.     

Parallelism, Preprocessing, and Reachability: A Hybrid Algorithm for Directed Graphs

The problem of reachability in a directed graph has resisted attempts at efficient parallelization. Only for fairly dense graphs can we efficiently achieve significant parallel speedups, using known methods. We describe a technique allowing significant parallel speedup even for moderately sparse graphs, following a sequential preprocessing step in which a representation of the graph is created.     

The Structure and Enumeration of Link Projections

We define a decomposition of link projections whose pieces we call atoroidal graphs. We describe a surgery operation on these graphs and show that all atoroidal graphs can be generated by performing surgery repeatedly on a family of well-known link projections. This gives a method of enumerating atoroidal graphs and hence link projections by recomposing the pieces of the decomposition.

     

A GRASP for Coloring Sparse Graphs

We first present a literature review of heuristics and metaheuristics developed for the problem of coloring graphs. We then present a Greedy Randomized Adaptive Search Procedure (GRASP) for coloring sparse graphs. The procedure is tested on graphs of known chromatic number, as well as random graphs with edge probability 0.1 having from 50 to 500 vertices. Empirical results indicate that the proposed GRASP implementation compares favorably to classical heuristics and implementations of simulated annealing and tabu search. GRASP is also found to be competitive with a genetic algorithm that is considered one of the best currently available for graph coloring.