A comparison of two variations of a pebble game on graphs

The number of pebbles used in the black [black-white] pebble game corresponds to the storage requirement of the deterministic [non-deterministic] evaluation of a straight line program. Suppose a distinguished vertex of a directed acyclic graph can be pebbled with k pebbles in the black-white pebble game. Then it can be pebbled with k′≤1/2k(k?1)+1 pebbles in the black pebble game.     

Bandwidth and pebbling

The main results of this paper establish relationships between the bandwidth of a graphG — which is the minimum over all layouts ofG in a line of the maximum distance between images of adjacent vertices ofG — and the ease of playing various pebble games onG. Three pebble games on graphs are considered: the well-known computational pebble game, the “progressive” (i.e., no recomputation allowed) version of the computational pebble game, both of which are played on directed acyclic graphs, and the quite different “breadth-first” pebble game, that is played on undirected graphs. We consider two costs of a play of a pebble game: the minimum number of pebbles needed to play the game on the graphG, and the maximumlifetime of any pebble in the game, i.e., the maximum number of moves that any pebble spends on the graph. The first set of results of the paper prove that the minimum lifetime cost of a play of either of the second two pebble games on a graphG is precisely the bandwidth ofG. The second set of results establish bounds on the pebble demand of all three pebble games in terms of the bandwidth of the graph being pebbled; for instance, the number of pebbles needed to pebble a graphG of bandwidthk is at most min (2k ²+k+1, 2k log₂|G|); and, in addition, there are bandwidth-k graphs that require 3k?1 pebbles. The third set of results relate the difficulty of deciding the cost of playing a pebble game on a given input graphG to the bandwidth ofG; for instance, the Pebble Demand problem forn-vertex graphs of bandwidthf(n) is in the class NSPACE (f(n) log² n); and the Optimal Lifetime Problem for either of the second two pebble games is NP-complete.     

Partitioning Planar Graphs with Vertex Costs: Algorithms and Applications

We prove separator theorems in which the size of the separator is minimized with respect to non-negative vertex costs. We show that for any planar graph G there exists a vertex separator of total sum of vertex costs at most and that this bound is optimal to within a constant factor. Moreover, such a separator can be found in linear time. This theorem implies a variety of other separation results. We describe applications of our separator theorems to graph embedding problems, to graph pebbling, and to multicommodity flow problems. Received June 1997; revised February 1999.     

On a game in directed graphs

Inspired by recent algorithms for electing a leader in a distributed system, we study the following game in a directed graph: each vertex selects one of its outgoing arcs (if any) and eliminates the other endpoint of this arc; the remaining vertices play on until no arcs remain. We call a directed graph lethal if the game must end with all vertices eliminated and mortal if it is possible that the game ends with all vertices eliminated. We show that lethal graphs are precisely collections of vertex-disjoint cycles, and that the problem of deciding whether or not a given directed graph is mortal is NP-complete (and hence it is likely that no “nice” characterization of mortal graphs exists).     

Pebble games for studying storage sharing

Pebble games are played on a directed acyclic graph (dag). Placing a pebble on a vertex may be thought of as entering the value of the subexpression represented by the vertex into accessible storage. In some applications, there are types associated with vertices e.g. some vertices may represent functions, others may represent function values. We are interested in determining if vertices of the same type can share storage. The problem considered is as follows. We are given a labelled dag to be pebbled. A pebble may be placed on a vertex if all sons of the vertex have pebbles—in fact it is legal to move a pebble from a son to a father. Pebbles may be picked up at any time. The objective is to pebble each vertex exactly once. We will be interested in ‘one pebblings of l vertices’ in which there is at most one pebble on vertices with label l, at all times; and ‘stack pebblings of l vertices’ in which the pebbled vertices with label l are along a path, at all times. Results about the existence of such pebblings are presented. The results have applications to testing serializability of database updates, and potential applications to semantics directed compiler generation.     

Cleaning a network with brushes

Following the decontamination metaphor for searching a graph, we introduce a cleaning process, which is related to both the chip-firing game and edge searching. Brushes (instead of chips) are placed on some vertices and, initially, all the edges are dirty. When a vertex is ‘fired’, each dirty incident edge is traversed by only one brush, cleaning it, but a brush is not allowed to traverse an already cleaned edge; consequently, a vertex may not need degree-many brushes to fire. The model presented is one where the edges are continually recontaminated, say by algae, so that cleaning is regarded as an on-going process. Ideally, the final configuration of the brushes, after all the edges have been cleaned, should be a viable starting configuration to clean the graph again. We show that this is possible with the least number of brushes if the vertices are fired sequentially but not if fired in parallel. We also present bounds for the least number of brushes required to clean graphs in general and some specific families of graphs.     

Maximum Weight Independent Sets in hole- and co-chair-free graphs

The Maximum Weight Independent Set (MWIS) problem on graphs with vertex weights asks for a set of pairwise nonadjacent vertices of maximum total weight. Being one of the most investigated and most important problems on graphs, it is well known to be $\mathbb{NP}$-complete and hard to approximate. The complexity of MWIS is open for hole-free graphs (i.e., graphs without induced subgraphs isomorphic to a chordless cycle of length at least five). By applying a combination of clique separator and modular decomposition, we obtain a polynomial time solution of MWIS for hole- and co-chair-free graphs (the co-chair consists of five vertices four of which form a clique minus one edge – a diamond – and the fifth has degree one and is adjacent to one of the degree two vertices of the diamond).     

Multi-Color Pebble Motion on Graphs

We consider a graph with n vertices, and p<n pebbles of m colors. A pebble move consists of transferring a pebble from its current host vertex to an adjacent unoccupied vertex. The problem is to move the pebbles to a given new color arrangement.     

Szegedy’s quantum walk with queries

When searching for a marked vertex in a graph, Szegedy’s usual search operator is defined by using the transition probability matrix of the random walk with absorbing barriers at the marked vertices. Instead of using this operator, we analyze searching with Szegedy’s quantum walk by using reflections around the marked vertices, that is, the standard form of quantum query. We show we can boost the probability to 1 of finding a marked vertex in the complete graph. Numerical simulations suggest that the success probability can be improved for other graphs, like the two-dimensional grid. We also prove that, for a certain class of graphs, we can express Szegedy’s search operator, obtained from the absorbing walk, using the standard query model.     

A Tight Lower Bound for a Special Case of Quadratic 0–1 Programming

We consider a still NP-complete partial case of the unconstrained binary quadratic optimization problem that can be described in terms of an undirected graph with red edges having negative weights and green edges having positive weights. The maximum vertex degree of the graph is three. It can be assumed w.l.o.g. that every vertex is incident to a red and a green edge. We are looking for a vertex cover with respect to the red edges which covers a subset of green edges of total weight as small as possible. We prove that for all connected such graphs except a subclass of special graphs having exactly five green edges it is possible to find a vertex cover with respect to the red edges for which the total weight of uncovered green edges is at least 1/4 fraction of the total weight of all green edges.     

Least Squares Vertex Baking

We investigate the representation of signals defined on triangle meshes using linearly interpolated vertex attributes. Compared to texture mapping, storing data only at vertices yields significantly lower memory overhead and less expensive runtime reconstruction. However, standard approaches to determine vertex values such as point sampling or averaging triangle samples lead to suboptimal approximations. We discuss how an optimal solution can be efficiently calculated using continuous least‐squares. In addition, we propose a regularization term that allows us to minimize gradient discontinuities and mach banding artifacts while staying close to the optimum. Our method has been integrated in a game production lighting tool and we present examples of representing signals such as ambient occlusion and precomputed radiance transfer in real game scenes, where vertex baking was used to free up resources for other game components.     

Robust self-assembly of graphs

Self-assembly is a process in which small building blocks interact autonomously to form larger structures. A recently studied model of self-assembly is the Accretive Graph Assembly Model whereby an edge-weighted graph is assembled one vertex at a time starting from a designated seed vertex. The weight of an edge specifies the magnitude of attraction (positive weight) or repulsion (negative weight) between adjacent vertices. It is feasible to add a vertex to the assembly if the total attraction minus repulsion of the already built neighbors exceeds a certain threshold, called the assembly temperature. This model naturally generalizes the extensively studied Tile Assembly Model. A natural question in graph self-assembly is to determine whether or not there exists a sequence of feasible vertex additions to realize the entire graph. However, even when it is feasible to realize the assembly, not much can be inferred about its likelihood of realization in practice due to the uncontrolled nature of the self-assembly process. Motivated by this, we introduce the robust self-assembly problem where the goal is to determine if every possible sequence of feasible vertex additions leads to the completion of the assembly. We show that the robust self-assembly problem is co-NP-complete even on planar graphs with two distinct edge weights. We then examine the tractability of the robust self-assembly problem on a natural subclass of planar graphs, namely grid graphs. We identify structural conditions that determine whether or not a grid graph can be robustly self-assembled, and give poly-time algorithms to determine this for several interesting cases of the problem. Finally, we also show that the problem of counting the number of feasible orderings that lead to the completion of an assembly is #P-complete.     

Exponential Speedup of Fixed-Parameter Algorithms for Classes of Graphs Excluding Single-Crossing Graphs as Minors

We present a fixed-parameter algorithm that constructively solves the $k$-dominating set problem on any class of graphs excluding a single-crossing graph (a graph that can be drawn in the plane with at most one crossing) as a minor in $O(4^{9.55\sqrt{k}}n^{O(1)})$ time. Examples of such graph classes are the $K_{3,3}$-minor-free graphs and the $K_{5}$-minor-free graphs. As a consequence, we extend our results to several other problems such as vertex cover, edge dominating set, independent set, clique-transversal set, kernels in digraphs, feedback vertex set, and a collection of vertex-removal problems. Our work generalizes and extends the recent results of exponential speedup in designing fixed-parameter algorithms on planar graphs due to Alber et al. to other (nonplanar) classes of graphs.     

A distributed low tree-depth decomposition algorithm for bounded expansion classes

We study the distributed low tree-depth decomposition problem for graphs restricted to a bounded expansion class. Low tree-depth decomposition have been introduced in 2006 and have found quite a few applications. For example it yields a linear-time model checking algorithm for graphs in a bounded expansion class. Recall that bounded expansion classes cover classes of graphs of bounded degree, of planar graphs, of graphs of bounded genus, of graphs of bounded treewidth, of graphs that exclude a fixed minor, and many other graphs. There is a sequential algorithm to compute low tree-depth decomposition (with bounded number of colors) in linear time. In this paper, we give the first efficient distributed algorithm for this problem. As it is usual for a symmetry breaking problem, we consider a synchronous model, and as we are interested in a deterministic algorithm, we use the usual assumption that each vertex has a distinct identity number. We consider the distributed message-passing \(\mathcal {CONGEST}_\mathrm{BC}\) model, in which messages have logarithmic length and only local broadcast are allowed. In this model, we present a logarithmic time distributed algorithm for computing a low tree-depth decomposition of graphs in a fixed bounded expansion class. In the sequential centralized case low tree-depth decomposition linear time algorithm are used as a core procedure in several non-trivial linear time algorithms. We believe that, similarly, low tree-depth decomposition could be at the heart of several non-trivial logarithmic time algorithms.     

Multi‐Scale Geometry Interpolation

Interpolating vertex positions among triangle meshes with identical vertex‐edge graphs is a fundamental part of many geometric modelling systems. Linear vertex interpolation is robust but fails to preserve local shape. Most recent approaches identify local affine transformations for parts of the mesh, model desired interpolations of the affine transformations, and then optimize vertex positions to conform with the desired transformations. However, the local interpolation of the rotational part is non‐trivial for more than two input configurations and ambiguous if the meshes are deformed significantly. We propose a solution to the vertex interpolation problem that starts from interpolating the local metric (edge lengths) and mean curvature (dihedral angles) and makes consistent choices of local affine transformations using shape matching applied to successively larger parts of the mesh. The local interpolation can be applied to any number of input vertex configurations and due to the hierarchical scheme for generating consolidated vertex positions, the approach is fast and can be applied to very large meshes.     

A parametric filtering algorithm for the graph isomorphism problem

We introduce a new filtering algorithm, called IDL(d)-filtering, for a global constraint dedicated to the graph isomorphism problem—the goal of which is to decide if two given graphs have an identical structure. The basic idea of IDL(d)-filtering is to label every vertex with respect to its relationships with other vertices around it in the graph, and to use these labels to filter domains by removing values that have different labels. IDL(d)-filtering is parameterized by a positive integer value d which gives a limit on the distance between a vertex to be labelled and the set of vertices considered to build its label. We experimentally compare different instantiations of IDL(d)-filtering with state-of-the-art dedicated algorithms and show that IDL(d)-filtering is more efficient on regular sparse graphs and competitive on other kinds of graphs.     

Capacitated Domination Problem

We consider a generalization of the well-known domination problem on graphs. The (soft) capacitated domination problem with demand constraints is to find a dominating set D of minimum cardinality satisfying both the capacity and demand constraints. The capacity constraint specifies that each vertex has a capacity that it can use to meet the demands of dominated vertices in its closed neighborhood, and the number of copies of each vertex allowed in D is unbounded. The demand constraint specifies the demand of each vertex in V to be met by the capacities of vertices in D dominating it. In this paper, we study the capacitated domination problem on trees from an algorithmic point of view. We present a linear time algorithm for the unsplittable demand model, and a pseudo-polynomial time algorithm for the splittable demand model. In addition, we show that the capacitated domination problem on trees with splittable demand constraints is NP-complete (even for its integer version) and provide a polynomial time approximation scheme (PTAS). We also give a primal-dual approximation algorithm for the weighted capacitated domination problem with splittable demand constraints on general graphs.     

Path relinking for the vertex separator problem

This paper presents the first population-based path relinking algorithm for solving the NP-hard vertex separator problem in graphs. The proposed algorithm employs a dedicated relinking procedure to generate intermediate solutions between an initiating solution and a guiding solution taken from a reference set of elite solutions (population) and uses a fast tabu search procedure to improve some selected intermediate solutions. Special care is taken to ensure the diversity of the reference set. Dedicated data structures based on bucket sorting are employed to ensure a high computational efficiency. The proposed algorithm is assessed on four sets of 365 benchmark instances with up to 20,000 vertices, and shows highly comparative results compared to the state-of-the-art methods in the literature. Specifically, we report improved best solutions (new upper bounds) for 67 instances which can serve as reference values for assessment of other algorithms for the problem.     

k-tuple domination in graphs

In a graph G, a vertex is said to dominate itself and all of its neighbors. For a fixed positive integer k, the k-tuple domination problem is to find a minimum sized vertex subset in a graph such that every vertex in the graph is dominated by at least k vertices in this set. The current paper studies k-tuple domination in graphs from an algorithmic point of view. In particular, we give a linear-time algorithm for the k-tuple domination problem in strongly chordal graphs, which is a subclass of chordal graphs and includes trees, block graphs, interval graphs and directed path graphs. We also prove that the k-tuple domination problem is NP-complete for split graphs (a subclass of chordal graphs) and for bipartite graphs.     

Single-edge monotonic sequences of graphs and linear-time algorithms for minimal completions and deletions

We study graph properties that admit an increasing, or equivalently decreasing, sequence of graphs on the same vertex set such that for any two consecutive graphs in the sequence their difference is a single edge. This is useful for characterizing and computing minimal completions and deletions of arbitrary graphs into having these properties. We prove that threshold graphs and chain graphs admit such sequences. Based on this characterization and other structural properties, we present linear-time algorithms both for computing minimal completions and deletions into threshold, chain, and bipartite graphs, and for extracting a minimal completion or deletion from a given completion or deletion. Minimum completions and deletions into these classes are NP-hard to compute.