Graph-Theoretic Concepts in Computer Science

The following text is a written version of the dinner speech, which was given by the author at the occasion of the 25th Workshop on Graphtheoretic Concepts in Computer Science (WG ’99), Ascona, June 18, 1999.

In this paper we survey results on the design and analysis of online algorithms, focusing on problems where graphs and graphtheoretic concepts have proven particularly useful in the formulation or in the solution of the problem. For each of the problems addressed, we also present important open questions.

This talk surveys two- and three-dimensional packing problems in the textile and leather manufacturing industry as well as in the automobile industry and presents methods for solving such problems. We solve these problems with methods from combinatorial optimization. Our research leads to software that is used in the respective industrial branches.On leather, the problem is to place stencils (for objects such as sofas, car seats, shoes etc.) on a leather hide such as to minimize the waste and to obey certain restrictions pertaining to leather quality. Since runtime requirements are tough, we are using a greedy placement strategy here that employs a shape fitting method based on a variant of geometric hashing.Work on leather is joint with Jörg Heistermann, Ralf Heckmann, and Birgit Fromme.On textiles, the problem is analogous to the leather case. Here, the fabric is rectangular, rotations of the stencils are restricted, and quality restrictions are replaced with a wide variety of constraints pertaining to patterns on the fabric. Cutting images can be reused in this case, and therefore more runtime is allowed. The most successful algorithmic variant for this case employs a fast randomized strategy for generating cutting images. This strategy is based on Minkowski sums. We can generate up to 1 Mio images per hour, the best of which is postoptimized with simulated annealing or a linear-programming method and then offered as the solution. On fabric, we can also compute lower bounds. For this purpose, we extend a branch-and-bound technique by Milenkovic to compute bounds that are quite tight (below 1 percentage point of waste) for pants and less tight (within several percentage points) on jackets. We also developed an algorithm that uses a database of cutting images to generate cutting images based on their similarity to already computed high-quality cutting images. By continually extending the database with cutting images computed by the algorithm, the algorithm is able to learn. Work on textiles is joint with Ralf Heckmann at GMD-SCAI. Research on textiles has been partially supported by the German National Science Foundation (DFG).Arrangement problems in the car manufacturing industry take many forms and are generally not yet very accessible to automation. The reason is the multitude of constraints on these problems (geometric, electromagnetic, thermal, maintenance, ergonomic) and the elusiveness of the cost function. We have chosen an approach in stages to make these problem more amenable to automation. In stage 1, we extended our approach to chip layout to three dimensions, in order to pack boxes with electronic modules in cars. Here the shapes are brick-like. In stage 2, we develop methods based on combinatorial optimization that pack more general - even nonconvex - 3D shapes. We use a two-phase method here. In the first phase we generate variants of the relative position and orientation of these shapes. In the second stage we apply a local compaction method that is able to change the orientation of the objects within limits. Here, we extend a method by Milenkovic to three dimensions. In the third stage, we integrate the methods that have been developed and propose scenarios for their application in the automobile industry. Packing electronic parts, packing parts in trunks of cars, and inserting modules like dynamos etc. into preplaced engine spaces are examples of such scenarios. Work on automobiles is in progress and is joint with Mike Schäfer at the Department of Computer Science, University of Bonn. Research on automobiles has been partially supported by the German Federal Ministry for Education and Research (BMBF).

Le trasformazioni in corso costituiscono una ri-voluzione, una rottura con le premesse culturali che ci hanno guidato finora, uno strappo dalle promesse che politologi e futurologi ci hanno prodigato nel tempo. Ogni continuita’ col passato e’ solo apparente, le dinamiche in realta’ sono caotiche, e le divergenze sono radicali. L’informatica, uno degli enzimi di questa trasformazione, si manifesta come ibrido scientifico- filosofico ed agisce come motore sia tecnico che culturale di questo processo di ri-definizione della vita sociale. La scuola diventa il nuovo centro di trasformazione del sociale, il momento di fissione delle regole attive della nuova societa’. Al tempo stesso, il sostrato su cui queste trasformazioni sono costrette ad operare e’ la comunita’.Uno sguardo, dal centro della trasformazione, a queste tre componenti e la loro interazione.

This paper considers informative labeling schemes for graphs. Specifically, the question introduced is whether it is possible to label the vertices of a graph with short labels in such a way that the distance between any two vertices can be inferred from inspecting their labels. A labeling scheme enjoying this property is termed a proximity-preserving labeling scheme. It is shown that for the class of n-vertex weighted trees with M-bit edge weights, there exists such a proximity-preserving labeling scheme using O(M log n + log2n) bit labels. For the family of all n-vertex unweighted graphs, a labeling scheme is proposed that using O(log2n · k · n1/k) bit labels can provide approximate estimates to the distance, which are accurate up to a factor of √κ. In particular, using O(log3n) bit labels the scheme can provide estimates accurate up to a factor of √2 log n. (For weighted graphs, one of the log n factors in the label size is replaced by a factor logarithmic in the network’s diameter.) In addition to their theoretical interest, proximity-preserving labeling systems seem to have some relevance in the context of communication networks. We illustrate this by proposing a potential application of our labeling schemes to efficient distributed connection setup in circuit- switched networks.

In this paper we study algorithms for “Dial-a-Ride” transportation problems. In the basic version of the problem we are given transportation jobs between the vertices of a graph and the goal is to find a shortest transportation that serves all the jobs. This problem is known to be NP-hard even on trees. We consider the extension when precedence relations between the jobs with the same source are given. Our results include a polynomial time algorithm on paths and approximation algorithms general graphs and trees with performances of 9/4 and 5/3, respectively.

The shortest common superstring problem (SCS) is known to be NP-hard and APX-hard. The APX-hardness was proved for the SCS in [BJLTY94], but the reduction used in that paper produces instances with arbitrarily large alphabets. We show that the problem is APX-hard even if the size of the alphabet is 2.A lot of results concerning approximation algorithms have been published. We use our result to establish the first explicit inapproximability results for the SCS.

In an edge modification problem one has to change the edge set of a given graph as little as possible so as to satisfy a certain property. We prove in this paper the NP-hardness of a variety of edge modification problems with respect to some well-studied classes of graphs. These include perfect, chordal, chain, comparability, split and asteroidal triple free. We show that some of these problems become polynomial when the input graph has bounded degree. We also give a general constant factor approximation algorithm for deletion and editing problems on bounded degree graphs with respect to properties that can be characterized by a finite set of forbidden induced subgraphs.

We examine a network design problem under the reload cost model. Given an undirected edge colored graph, reload costs arise at the nodes of the graph and are depending on the colors of the pair of edges used by a walk through the node.In this paper we consider the problem of finding a spanning tree of minimum diameter with respect to the underlying reload costs. We present hardness results and lower bounds for the approximability even on graphs with maximum degree 5. On the other hand we provide an exact algorithm for graphs of maximum degree 3.

This paper studies the complexity of the Maximum Induced Matching problem (MIM) in regular graphs and trees. We show that the largest induced matchings in a regular graph of degree d can be approximated with a performance ratio less than d. However MIM is NP-hard to approximate within some constant c > 1 even if the input is restricted to various classes of bounded degree and regular graphs. Finally we describe a simple algorithm providing a linear time optimal solution to MIM if the input graph is a tree.

We develop an O(n3) algorithm for deciding if an n-vertex digraph has a subset of vertices with the property that each vertex of the graph has an even number of arcs into the subset. This algorithm allows us to give a combinatorial interpretation of Gauss-Jordan and Gauss elimination on square boolean matrices. In addition to solving this independence-mod-2 (even) set existence problem we also give efficient algorithms for related domination-mod-2 (odd) set existence problems on digraphs. However, for each of the four combinations of these two properties we show that even though the existence problem on digraphs is tractable, the problems of deciding the existence of a set of size exactly k, larger than k, or smaller than k, for a given k, are all NP-complete for undirected graphs.

NLCk is a family of algebras on vertex-labeled graphs introduced by Wanke. An NLC-decomposition of a graph is a derivation of this graph from single vertices using the operations in question. The width of the decomposition is the number of labels used, and the NLC-width of the graph is the smallest width among its NLC-decompositions. Many difficult graph problems can be solved efficiently with dynamic programming if an NLC-decomposition of low width is given for the input graph. It is unknown though whether arbitrary graphs of NLC-width at most k can be decomposed with k labels in polynomial time. So far this has been possible only for k = 1, which corresponds to cographs. In this paper, an algorithm is presented that works for k = 2. It runs in O(n4 log n) time and uses O(n2) space. Related concepts: clique-decomposition, cliquewidth.

When working on systems of the real world, abstractions in the form of graphs have proven a superior modeling and representation approach. This paper is on the analysis of such graphs. Based on the paradigm that a graph of a system contains information about the system’s structure, the paper contributes within the following respects: 1. It introduces a new and lucid structure measure, the so-called weighted partial connectivity, Λ, whose maximization defines a graph’s structure (Section 2). 2. It presents a fast algorithm that approximates a graph’s optimum Λ-value (Section 3).Moreover, the proposed structure definition is compared to existing clustering approaches (Section 4), resulting in a new splitting theorem concerning the well-known minimum cut splitting measure. A key concept of the proposed structure definition is its implicit determination of an optimum number of clusters.Different applications, which illustrate the usability of the measure and the algorithm, round off the paper (Section 5).

Graphs of clique—width at most k were introduced by Courcelle, Engelfriet and Rozenberg (1993) as graphs which can be defined by k-expressions based on graph operations which use k vertex labels. In this paper we study the clique—width of perfect graph classes. On one hand, we show that every distance—hereditary graph, has clique—`width at most 3, and a 3—expression defining it can be obtained in linear time. On the other hand, we show that the classes of unit interval and permutation graphs are not of bounded clique—width. More precisely, w e show that for every n ∈ N there is a unit interval graph I_n and a permutation graph H_n having n2 vertices, each of whose clique—width is exactly n+1. These results allowus to see the borderwithin the hierarchy of perfect graphs between classes whose clique—width is bounded and classes whose clique—width is unbounded. Finally we show that every n×n square grid, n. N, n ≥ 3, has clique—width exactly n + 1.

We present a modification of Bodlaender’s linear time algorithm that, for constant k, determines whether an input graph G = (V,E) has treewidth k and, if so, constructs a tree decomposition of G of width at most k. Our algorithm has the following additional feature: if G has treewidth greater than k then a subgraph G′ of G of treewidth greater than k is returned along with a tree decomposition of G′ of width at most 2k. A consequence is that the fundamental disjoint rooted paths problem can now be solved in O(n2) time. This is the primary motivation for this paper.

We consider the class C* of graphs whose minimal separators have a fixed bounded size. We give an O(nm)-time algorithm computing an optimal tree-decomposition of every graph in C* with n vertices and m edges. Furthermore we make evident that many NP-complete problems are solvable in polynomial time when restricted to this class. Both claims hold although C* contains graphs of arbitrarily large tree-width.

We present an efficient algorithm which computes the set of minimal separators of a graph in O(n3) time per separator, thus gaining a factor of n2 on the current best-time algorithms for this problem. Our process is based on a newst ructural result, derived from the work of Kloks and Kratsch on listing all the minimal separators of a graph.

We consider two broadcasting problems in the n-dimensional hypercube under the shouting communication mode, i.e. any node of a network can inform all its neighbours in one time step. In addition, during any time step a number of links of the network can be faulty. Moreover the faults are dynamic. The first problem is to find an upper bound on the number of time steps necessary to complete the broadcasting if at most n - 1 links are faulty in any step. Fraigniaud and Peyrat [10] proved that n+O(log n) time steps are sufficient. De Marco and Vaccaro [8] decreased the upper bound to n + 7 and showed a worst case lower bound n + 2 for n ≥ 3. We prove that n + 2 time steps are sufficient. The second problem from [8] is to find the maximal number k such that the broadcasting time remains n if at most k faults are allowed in any step. We prove that k equals either n-2 or n-3. Our method is related to the isoperimetric problem in graphs and can be applied to other networks.

We study an n-dimensional directed symmetric hypercube H _n , in which every pair of adjacent vertices is connected by two arcs of opposite directions. Using the computer, we show that for H₄ and for any permutation on its vertices, there exists a system of pairwise arc-disjoint directed paths from each vertex to its target in the permutation. This gives the answer to Szymanski’s conjecture [Szy89] for dimension 4. In addition to this study, we consider in H_n the so-called 2-1 routing requests, that is routing requests where any vertex of H_n can be used twice as a source, but only once as a target. We give two such routing requests which cannot be routed in H₃. Moreover, we show that for any dimension n ≥ 3, it is possible to find a 2-1 routing request gn such that gn cannot be routed in H _n : in other words, for any n ≥ 3, H _n is not (2-1)-rearrangeable.

We study the problem of designing fault-tolerant routings for a communication network which is a triconnected planar network of processors in the surviving route graph model. The surviving route graph for a graph G, a routing ρ anda set of faults F is a directed graph consisting of nonfaulty nodes with a directed edge from a node x to a node y iff there are no faults on the route from x to y. The diameter of the surviving route graph couldb e one of the fault-tolerance measures for the graph G andt he routing ρ. In this paper, we show that we can construct a routing for any triconnectedpl anar graph with a triangle face such that the diameter of the surviving route graphs is two(thus optimal) for any faults F(|F| ≤ 2). We also show that the optimal routing can be computedin linear time.

Let G be a simple connected graph where every node is colored either black or white. Consider now the following repetitive process on G:eac h node recolors itself, at each local time step, with the color held by the majority of its neighbors. Since the clocks are not necessarily synchronized, the process can be asynchronous.

Knödel graphs and Fibonacci graphs are two classes of bipartite incident-graph of circulant digraphs. Both graphs have been extensively studied for the purpose of fast communications in networks, and they have deserved a lot of attention in this context. In this paper, we show that there exists an O(n log5n)-time algorithm to recognize Knödel graphs, and that the same technique applies to Fibonacci graphs. The algorithm is based on a characterization of the cycles of length six in these graphs (bipartite incident-graphs of circulant digraphs always have cycles of length six). A consequence of our result is that none of the Knödel graphs are edge-transitive, apart those of 2k -2 vertices. An open problem that arises in this field is to derive a polynomial-time algorithm for any infinite family of bipartite incident-graphs of circulant digraphs indexed by their number of vertices.

In this paper we introduce a new order on the set of n- dimensional tuples and prove that this order preserves nestedness in the edge isoperimetric problem for the graph Pn, defined as the nth cartesian power of the well-known Petersen graph. Thus, we show, that there is a graph for which powers the solution of the edge isoperimetric problem preserve nestedness and it is different from the lexicographic order. With respect to this result we determine the cutwidth and wirelength of Pn. These results are then generalized to the cartesian product of Pn and the m-dimensional binary hypercube.

We consider the dihamiltonian decomposition problem for 3- regular graphs. A graph G is dihamiltonian decomposable if in the digraph obtained from G by replacing each edge of G as two directed edges, the set of edges are partitioned into 3 edge-disjoint directed hamiltonian cycles. We suggest some conditions for dihamiltonian decomposition of 3-regular graphs: for a 3-regular graph G, it is dihamiltonian decomposable only if it is bipartite, and it is not dihamiltonian decomposable if the number of vertices is a multiple of 4. Applying these conditions to interconnection network topologies, we investigate dihamiltonian decomposition of cubeconnected cycles, chordal rings, etc.

In this paper we introduce a new drawing style of a plane graph G, called a “box-rectangular drawing.” It is defined to be a drawing of G on an integer grid such that every vertex is drawn as a rectangle, called a box, each edge is drawn as either a horizontal line segment or a vertical line segment, and the contour of each face is drawn as a rectangle. We establish a necessary and sufficient condition for the existence of a box-rectangular drawing of G. We also give a simple lineartime algorithm to find a box-rectangular drawing of G if it exists.

We describe a multi-scale approach to the problem of drawing undirected straight-line graphs “nicely”. In contrast to conventional global/dynamic algorithms, we employ increasingly coarser-scale representations of the graph, together with a simple local organization scheme, without imposing formal criteria on the quality of the picture at large. Our algorithm can deal easily with very large graphs; some of our examples contain over 1000 vertices.

Lai and Leinwand have shown that an arbitrary plane (i.e., embedded planar) graph G can be transformed, bya dding crossover vertices, into a new plane graph G′ admitting a rectangular dual. Moreover, theyc onjectured that finding a minimum set of such crossover vertices is an NP-complete problem. In this paper it is shown that the above problem can be resolved in polynomial time by reducing it to a graph covering problem, and an efficient algorithm for finding a minimum set of edges on which to insert the crossover vertices is also presented.

In random geometric graphs, vertices are randomly distributed on [0, 1]2 and pairs of vertices are connected by edges whenever they are sufficiently close together. Layout problems seek a linear ordering of the vertices of a graph such that a certain measure is minimized. In this paper, we study several layout problems on random geometric graphs: Bandwidth, Minimum Linear Arrangement, Minimum Cut, Minimum Sum Cut, Vertex Separation and Bisection. We first prove that some of these problems remain NP-complete even for geometric graphs. Afterwards, we compute lower bounds that hold with high probability on random geometric graphs. Finally, we characterize the probabilistic behavior of the lexicographic ordering for our layout problems on the class of random geometric graphs.

The diversity of application areas relying on tree-structured data results in a wide interest in algorithms which determine differences or similarities among trees. One way of measuring the similarity between trees is to find the smallest common superstructure or supertree, where common elements are typically defined in terms of a mapping or embedding. In the simplest case, a supertree will contain exact copies of each input tree, so that for each input tree, each vertex of a tree can be mapped to a vertex in the supertree such that each edge maps to the corresponding edge. More general mappings allow for the extraction of more subtle common elements captured by looser definitions of similarity. We consider supertrees under the general mapping of minor containment. Minor containment generalizes both subgraph isomorphism and topological embedding; as a consequence of this generality, however, it is NP-complete to determine whether or not G is a minor of H, even for general trees. By focusing on trees of bounded degree, we obtain an O(n3) algorithm which determines the smallest tree T such that both of the input trees are minors of T, even when the trees are assumed to be unrooted and unordered.

Recently, there have been increasing interests and progresses in lowering the worst case time complexity for well-known NP-hard problems, in particular for the Vertex Cover problem. In this paper, new properties for the Vertex Cover problem are indicated and several new techniques are introduced, which lead to a simpler and improved algorithm of time complexity O(kn + 1.271kk2) for the problem. Our algorithm also induces improvement on previous algorithms for the Independent Set problem on graphs of small degree.

In a cooperation with the national German railway company, we construct a directed graph from a set of train time tables where train stations correspond to vertices, and where pairs of consecutive stops of trains correspond to edges. We consider the problem of locating vertices of this time table graph that intuitively correspond to train stations where the underlying railroad network branches into several directions, and that induce a partition of the edge set into bundles.We formulate this problem as a graph theoretic optimization problem, and show for two versions of the problem that they are NP-hard. For the first version we show that it is even NP-complete to decide whether any other solution besides the trivial one exists.

In this paper we describe a computational study to solve hard frequency assignment problems (FAPs) to optimality using a tree decomposition of the graph that models interference constraints. We present a dynamic programming algorithm which solves FAPs based on this tree decomposition. With the use of several dominance and bounding techniques it is possible to solve small and medium-sized real-life instances of the frequency assignment problem to optimality. Moreover, with an iterative version of the algorithm we obtain good lower bounds for large-sized instances within reasonable time and memory limits.

A λ-labeling of a graph G is an assignment of labels from the set {0,...,λ} to the vertices of a graph G such that vertices at distance at most two get different labels and adjacent vertices get labels which are at least two apart. We study the minimum value λ = λ (G) such that G admits a λ-labeling. We show that for every fixed value k ≥ 4 it is NP-complete to determine whether λ(G) ≤ k. We further investigate this problem for sparse graphs (k-almost trees), extending the already known result for ordinary trees.In a generalization of this problem we wish to find a labeling such that vertices at distance two are assigned labels that differ by at least q and the labels of adjacent vertices differ by at least p (where p and q are given positive integers). We denote the minimum number of labels by L(G;p,q) (hence λ(G) = L(G;2, 1)). We show several hardness results for L(G; p, q) including that for any p < q ≥ 1 there is a λ = λ(p,q) such that deciding if L(G;p,q) ≤ λ(p,q) is NP-complete.

We prove that claw-free graphs, containing an induced dominating path, have a Hamiltonian path, and that two-connected claw-free graphs, containing an induced doubly dominating cycle or a pair of vertices such that there exist two internally disjoint induced dominating paths connecting them, have a Hamiltonian cycle. As a consequence, we obtain linear time algorithms for both problems if the input is restricted to (claw,net)-free graphs. These graphs enjoy those interesting structural properties.

We present an O(n2.376) algorithm for recognizing claw-free AT-free graphs and a linear-time algorithm for computing the set of all central vertices of a claw-free AT-free graph. In addition, we give efficient algorithms that solve the problems Independent set, Dominating set, and Coloring. We argue that all running times achieved are optimal unless better algorithms for a number of famous graph problems such as triangle recognition and bipartite matching have been found. Our algorithms exploit the structure of 2LexBFS schemes.

We study the problem of finding an acyclic orientation of an undirected graph G such that each path is contained in a limited number of maximal cliques of G. In general, in an acyclic oriented graph, each path is contained in more than one maximal cliques. We focus our attention on crown-free interval graphs, and show how to find an acyclic orientation of such a graph, which guarantees that each path is contained in at most four maximal cliques. The proposed technique is used to find approximated solutions for a class of related optimization problems where a solution corresponds to an acyclic orientation of graphs.

We call a T-vertex of a graph G = (V,E) a vertex z whose neighbourhood N(z) in G induces a triangulated graph, and we show that every C₄-free Berge graph either is a clique or contains at least two non-adjacent T-vertices. An easy consequence of this result is that every C₄-free Berge graph admits a T-elimination scheme, i.e. an ordering [v₁, v₂, . . . , v_n] of its vertices such that vi is a T-vertex in the subgraph induced by v_i, . . . , v_n in G.