Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top

2009 | Book

Landmarks in Algorithmic Graph Theory: A Personal Retrospective Read chapter Read first chapter

Graph Theory, Computational Intelligence and Thought

Essays Dedicated to Martin Charles Golumbic on the Occasion of His 60th Birthday

Editors: Marina Lipshteyn, Vadim E. Levit, Ross M. McConnell

Publisher: Springer Berlin Heidelberg

Book Series : Lecture Notes in Computer Science

Part of: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Login to get access
insite
SEARCH

About this book

Martin Charles Golumbic has been making seminal contributions to algorithmic graph theory and artificial intelligence throughout his career. He is universally admired as a long-standing pillar of the discipline of computer science. He has contributed to the development of fundamental research in artificial intelligence in the area of complexity and spatial-temporal reasoning as well as in the area of compiler optimization. Golumbic's work in graph theory led to the study of new perfect graph families such as tolerance graphs, which generalize the classical graph notions of interval graph and comparability graph. He is credited with introducing the systematic study of algorithmic aspects in intersection graph theory, and initiated research on new structured families of graphs including the edge intersection graphs of paths in trees (EPT) and trivially perfect graphs.

Golumbic is currently the founder and director of the Caesarea Edmond Benjamin de Rothschild Institute for Interdisciplinary Applications of Computer Science at the University of Haifa. He also served as chairman of the Israeli Association of Artificial Intelligence (1998-2004), and founded and chaired numerous international symposia in discrete mathematics and in the foundations of artificial intelligence.

This Festschrift volume, published in honor of Martin Charles Golumbic on the occasion of his 60th birthday, contains 20 papers, written by graduate students, research collaborators, and computer science colleagues, who gathered at a conference on subjects related to Martin Golumbic's manifold contributions in the field of algorithmic graph theory and artificial intelligence, held in Jerusalem, Tiberias and Haifa, Israel in September 2008.

Table of Contents

Frontmatter
Landmarks in Algorithmic Graph Theory: A Personal Retrospective
Abstract
This is an edited version of the conference lecture delivered by the author in celebration of his 60th birthday. It is intended to be an autobiographical tour through stories, pictures and theorems, suitable for both mathematicians and non-scientists.
Martin Charles Golumbic
A Higher-Order Graph Calculus for Autonomic Computing
Abstract
In this paper, we present a high-level formalism based on port graph rewriting, strategic rewriting, and rewriting calculus. We argue that this formalism is suitable for modeling autonomic systems and briefly illustrate its expressivity for modeling properties of such systems.
Oana Andrei, Hélène Kirchner
Algorithms on Subtree Filament Graphs
Abstract
We describe polynomial time algorithms to find in subtree filament graphs a minimum dominating hole, a clique intersecting all its maximum independent sets and a maximum induced split subgraph.
Fanica Gavril
A Note on the Recognition of Nested Graphs
Abstract
We consider a two-terminal directed acyclic graph (st-dag) characterized by a special structure of its mincuts and call it a nested graph. This graph is of interest as an st-dag with a minimum possible number of mincuts.We present a linear-time algorithm for recognizing nested graphs.
Mark Korenblit, Vadim E. Levit
Asynchronous Congestion Games
Abstract
We introduce a new class of games, asynchronous congestion games (ACGs). In an ACG, each player has a task that can be carried out by any element of a set of resources, and each resource executes its assigned tasks in a random order. Each player’s aim is to minimize his expected cost which is the sum of two terms – the sum of the fixed costs over the set of his utilized resources and the expected cost of his task execution. The cost of a player’s task execution is determined by the earliest time his task is completed, and thus it might be beneficial for him to assign his task to several resources. We show the existence of pure strategy Nash equilibria in ACGs. Moreover, we present a polynomial time algorithm for finding such an equilibrium in a given ACG.
Michal Penn, Maria Polukarov, Moshe Tennenholtz
Combinatorial Problems for Horn Clauses
Abstract
Given a family of Horn clauses, what is the minimal number of Horn clauses implying all other clauses in the family? What is the maximal number of Horn clauses from the family without having resolvents of a certain kind? We consider various problems of this type, and give some sharp bounds. We also consider the probability that a random family of a given size implies all other clauses in the family, and we prove the existence of a sharp threshold.
Marina Langlois, Dhruv Mubayi, Robert H. Sloan, György Turán
Covering a Tree by a Forest
Abstract
Consider a tree T and a forest F. The paper discusses the following new problems: The Forest vertex-cover problem (FVC): cover the vertices of T by a minimum number of copies of trees of F, such that every vertex of T is covered exactly once. TheForest edge-cover problem (FEC): cover the edges of T by a minimum number of copies of trees of F, such that every edge of T is covered exactly once. For a solution to always exist, we assume that F contains a one vertex (one edge) tree.
Two versions of Problem FVC are considered: ordered covers (OFVC), and unordered covers (UFVC). Three versions of Problem FEC are considered: ordered covers (OFEC), unordered covers (UFEC) and consecutive covers (CFEC). We describe polynomial time algorithms for Problems OFVC, UFVC and CFEC, and prove that Problems OFEC and UFEC are NP-complete.
Fanica Gavril, Alon Itai
Dominating Induced Matchings
Abstract
We study the problem of determining whether or not a graph G has an induced matching that dominates every edge of the graph, which is also known as efficient edge domination. This problem is known to be NP-complete in general as well as in some restricted domains, such as bipartite graphs or regular graphs. In this paper, we identify a graph parameter to which the complexity of the problem is sensible and produce results of both negative (intractable) and positive (solvable in polynomial time) type.
Domingos M. Cardoso, Vadim V. Lozin
HyperConsistency Width for Constraint Satisfaction: Algorithms and Complexity Results
Abstract
Generalized hypertree width (short: ghw) is a concept that leads to a large class of efficiently solvable CSP instances, whose associated recognition problem (of checking whether the ghw of a CSP is bounded by a constant k) is however known to be NP-hard. An elegant way to circumvent this intractability has recently been proposed in the literature, by means of a “no-promise” approach solving CSPs of bounded ghw without the need of actually computing a generalized hypertree decomposition. In fact, despite the conceptual relevance of this approach, its computational issues have not yet been investigated and, indeed, precise bounds on the running time of the no-promise algorithm are missing.
The first contribution of this paper is precisely to fill this gap. Indeed, the computational complexity of the no-promise approach is analyzed, by exploiting an intuitive characterization relying on the notion of hyperconsistency width. It turns out that, in the basic formulation, the approach is hardly suited for practical applications mainly because of its bad scaling in the size of the constraint database. Motivated by these news and based on a variant of hyperconsistency width, a different and more efficient method to decide whether CSPs of bounded ghw admit solutions is then provided. Importantly, the improved method exhibits the same scaling as current evaluation algorithms for instances of bounded hypertree width, nonetheless allowing to isolate a larger class of queries. Finally, to give a complete picture of the complexity issues of the no-promise approach, the problems of computing one solution and of enumerating all the solutions are also studied.
Georg Gottlob, Gianluigi Greco, Bruno Marnette
Local Search Heuristics for the Multidimensional Assignment Problem
Abstract
The Multidimensional Assignment Problem (MAP) (abbreviated s-AP in the case of s dimensions) is an extension of the well-known assignment problem. The most studied case of MAP is 3-AP, though the problems with larger values of s have also a number of applications. We consider several known and new MAP local search heuristics for MAP as well as their combinations. Computational experiments with three instance families are provided and discussed. As a result, we select dominating local search heuristics. One of the most interesting conclusions is that combination of two heuristics may yield a superior heuristic with respect to both solution quality and the running time.
G. Gutin, D. Karapetyan
On Distance-3 Matchings and Induced Matchings
Abstract
For a finite undirected graph G = (V,E) and positive integer k ≥ 1, an edge set M ⊆ E is a distance-k matching if the mutual distance of edges in M is at least k in G. For k = 1, this gives the usual notion of matching in graphs, and for general k ≥ 1, distance-k matchings were called k-separated matchings by Stockmeyer and Vazirani. The special case k = 2 has been studied under the names induced matching (i.e., a matching which forms an induced subgraph in G) by Cameron and strong matching by Golumbic and Laskar in various papers.
Finding a maximum induced matching is \(\mathbb{NP}\)-complete even on very restricted bipartite graphs but for k = 2, it can be done efficiently on various classes of graphs such as chordal graphs, based on the fact that an induced matching in G corresponds to an independent vertex set in the square L(G)2 of the line graph L(G) of G which, by a result of Cameron, is chordal for any chordal graph G.
We show that, unlike for k = 2, for a chordal graph G, L(G)3 is not necessarily chordal, and finding a maximum distance-3 matching remains \(\mathbb{NP}\)-complete on chordal graphs. For strongly chordal graphs and interval graphs, however, the maximum distance-3 matching problem can be solved in polynomial time. Moreover, we obtain various new results for induced matchings.
Andreas Brandstädt, Raffaele Mosca
On Duality between Local Maximum Stable Sets of a Graph and Its Line-Graph
Abstract
G is a König-Egervá ry graph provided \(\alpha(G)+\mu (G)=\left\vert V(G)\right\vert \), where μ(G) is the size of a maximum matching and α(G) is the cardinality of a maximum stable set,[2],[21].
S is a local maximum stable set of G, and we write S ∈ Ψ(G), if S is a maximum stable set of the subgraph induced by S ∪ N(S), where N(S) is the neighborhood of S,[11]. Nemhauser and Trotter Jr. proved that any S ∈ Ψ(G) is a subset of a maximum stable set of G,[19].
In this paper we demonstrate that if S ∈ Ψ(G), the subgraph H induced by S ∪ N(S) is a König-Egerváry graph, and M is a maximum matching in H, then M is a local maximum stable set in the line graph of G.
Vadim E. Levit, Eugen Mandrescu
On Path Partitions and Colourings in Digraphs
Abstract
We provide a new proof of a theorem of Saks which is an extension of Greene’s Theorem to acyclic digraphs, by reducing it to a similar, known extension of Greene and Kleitman’s Theorem. This suggests that the Greene-Kleitman Theorem is stronger than Greene’s Theorem on posets. We leave it as an open question whether the same holds for all digraphs, that is, does Berge’s conjecture concerning path partitions in digraphs imply the extension of Greene’s theorem to all digraphs (conjectured by Aharoni, Hartman and Hoffman)?
Irith Ben-Arroyo Hartman
On Related Edges in Well-Covered Graphs without Cycles of Length 4 and 6
Abstract
A graph is well-covered if every maximal independent set has the same cardinality. The recognition problem of well-covered graphs is known to be co-NPC. The complexity status of the problem is not known if the input is restricted to graphs with no cycles of length 4. We conjecture that the problem is polynomial if the input graph does not contain cycles of length 4 and 6, and prove several theorems supporting our conjecture.
Vadim E. Levit, David Tankus
On the Cubicity of AT-Free Graphs and Circular-Arc Graphs
Abstract
A unit cube in k dimensions (k-cube) is defined as the Cartesian product R 1×R 2× ⋯ ×R k where R i (for 1 ≤ i ≤ k) is a closed interval of the form [a i ,a i  + 1] on the real line. A graph G on n nodes is said to be representable as the intersection of k-cubes (cube representation in k dimensions) if each vertex of G can be mapped to a k-cube such that two vertices are adjacent in G if and only if their corresponding k-cubes have a non-empty intersection. The cubicity of G denoted as cub(G) is the minimum k for which G can be represented as the intersection of k-cubes.
An interesting aspect about cubicity is that many problems known to be NP-complete for general graphs have polynomial time deterministic algorithms or have good approximation ratios in graphs of low cubicity. In most of these algorithms, computing a low dimensional cube representation of the given graph is usually the first step.
We give an O(bw·n) algorithm to compute the cube representation of a general graph G in bw + 1 dimensions given a bandwidth ordering of the vertices of G, where bw is the bandwidth of G. As a consequence, we get O(Δ) upper bounds on the cubicity of many well-known graph classes such as AT-free graphs, circular-arc graphs and cocomparability graphs which have O(Δ) bandwidth. Thus we have:
1
cub(G) ≤ 3Δ− 1, if G is an AT-free graph.
 
1
cub(G) ≤ 2Δ + 1, if G is a circular-arc graph.
 
1
cub(G) ≤ 2Δ, if G is a cocomparability graph.
 
Also for these graph classes, there are constant factor approximation algorithms for bandwidth computation that generate orderings of vertices with O(Δ) width. We can thus generate the cube representation of such graphs in O(Δ) dimensions in polynomial time.
L. Sunil Chandran, Mathew C. Francis, Naveen Sivadasan
O(m logn) Split Decomposition of Strongly Connected Graphs
Abstract
In the early 1980’s, Cunningham described a unique decomposition of a strongly-connected graph. A linear time bound for finding it in the special case of an undirected graph has been given previously, but up until now, the best bound known for the general case has been O(n 3). We give an O(m logn) bound.
Benson L. Joeris, Scott Lundberg, Ross M. McConnell
Path-Bicolorable Graphs
(Extended Abstract)
Abstract
In this paper, we introduce the notion of path-bicolorability that generalizes bipartite graphs in a natural way: For k ≥ 2, a graph G = (V,E) is P k -bicolorable if its vertex set V can be partitioned into two subsets (i.e., colors) V 1 and V 2 such that for every induced P k (i.e., path with exactly k − 1 edges and k vertices) in G, the two colors alternate along the P k , i.e., no two consecutive vertices of the P k belong to the same color V i , i = 1,2. Obviously, a graph is bipartite if and only if is P 2-bicolorable, every graph is P k -bicolorable for some k and if G is P k -bicolorable then it is P k + 1-bicolorable. The notion of P k -bicolorable graphs is motivated by a similar notion of cycle-bicolorable graphs introduced in connection with chordal probe graphs. Moreover, P 3- and P 4-bicolorable graphs are closely related to various other concepts such as 2-subcolorable graphs, P 4-bipartite graphs and alternately orientable graphs.
We give a structural characterization of P 3-bicolorable graphs which also implies linear time recognition of these graphs. Moreover, we give a characterization of P 4-bicolorable graphs in terms of forbidden subgraphs.
Andreas Brandstädt, Martin C. Golumbic, Van Bang Le, Marina Lipshteyn
Path Partitions, Cycle Covers and Integer Decomposition
(Lecture Note)
Abstract
A polyhedron P has the integer decomposition property, if every integer vector in kP is the sum of k integer vectors in P. We explain that the projections of polyhedra defined by totally unimodular constraint matrices have the integer decomposition property, in order to deduce the same property for coflow polyhedra defined by Cameron and Edmonds. We then apply this result to the convex hull of particular stable sets in graphs. Therebye we prove a generalization of Greene and Kleitman’s well-known theorem on posets to arbitrary digraphs which implies recent and classical purely graph theoretical results on cycle covers, is closely related to conjectures of Berge and Linial on path partitions, and implies these for some particular values of the parameters.
András Sebő
Properly Coloured Cycles and Paths: Results and Open Problems
Abstract
In this paper, we consider a number of results and six conjectures on properly coloured (PC) paths and cycles in edge-coloured multigraphs. We overview some known results and prove new ones. In particular, we consider a family of transformations of an edge-coloured multigraph G into an ordinary graph that allow us to check the existence of PC cycles and PC (s,t)-paths in G and, if they exist, to find shortest ones among them. We raise a problem of finding the optimal transformation and consider a possible solution to the problem.
Gregory Gutin, Eun Jung Kim
Recognition of Antimatroidal Point Sets
Abstract
The notion of ”antimatroid with repetition” was conceived by Bjorner, Lovasz and Shor in 1991 as a multiset extension of the notion of antimatroid [2]. When the underlying set consists of only two elements, such two-dimensional antimatroids correspond to point sets in the plane. In this research we concentrate on efficient representation of antimatroidal point sets. We define a set of corner points that concisely represents a given antimatroidal point set and show how to reconstruct the antimatroidal point set from a proper set of corner points. We also present an algorithm allowing the given set of points to be recognized as a set of corner points of some antimatroidal point set.
Yulia Kempner, Vadim E. Levit
Tree Projections: Game Characterization and Computational Aspects
Abstract
The notion of tree projection provides a natural generalization for various structural decomposition methods, which have been proposed in the literature in order to single out classes of nearly-acyclic (hyper)graphs. In this paper, the mathematical properties of the notion of tree projection are surveyed, and the complexity of the basic tree projection problem (of deciding the existence of a tree projection) is pinpointed. In more details, a game-theoretic characterization (in terms of the Robber and Captain game [15] ) for tree projections is described, which yields a simple argument for the membership in NP of the tree projection problem. Eventually, the main ideas proposed in [14] and underlying the proof of NP-hardness of the tree projection problem are discussed.
Georg Gottlob, Gianluigi Greco, Zoltán Miklós, Francesco Scarcello, Thomas Schwentick
Backmatter
Metadata
Title
Graph Theory, Computational Intelligence and Thought
Editors
Marina Lipshteyn
Vadim E. Levit
Ross M. McConnell
Copyright Year
2009
Publisher
Springer Berlin Heidelberg
Electronic ISBN
978-3-642-02029-2
Print ISBN
978-3-642-02028-5
DOI
https://doi.org/10.1007/978-3-642-02029-2

Premium Partner

    Image Credits