Skip to main content

1995 | Buch

Graph-Theoretic Concepts in Computer Science

20th International Workshop, WG '94 Herrsching, Germany, June 16–18, 1994 Proceedings

herausgegeben von: Ernst W. Mayr, Gunther Schmidt, Gottfried Tinhofer

Verlag: Springer Berlin Heidelberg

Buchreihe : Lecture Notes in Computer Science

insite
SUCHEN

Über dieses Buch

This volume presents the proceedings of the 20th International Workshop on Graph-Theoretic Concepts in Computer Science (WG '94), held in Herrsching, Germany in June 1994.
The volume contains 32 thoroughly revised papers selected from 66 submissions and provides an up-to-date snapshot of the research performed in the field. The topics addressed are graph grammars, treewidth, special graph classes, algorithms on graphs, broadcasting and architecture, planar graphs and related problems, and special graph problems.

Inhaltsverzeichnis

Frontmatter
Domino treewidth
Extended abstract

We consider a special variant of tree-decompositions, called domino tree-decompositions, and the related notion of domino treewidth. In a domino tree-decomposition, each vertex of the graph belongs to at most two nodes of the tree. We prove that for every k, d, there exists a constant C k,d such that a graph with treewidth at most k and maximum degree at most d has domino treewidth at most C k,d The domino treewidth of a tree can be computed in O(n2 log n) time. There exist polynomial time algorithms that — for fixed k — decide whether a given graph G has domino treewidth at most k. If k is not fixed, this problem is NP-complete. The domino treewidth problem is hard for the complexity classes W[t] for all t ξ N, and hence the problem for fixed k is unlikely to be solvable in O(nc), where c is a constant, not depending on k.

Hans L. Bodlaender, Joost Engelfriet
A lower bound for treewidth and its consequences

We present a new lower bound for the treewidth (and hence the pathwidth) of a graph and give a linear-time algorithm to compute the bound. With the growing interest in treewidth based methods, this bound has many potential applications.Our bound helps shed new light on the structure of obstructions for width ω. As a result, we are able to characterize completely those treewidth obstructions of order ω+3. Unexpectedly, we find that these graphs are exactly the pathwidth obstructions of order ω+3. Further, we are also able to enumerate these obstructions.Surprisingly, while there is only one obstruction of order ω+2 for width ω, we find that the number of obstructions of order ω+3 alone is an asymptotically exponential function of ω. Our proof of this is based on the theory of partitions of integers and is the first non-trivial lower bound on the number of obstructions for treewidth.

Siddharthan Ramachandramurthi
Tree-width and path-width of comparability graphs of interval orders

The problem to decide whether the tree-width of a comparability graph is less than k is NP-complete, if k is part of the input. We prove that the tree-width of comparability graphs of interval orders can be determined in linear time and that it equals the path-width of the graph. Our proof is constructive, i.e., we give an explicit path decomposition of the graph.

Renate Garbe
A declarative approach to graph based modeling

The class of TGraphs, i.e. typed, attributed, and ordered directed graphs, is introduced as a general graph class for graph based modeling. TGraphs are suitable for a wide area of applications. A declarative approach to specifying subclasses of TGraphs by a combination of a schematic graphical description and an additional constraint language is given. The implementation of TGraphs by an appropriate software approach is described.

Jürgen Ebert, Angelika Franzke
Multilevel graph grammars

The classical double pushout approach to the algebraic theory of graph grammars is extended to multilevel graph representations, where parts of graphs are not visible and the information can be restored via the explicit application of productions. The notions of applicability and derivation are investigated and the compatibility of the representations with the derivations is shown. Production mechanisms for multilevel graph are motivated by problems in Visual Languages and the representation of Iconic Languages in particular.

Francesco Parisi-Presicce, Gabriele Piersanti
The algorithmic use of hypertree structure and maximum neighbourhood orderings

The use of (generalized) tree structure in graphs is one of the main topics in the field of efficient graph algorithms. The well-known partial κ-tree (resp. treewidth) approach belongs to this kind of research and bases on a tree structure of constant-size bounded maximal cliques. Without size bound on the cliques this tree structure of maximal cliques characterizes chordal graphs which are known to be important also in connection with relational database schemes where hypergraphs with tree structure (acyclic hypergraphs) and their elimination orderings (perfect elimination orderings for chordal graphs, Graham-reduction for acyclic hypergraphs) are studied.We consider here graphs with a tree structure which is dual (in the sense of hypergraphs) to that one of chordal graphs (therefore we call these graphs dually chordal). The corresponding vertex elimination orderings of these graphs are the maximum neighbourhood orderings. These orderings were studied recently in several papers and some of the algorithmic consequences of such orderings were given.The aim of this paper is a systematic treatment of the algorithmic use of maximum neighbourhood orderings. These orderings are useful especially for dominating-like problems (including Steiner tree) and distance problems. Many problems efficiently solvable for strongly chordal graphs remain efficiently solvable for dually chordal graphs too.Our results on dually chordal graphs not only generalize, but also improve and extend the corresponding results on strongly chordal graphs, since a maximum neighbourhood ordering (if it exists) can be constructed in linear time and we consequently use the underlying structure properties of dually chordal graphs closely connected to hypergraphs.

Andreas Brandstädt, Victor D. Chepoi, Feodor F. Dragan
On domination elimination orderings and domination graphs
Extended abstract

Several efficient algorithms have been proposed to construct a perfect elimination ordering of the vertices of a chordal graph. We study a generalization of perfect elimination orderings, so called domination elimination orderings (deo). We show that graphs with the property that each induced subgraph has a deo (domination graphs) are related to formulas that can be reduced to formulas with a very simple structure. We also show that every brittle graph and every graph with no induced house and no chordless cycle of length at least five (HC-free graphs) are domination graphs. Moreover, every ordering produced by the Maximum Cardinality Search Procedure on an HC-free graph is a deo.

Elias Dahihaus, Peter Hammer, Frédéric Maffray, Stephan Olariu
Complexity of graph covering problems

Given a fixed graph H, the H-cover problem asks whether an input graph G allows a degree preserving mapping f∶V(G)→V(H) such that for every v∈V(G), f(N G (v))=N H (f(v)). In this paper, we design efficient algorithms for certain graph covering problems according to two basic techniques. The first one is a reduction to the 2-SAT problem. The second technique exploits necessary and sufficient conditions for the existence of regular factors in graphs. For other infinite classes of graph covering problems we derive NP-completeness results by reductions from graph coloring problems. We illustrate this methodology by classifying all graph covering problems defined by simple graphs with at most 6 vertices.

Jan Kratochvíl, Andrzej Proskurowski, Jan Arne Telle
Dominoes

A graph is called a domino if every vertex is contained in at most two maximal cliques. The class of dominoes properly contains the class of line graphs of bipartite graphs, and is in turn properly contained in the class of claw-free graphs. We give some characterizations of this class of graphs, show that they can be recognized in linear time, give a linear time algorithm for listing all maximal cliques (which implies a linear time algorithm computing a maximum clique of a domino) and show that the PATHWIDTH problem remains NP-complete when restricted to the class of chordal dominoes.

T. Kloks, D. Kratsch, H. Müller
GLB-closures in directed acyclic graphs and their applications

A subset S of the vertices of a directed acyclic graph is called glb-closed, if it contains the greatest lower bounds of all pairs of vertices of S. The glb-closure of S is the smallest glb-closed subset containing S. An efficient output sensitive algorithm for computing glb-closures is presented and two applications in the field of object-oriented programming languages are discussed.

Volker Turau, Weimin Chen
Minimum vertex cover, distributed decision-making, and communication complexity
Extended abstract

In this paper we study the problem of computing approximate vertex covers of a graph on the basis of partial information and we consider the distributed decision-making and the communication complexity frameworks. In the first framework we do not allow communication among the processors: in this case, we show an optimal algorithm whose performance ratio is equal to p where p is the number of processors. In the second framework two processors are allowed to communicate in order to find an approximate solution: in this latter case, we show a linear lower bound on the communication complexity of the problem.

Pierluigi Crescenzi, Luca Trevisan
Cartesian products of graphs as spanning subgraphs of de Bruijn graphs
Extended abstract

For Cartesian products G=G1×⋯× G m (m≥2) of nontrivial connected graphs G i and the n-dimensional base B de Bruijn graph D=D B (n), we investigate whether or not there exists a spanning subgraph of D which is isomorphic to G. We show that G is never a spanning subgraph of D when n is greater than three or when n equals three and m is greater than two. For n=3 and m=2, we can show for wide classes of graphs that G cannot be a spanning subgraph of D. In particular, these non-existence results imply that D B (n) never contains a torus (i.e., the Cartesian product of m≥2 cycles) as a spanning subgraph when n is greater than two. For n=2 the situation is quite different: we present a sufficient condition for a Cartesian product G to be a spanning subgraph of D=D B (2). As one of the corollaries we obtain that a torus G=G1×⋯× G m is a spanning subgraph of D=D B (2) provided that ∥G∥=∥D∥ and that the G i are even cycles of length ≥4. In addition we apply our results to obtain embeddings of relatively small dilation of popular processor networks (as tori, meshes and hypercubes) into de Bruijn graphs of fixed small base.

Thomas Andreae, Michael Nölle, Gerald Schreiber
Specification of graph translators with triple graph grammars

Data integration is a key issue for any integrated set of software tools. A typical CASE environment, for instance, offers tools for the manipulation of requirements and software design documents, and it provides more or less sophisticated assistance for keeping these documents in a consistent state. Up to now, almost all data consistency observing or preserving integration tools are hand-crafted due to the lack of generic implementation frameworks and the absence of adequate specification formalisms. Triple graph grammars are intended to fill this gap and to support the specification of interdependencies between graph-like data structures on a very high level. Furthermore, they are the fundamentals of a new machinery for the production of batch-oriented as well as incrementally working data integration tools.

Andy Schürr
Using programmed graph rewriting for the formal specification of a configuration management system

Due to increasing complexity of hardware and software systems, configuration management has been receiving more and more attention in nearly all engineering domains (e.g. electrical, mechanical, and software engineering). This observation has driven us to develop a configuration management model (called CoMa) for managing systems of engineering design documents. The CoMa model integrates composition hierarchies, dependencies, and versions into a coherent framework based on a sparse set of essential configuration management concepts. In order to give a clear and comprehensible specification, the CoMa model is defined in a high-level, multi-paradigm specification language (PROGRES) which combines concepts from various disciplines (database systems, knowledge-based systems, graph rewriting systems, programming languages).

Bernhard Westfechtel
Exponential time analysis of confluent and boundary eNCE graph languages

eNCE (edge label neighborhood controlled) graph grammars belong to the most powerful graph rewriting systems with single-node graphs on the left-hand side of the productions. From an algorithmic point of view, confluent and boundary eNCE graph grammars are the most interesting subclasses of eNCE graph grammars. In confluent eNCE graph grammars, the order in which nonterminal nodes are substituted is irrelevant for the resulting graph. In boundary eNCE graph grammars, nonterminal nodes are never adjacent. In this paper, we show that given a confluent or boundary eNCE graph grammar G, the problem whether the language L(G) defined by G is empty, is DEXPTIME-complete.

K. Skodinis, E. Wanke
Time-optimal tree computations on sparse meshes

The main goal of this work is to fathom the suitability of the mesh with multiple broadcasting architecture (MMB) for some treerelated computations. We view our contribution at two levels: on the one hand we exhibit time lower bounds for a number of tree-related problems both on the CREW-PRAM and on the MMB. On the other hand, we show that these lower bounds are tight by exhibiting time-optimal tree algorithms on the MMB. Specifically, we show that the task of encoding and/or decoding n-node binary and ordered trees cannot be solved faster than Ω(log n) time even if the MMB has an infinite number of processors. We then go on to show that this lower bound is tight. We also show that the task of reconstructing n-node binary trees from their traversais can be performed in O(1) time on the same architecture. Our algorithms rely on novel time-optimal algorithms on sequences of parentheses that we also develop.

D. Bhagavathi, V. Bokka, H. Gurla, S. Olariu, J. L. Schwing
Prefix graphs and their applications

The range product problem is, for a given set S equipped with an associative operator o, to preprocess a sequence a1,⋯, an of elements from S so as to enable efficient subsequent processing of queries of the form: Given a pair (s, t) of integers with 1≤s≤t≤n, return a s oas+1 o⋯o a t . The generic range product problem and special cases thereof, usually with o computing the maximum of its arguments according to some linear order on S, have been extensively studied. We show that a large number of previous sequential and parallel algorithms for these problems can be unified and simplified by means of prefix graphs.

Shiva Chaudhuri, Torben Hagerup
The complexity of broadcasting in planar and decomposable graphs

Broadcasting in processor networks means disseminating a single piece of information, which is originally known only at some nodes, to all members of the network. The goal is to inform everybody using as few rounds as possible, that is to minimize the broadcasting time.Given a graph and a subset of nodes, the sources, the problem to determine its specific broadcast time, or more general to find a broadcast schedule of minimal length has been shown to be NP-complete. In contrast to other optimization problems for graphs, like vertex cover or traveling salesman, little was known about restricted graph classes for which polynomial time algorithms exist, for example for graphs of bounded treewidth. The broadcasting problem is harder in this respect because it does not have the finite state property. Here, we will investigate this problem in detail and prove that it remains hard even if one restricts to planar graphs of bounded degree or constant broadcasting time. A simple consequence is that the minimal broadcasting time cannot even be approximated with an error less than 1/8, unless P=NP.On the other hand, we will investigate for which classes of graphs this problem can be solved efficiently and show that broadcasting and even a more general version of this problem becomes easy for graphs with good decomposition properties. The solution strategy can efficiently be parallelized, too. Combining the negative and the positive results reveals the parameters that make broadcasting difficult. Depending on simple graph properties the complexity jumps from NC or P to NP.

Andreas Jakoby, Rüdiger Reischuk, Christian Schindelhauer
The maximal f-dependent set problem for planar graphs is in NC

The maximal f-dependent set (Max-f-DS) problem is the following problem: Given a graph G=(V, E) and a nonnegative integer-valued function f defined on V, find a maximal subset U of V such that no vertex u∈U has degree>f(u) in the subgraph induced by U. Whether the problem is in NC (or RNC) or not is an open question. Concerning this question, only a rather trivial result due to Diks, Garrido, and Lingas is known up to now, which says that the problem can be solved in NC if the maximum value of f is poly-logarithmic in the input size [Proceedings of the 2nd International Symposium on Algorithms, LNCS 557 (1991) 385–395]. In this paper, we show a nontrivial interesting result that the Max-f-DS problem for planar graphs can be solved in O(log5n) time with O(n) processors on a CRCW PRAM, where n is the input size.

Zhi -Zhong Chen
On-line convex planarity testing
Extended abstract

An important class of planar straight-line drawings of graphs are convex drawings, where all faces are drawn as convex polygons. A graph is said to be convex planar if it admits a convex drawing. We consider the problem of testing convex planarity in a dynamic environment, where a graph is subject to on-line insertions of vertices and edges. We present on-line algorithms for convex planarity testing with the following performance, where n denotes the number of vertices of the graph: convex planarity testing and insertion of vertices take worst-case time O(1), insertion of edges takes amortized time O(log n), and the space requirement of the data structure is O(n). Furthermore, we give a new combinatorial characterization of convex planar graphs.

Giuseppe Di Battista, Roberto Tamassia, Luca Vismara
Book embeddings and crossing numbers

The paper introduces the book crossing number problem which can be viewed as a variant of the well-known plane and surface crossing number problem or as a generalization of the book embedding problem. The book crossing number of a graph G is defined as the minimum number of edge crossings when the vertices of G are placed on the spine of a k-page book and edges are drawn on pages, so that each edge is contained by one page. We present polynomial time algorithms for drawing graphs in books with small number of crossings. One algorithm is suitable for sparse graphs and gives a drawing in which the number of crossings is within a multiplicative factor of O(log2n) from the optimal one under certain conditions. Using these drawings we improve the best known upper bound on the rectilinear crossing number, provided that m≥4n. We also derive a general lower bound on the book crossing number of any graph and present a second polynomial time algorithm to generate a drawing of any graph with O(m2/k2) many edge crossings. This number of crossings is within a constant multiplicative factor from our general lower bound of Ω(m3/n2k2), provided that m=Θ(n2). For several classes of well-known graphs, we also sharpen our algorithmic upper bounds by giving specific drawings.

Farhad Shahrokhi, Ondrej Sýkora, László A. Székely, Imrich Vrt'o
Measuring the distance to series-parallelity by path expressions

Many graph and network problems are easily solved in the special case of series-parallel networks, but are highly intractable in the general case. This paper considers two complexity measures of two-terminal directed acyclic graphs (st-dags) describing the “distance” of an st-dag from series-parallelity. The two complexity measures are the factoring complexity ψ(G) and the reduction complexity μ(G). Bein, Kamburowski, and Stallmann [3] have shown that ψ(G)≤μ(G)≤n−3, where G is an st-dag with n nodes. They conjectured that ψ(G)=μ(G). This paper gives a proof for this conjecture.

Valeska Naumann
Labelled trees and pairs of input-output permutations in priority queues

A priority queue can transform a permutation π of a set of size n to some but not necessarily all permutations σ. A recent result of Atkinson and Thiyagarajah [1] states that the number of distinct pairs (π, σ) is (n+1)n−1. Recall that Cayley's Theorem ([2]) states that the number of labelled trees on n+1 nodes is also equal to (n+1)n−1. We present a direct correspondence between these labelled trees and these pairs of permutations and discuss related problems.

M. Golin, S. Zaks
Rankings of graphs

A vertex (edge) coloring c∶V → {1, 2, ⋯, t} (c′∶E → {1, 2, ⋯, t}) of a graph G=(V, E) is a vertex (edge) t-ranking if for any two vertices (edges) of the same color every path between them contains a vertex (edge) of larger color. The vertex ranking number χ r (G) (edge ranking number $$\chi '_r \left( G \right)$$ ) is the smallest value of t such that G has a vertex (edge) t-ranking. In this paper we study the algorithmic complexity of the VERTEX RANKING and EDGE RANKING problems. Among others it is shown that χ r (G) can be computed in polynomial time when restricted to graphs with treewidth at most k for any fixed k. We characterize those graphs where the vertex ranking number χ r and the chromatic number χ coincide on all induced subgraphs, show that χ r (G)=χ(G) implies χ(G)=ω(G) (largest clique size) and give a formula for $$\chi '_r \left( {K_n } \right)$$ .

H. L. Bodlaender, J. S. Deogun, K. Jansen, T. Kloks, D. Kratsch, H. Müller, Zs. Tuza
Bypass strong V-structures and find an isomorphic labelled subgraph in linear time

This paper identifies a condition for which the existence of an isomorphic subgraph can be decided in linear time. The condition is evaluated in two steps. First the host graph is analysed to determine its strong V-structures. Then the guest graph must be appropriately represented. If this representation exists, the given algorithm constructively decides the subgraph isomorphism problem for the guest and the host graph in linear time.The result applies especially to the implementation of graph rewriting systems. An isomorphic subgraph must be determined automatically in each rewriting step. Thus the efficient solution presented in this paper is an important advancement for any implementation project.

Heiko Dörr
Efficient algorithms for a mixed k-partition problem of graphs without specifying bases

This paper describes efficient algorithms for partitioning a k-edge-connected graph into k edge-disjoint connected subgraphs, each of which has a specified number of elements(vertices and edges). If each subgraph contains the specified element (called base), we call this problem the mixed k-partition problem with bases(called k-PART-WB), otherwise we call it the mixed k-partition problem without bases (called k-PART-WOB). In this paper, we show that k-PART-WB always has a solution for every k-edge-connected graph and we consider the problem without bases and we obtain the following results: (1)for any k≥2, k-PART-WOB can be solved in O(∥V∥√∥V∥log2∥V∥+∥E∥) time for every 4-edge-connected graph G=(V,E), (2)3-PART-WOB can be solved in O(∥V∥2) for every 2-edge-connected graph G=(V,E) and (3)4-PART-WOB can be solved in O(∥E∥2) for every 3-edge-connected graph G=(V,E).

Koichi Wada, Akinari Takaki, Kimio Kawaguchi
Fugitive-search games on graphs and related parameters

The goal of a fugitive-search game on a graph is to trap a fugitive that hides on the vertices of the graph by systematically placing searchers on the vertices. The fugitive is assumed to have complete knowledge of the graph and of the searchers' moves, but is restricted to move only along paths whose vertices are not guarded by searchers. The search number of the graph is the least number of searchers necessary to trap the fugitive. Variants of the fugitive-search game have been related to important graph parameters like treewidth and pathwidth. In this paper, we introduce a class of fugitive-search games where the searchers do not see the fugitive and the fugitive can only move just before a searcher is placed on the vertex it occupies. Letting the fugitive's speed (i.e. the maximum number of edges the fugitive can traverse at a single move) vary, we get different games. We show that if the speed of the fugitive is unbounded then the search number minus 1 is equal to the treewidth of the graph, while if the speed is 1 then the search number minus 1 is equal to the width, a polynomially computable graph parameter. We also show that in the above two cases, the search number remains the same even if we consider only these search strategies that at every step further restrict the fugitive's possible resorts (this monotonicity phenomenon is usually expressed as: “recontamination does not help”). Finally, we show that for any graph, if the length of any chordless cycle is bounded by a constant s (s≥3), then the treewidth of the graph plus 1 is equal to the search number for fugitive speed s−2.

Nick D. Dendris, Lefteris M. Kirousis, Dimitris M. Thilikos
New approximation results on graph matching and related problems

For a graph G with e edges and n vertices, a maximum cardinality matching of G is a maximum subset M of edges such that no two edges of M are incident at a common vertex. The best known algorithm for solving the problem in general graphs requires O(n5/2) time. We first propose an approximate maximum cardinality matching algorithm that runs in O(e+n) sequential time yielding a matching of size at least e/n−1, improving the bound known before. For bipartite graphs, the algorithm yields a matching of size at least 2e/n. The proposed algorithms are extremely simple, and the derived lowerbounds are existentially tight. Next, the proposed maximum cardinality matching algorithm is extended to the weighted case running in O(e+n) time. The problem of approximate maximum matching has a number of applications, for example in, Vertex Cover, TSP, MAXCUT, and VLSI physical design problems.

Yoji Kajitani, Jun Dong Cho, Majid Sarrafzadeh
New lower bounds and hierarchy results for restricted branching programs

Known lower bound techniques for depth restricted branching programs are not sensitive enough to lead to tight hierarchies. A new lower bound technique implies the separation of the classes of polynomial-size branching programs, where on each path k variables may be tested more than once and k≤(1−ε)(n/3)1/3/ log2/3n for some ε>0. Methods from communication complexity theory are adopted to separate the classes of polynomial-size ordered read k times branching programs, where k=o(n1/2/ log2n).

Detlef Sieling, Ingo Wegener
On-line algorithms for satisfiability problems with uncertainty

In this paper the problem of the on-line satisfiability of a Horn formula with uncertainty is addressed; we show how to represent a significant class of formulae by weighted directed hypergraphs and we present two algorithms that solve the on-line SAT problem and find a minimal interpretation for the formula working on the dynamic hypergraph representation. These algorithms make increasing assumptions on the formula and we will find that the second one solves the on-line SAT problem with a total time linear in the size of the formula, matching the optimal result for boolean Horn formulae.

Roberto Giaccio
NC algorithms for antidirected hamiltonian paths and cycles in tournaments
Extended abstract

Two classical theorems about tournaments state that a tournament with no less than eight vertices admits an antidirected Hamiltonian path and an even cardinality tournament with no less than sixteen vertices admits an antidirected Hamiltonian cycle. Sequential algorithms for finding such a path as well as a cycle follow directly from the proofs of the theorems. Unfortunately, these proofs are inherently sequential and can not be exploited in a parallel context. In this paper we propose new proofs leading to efficient parallel algorithms.

E. Bampis, Y. Manoussakis, I. Milis
Directed path graph isomorphism
Extended abstract

This paper deals with the isomorphism problem of directed path graphs and rooted directed path graphs. Both graph classes belong to the class of chordal graphs, and for both classes the relative complexity of the isomorphism problem is yet unknown. We prove that deciding isomorphism of directed path graphs is isomorphism complete, whereas for rooted directed path graphs we present a polynomial-time isomorphism algorithm.

Luitpold Babel, Ilia Ponomarenko, Gottfried Tinhofer
Backmatter
Metadaten
Titel
Graph-Theoretic Concepts in Computer Science
herausgegeben von
Ernst W. Mayr
Gunther Schmidt
Gottfried Tinhofer
Copyright-Jahr
1995
Verlag
Springer Berlin Heidelberg
Electronic ISBN
978-3-540-49183-5
Print ISBN
978-3-540-59071-2
DOI
https://doi.org/10.1007/3-540-59071-4