Computing minimal doubly resolving sets of graphs

In this paper we consider the minimal doubly resolving sets problem (MDRSP) of graphs. We prove that the problem is NP-hard and give its integer linear programming formulation. The problem is solved by a genetic algorithm (GA) that uses binary encoding and standard genetic operators adapted to the problem. Experimental results include three sets of ORLIB test instances: crew scheduling, pseudo-boolean and graph coloring. GA is also tested on theoretically challenging large-scale instances of hypercubes and Hamming graphs. Optimality of GA solutions on smaller size instances has been verified by total enumeration. For several larger instances optimality follows from the existing theoretical results. The GA results for MDRSP of hypercubes are used by a dynamic programming approach to obtain upper bounds for the metric dimension of large hypercubes up to 2⁹⁰$2^{90}$ nodes, that cannot be directly handled by the computer.     

Dominating sets in directed graphs

We consider the problem of incrementally computing a minimal dominating set of a directed graph after the insertion or deletion of a set of arcs. Earlier results have either focused on the study of the properties that minimum (not minimal) dominating sets preserved or lacked to investigate which update affects a minimal dominating set and in what ways. In this paper, we first show how to incrementally compute a minimal dominating set on arc insertions. We then reduce the case of computing a minimal dominating set on arc deletions to the case of insertions. Some properties on minimal dominating sets are provided to support the incremental strategy. Lastly, we give a new bound on the size of minimum dominating sets based on those results.     

Minimum feedback vertex sets in cocomparability graphs and convex bipartite graphs

Polynomial-time algorithms for the feedback vertex set problem in cocomparability graphs and convex bipartite graphs are presented. Received September 14, 1994 / January 18, 1996     

Feedback vertex sets in star graphs

In a graph G=(V,E), a subset F⊂V(G) is a feedback vertex set of G if the subgraph induced by V(G)?F is acyclic. In this paper, we propose an algorithm for finding a small feedback vertex set of a star graph. Indeed, our algorithm can derive an upper bound to the size of the feedback vertex set for star graphs. Also by applying the properties of regular graphs, a lower bound can easily be achieved for star graphs.     

Computing bond orders in molecule graphs

In this paper, we deal with restoring missing information in molecule databases: Many data formats only store the atoms’ configuration but omit bond multiplicities. As this information is essential for various applications in chemistry, we consider the problem of recovering bond type information using a scoring function for the possible valences of each atom—the Bond Order Assignment problem. We show that the Bond Order Assignment is NP-hard, and its maximization version is MAX SNP-hard. We then give two exact fixed-parameter algorithms for the problem, where bond orders are computed via dynamic programming on a tree decomposition of the molecule graph. We evaluate our algorithm on a set of real molecule graphs and find that it works fast in practice.     

Computing with graphs and graph transformations

Many software applications require the construction and manipulation of graphs. In standard programming languages, this is accomplished using low‐level mechanisms such as pointer manipulation or array indexing. In contrast, graph productions are a convenient high‐level visual notation for coding graph modifications. A graph production replaces one subgraph by another subgraph. Graph productions can define a graph grammar and graph language, or can directly transform an input graph into an output graph. Graph transformation has been applied in many areas, including the definition of visual languages and their tools, the construction of software development environments, the definition of constraint programming algorithms, the modeling of distributed systems, and the construction of neural networks. One application is presented in detail: the interpretation of mathematical notation in scanned document images. The graph models the set of mathematical symbols, and their spatial and logical relationships. This graph is transformed by productions written in the PROGRES language. Copyright © 1999 John Wiley & Sons, Ltd.     

Large independent sets in random regular graphs

We present algorithmic lower bounds on the size _sd$s_d$ of the largest independent sets of vertices in random d$d$-regular graphs, for each fixed d≥3$d\ge 3$. For instance, for d=3$d=3$ we prove that, for graphs on n$n$ vertices, _sd≥0.43475n$s_d\ge 0.43475n$ with probability approaching one as n$n$ tends to infinity.     

Finding hidden independent sets in interval graphs

We design efficient competitive algorithms for discovering hidden information using few queries. Specifically, consider a game in a given set of intervals (and their implied interval graph G) in which our goal is to discover an (unknown) independent set X by making the fewest queries of the form “Is point p covered by an interval in X?” Our interest in this problem stems from two applications: experimental gene discovery with PCR technology and the game of Battleship (in a 1-dimensional setting). We provide adaptive algorithms for both the verification scenario (given an independent set, is it X?) and the discovery scenario (find X without any information). Under some assumptions, these algorithms use an asymptotically optimal number of queries in every instance.     

On disjoint maximal independent sets in graphs

An old problem in graph theory is to characterize the graphs that admit two disjoint maximal independent sets.     

Connecting face hitting sets in planar graphs

We show that any face hitting set of size n of a connected planar graph with a minimum degree of at least 3 is contained in a connected subgraph of size 5n−6. Furthermore we show that this bound is tight by providing a lower bound in the form of a family of graphs. This improves the previously known upper and lower bound of 11n−18 and 3n respectively by Grigoriev and Sitters. Our proof is valid for simple graphs with loops and generalizes to graphs embedded in surfaces of arbitrary genus.     

Computing relative neighbourhood graphs in the plane

The relative neighbourhood graph (RNG) of a set of N points connects the relative neighbours, i.e. a pair of points is connected by an edge if those points are at least as close to each other as to any other point. The paper presents two new algorithms for constructing RNG in two-dimensional Euclidean space. The method is to determine a supergraph for RNG which can then be thinned efficiently from the extra edges. The first algorithm is simple, and works in O(N²) time. The worst case running time of the second algorithm is also O(N²), but its average case running time is O(N) for points from a homogeneous planar Poisson point process. Experimental tests have shown the usefulness of the approach.     

Computing invariants in graphs of small bandwidth

Many graph invariants (chromatic number, rook polynomial, Tutte polynomial, etc.) are known to be computable for general graphs in exponential time only. Algorithms for their computation usually depend on special properties of the invariants and are not extendable to slightly different problems.Some general framework (called composition method) for the construction of algorithms for the solution graph of related problems has been developed during the last two years. In this paper we will demonstrate the power of this method by automating and applying it to a class of well-known problems covering e.g. the chromatic and the Tutte polynomial. The obtained algorithms are comparable to existing hand optimized ones in running time and memory usage.     

Counting maximal independent sets in directed path graphs

The problem of counting maximal independent sets is #P-complete for chordal graphs but solvable in polynomial time for its subclass of interval graphs. This work improves upon both of these results by showing that the problem remains #P-complete when restricted to directed path graphs but that a further restriction to rooted directed path graphs admits a polynomial time solution.