Pursuit-Evasion on Trees by Robot Teams

We present Graph-Clear: a novel pursuit-evasion problem on graphs which models the detection of intruders in complex indoor environments by robot teams. The environment is represented by a graph, and a robot team can execute sweep and block actions on vertices and edges, respectively. A sweep action detects intruders in a vertex and represents the capability of the robot team to detect intruders in the region associated to the vertex. Similarly, a block action prevents intruders from crossing an edge and represents the capability to detect intruders as they move between regions. Both actions may require multiple robots to be executed. A strategy is a sequence of block and sweep actions to detect all intruders. When instances of Graph-Clear are being solved, the goal is to determine optimal strategies, i.e., strategies that use the least number of robots. We prove that for the general case of graphs, the problem of computation of optimal strategies is NP-hard. Next, for the special case of trees, we provide a polynomial-time algorithm. The algorithm ensures that throughout the execution of the strategy, all cleared vertices form a connected subtree, and we show that it produces optimal strategies.      

Maximal matching polytope in trees

Given a weighted simple graph, the minimum weighted maximal matching (MWMM) problem is the problem of finding a maximal matching of minimum weight. The MWMM problem is NP-hard in general, but is polynomial-time solvable in some special classes of graphs. For instance, it has been shown that the MWMM problem can be solved in linear time in trees when all the edge weights are equal to one. In this paper, we show that the convex hull of the incidence vectors of maximal matchings (the maximal matching polytope) in trees is given by the polytope described by the linear programming relaxation of a recently proposed integer programming formulation. This establishes the polynomial-time solvability of the MWMM problem in weighted trees. The question of whether or not the MWMM problem can be solved in linear time in weighted trees is open.     

The Freeze-Tag Problem: How to Wake Up a Swarm of Robots

An optimization problem that naturally arises in the study of swarm robotics is the Freeze-Tag Problem (FTP) of how to awaken a set of "asleep" robots, by having an awakened robot move to their locations. Once a robot is awake, it can assist in awakening other slumbering robots. The objective is to have all robots awake as early as possible. While the FTP bears some resemblance to problems from areas in combinatorial optimization such as routing, broadcasting, scheduling, and covering, its algorithmic characteristics are surprisingly different. We consider both scenarios on graphs and in geometric environments. In graphs, robots sleep at vertices and there is a length function on the edges. Awake robots travel along edges, with time depending on edge length. For most scenarios, we consider the offline version of the problem, in which each awake robot knows the position of all other robots. We prove that the problem is NP-hard, even for the special case of star graphs. We also establish hardness of approximation, showing that it is NP-hard to obtain an approximation factor better than 5/3, even for graphs of bounded degree. These lower bounds are complemented with several positive algorithmic results, including: · We show that the natural greedy strategy on star graphs has a tight worst-case performance of 7/3 and give a polynomial-time approximation scheme (PTAS) for star graphs. · We give a simple O(log δ)-competitive online algorithm for graphs with maximum degree δ and locally bounded edge weights. · We give a PTAS, running in nearly linear time, for geometrically embedded instances.     

Polynomial-time algorithms for weighted efficient domination problems in AT-free graphs and dually chordal graphs

An efficient dominating set (or perfect code) in a graph is a set of vertices the closed neighborhoods of which partition the vertex set of the graph. The minimum weight efficient domination problem is the problem of finding an efficient dominating set of minimum weight in a given vertex-weighted graph; the maximum weight efficient domination problem is defined similarly. We develop a framework for solving the weighted efficient domination problems based on a reduction to the maximum weight independent set problem in the square of the input graph. Using this approach, we improve on several previous results from the literature by deriving polynomial-time algorithms for the weighted efficient domination problems in the classes of dually chordal and AT-free graphs. In particular, this answers a question by Lu and Tang regarding the complexity of the minimum weight efficient domination problem in strongly chordal graphs.     

Computing minimum distortion embeddings into a path for bipartite permutation graphs and threshold graphs

The problem of computing minimum distortion embeddings of a given graph into a line (path) was introduced in 2004 and has quickly attracted significant attention with subsequent results appearing at recent stoc and soda conferences. So far, all such results concern approximation algorithms or exponential-time exact algorithms. We give the first polynomial-time algorithms for computing minimum distortion embeddings of graphs into a path when the input graphs belong to specific graph classes. In particular, we solve this problem in polynomial time for bipartite permutation graphs and threshold graphs. For both graph classes, the distortion can be arbitrarily large. The graphs that we consider are unweighted.     

Spanning Trees and the Complexity of Flood-Filling Games

We consider problems related to the combinatorial game (Free-) Flood-It, in which players aim to make a coloured graph monochromatic with the minimum possible number of flooding operations. We show that the minimum number of moves required to flood any given graph G is equal to the minimum, taken over all spanning trees T of G, of the number of moves required to flood T. This result is then applied to give two polynomial-time algorithms for flood-filling problems. Firstly, we can compute in polynomial time the minimum number of moves required to flood a graph with only a polynomial number of connected subgraphs. Secondly, given any coloured connected graph and a subset of the vertices of bounded size, the number of moves required to connect this subset can be computed in polynomial time.     

On the k-path partition of graphs

The k-path partition problem is to partition a graph into the minimum number of paths, so that none of them has length more than k, for a given positive integer k. The problem is a generalization of the Hamiltonian path problem and the problem of partitioning a graph into the minimum number of paths. The k-path partition problem remains NP-complete on the class of chordal bipartite graphs if k is part of the input, and we show that it is NP-complete on the class of comparability graphs even for k=3. On the positive side, we present a polynomial-time solution for the problem, with any k, on bipartite permutation graphs, which form a subclass of chordal bipartite graphs.     

Complexity dichotomy on partial grid recognition

Deciding whether a graph can be embedded in a grid using only unit-length edges is NP-complete, even when restricted to binary trees. However, it is not difficult to devise a number of graph classes for which the problem is polynomial, even trivial. A natural step, outstanding thus far, was to provide a broad classification of graphs that make for polynomial or NP-complete instances. We provide such a classification based on the set of allowed vertex degrees in the input graphs, yielding a full dichotomy on the complexity of the problem. As byproducts, the previous NP-completeness result for binary trees was strengthened to strictly binary trees, and the three-dimensional version of the problem was for the first time proven to be NP-complete. Our results were made possible by introducing the concepts of consistent orientations and robust gadgets, and by showing how the former allows NP-completeness proofs by local replacement even in the absence of the latter.     

Partitioning a Weighted Tree into Subtrees with?Weights in a Given Range

Assume that each vertex of a graph G is assigned a nonnegative integer weight and that l and u are given integers such that 0≤l≤u. One wishes to partition G into connected components by deleting edges from G so that the total weight of each component is at least l and at most u. Such a partition is called an (l,u)-partition. We deal with three problems to find an (l,u)-partition of a given graph: the minimum partition problem is to find an (l,u)-partition with the minimum number of components; the maximum partition problem is defined analogously; and the p-partition problem is to find an (l,u)-partition with a given number p of components. All these problems are NP-hard even for series-parallel graphs, but are solvable in linear time for paths. In this paper, we present the first polynomial-time algorithm to solve the three problems for arbitrary trees.     

Computing the metric dimension of the categorial product of some graphs

A set of vertices W is a resolving set of a graph G if every two vertices of G have distinct representations of distances with respect to the set W. The number of vertices in a smallest resolving set is called the metric dimension. This invariant has extensive applications in robotics, since the metric dimension can represent the minimum number of landmarks, which uniquely determine the position of a robot moving in a graph space. Finding the metric dimension of a graph is a non-deterministic polynomial-time hard problem. We present exact values of the metric dimension of several networks, which can be obtained as categorial products of graphs.     

Variations of the maximum leaf spanning tree problem for bipartite graphs

The maximum leaf spanning tree problem is known to be NP-complete. In [M.S. Rahman, M. Kaykobad, Complexities of some interesting problems on spanning trees, Inform. Process. Lett. 94 (2005) 93-97], a variation on this problem was posed. This variation restricts the problem to bipartite graphs and asks, for a fixed integer K, whether or not the graph contains a spanning tree with at least K leaves in one of the partite sets. We show not only that this problem is NP-complete, but that it remains NP-complete for planar bipartite graphs of maximum degree 4. We also consider a generalization of a related decision problem, which is known to be polynomial-time solvable. We show the problem is still polynomial-time solvable when generalized to weighted graphs.     

Minimum cost flows with minimum quantities

We consider a variant of the well-known minimum cost flow problem where the flow on each arc in the network is restricted to be either zero or above a given lower bound. The problem was recently shown to be weakly NP-complete even on series-parallel graphs. We start by showing that the problem is strongly NP-complete and cannot be approximated in polynomial time (unless P=NP) up to any polynomially computable function even when the graph is bipartite and the given instance is guaranteed to admit a feasible solution. Moreover, we present a pseudo-polynomial-time exact algorithm and a fully polynomial-time approximation scheme (FPTAS) for the problem on series-parallel graphs.     

Linear-time algorithms for eliminating claws in graphs

Since many -complete graph problems are polynomial-time solvable when restricted to claw-free graphs, we study the problem of determining the distance of a given graph to a claw-free graph, considering vertex elimination a measure. Claw-free Vertex Deletion (CFVD) consists of determining the minimum number of vertices to be removed from a graph such that the resulting graph is claw-free. Although CFVD is -hard in general and recognizing claw-free graphs is still a challenge, where the current best deterministic algorithm for a graph G consists of performing executions of the best algorithm for matrix multiplication, we present linear-time algorithms for CFVD on weighted block graphs and weighted graphs with bounded treewidth. Furthermore, we show that this problem on forests can be solved in linear time by a simpler algorithm, and we determine the exact values for full k-ary trees. On the other hand, we show that CFVD is -hard even when the input graph is a split graph. We also show that the problem is hard to be approximated within any constant factor better than 2, assuming the unique games conjecture.     

Causal graphs and structurally restricted planning

The causal graph is a directed graph that describes the variable dependencies present in a planning instance. A number of papers have studied the causal graph in both practical and theoretical settings. In this work, we systematically study the complexity of planning restricted by the causal graph. In particular, any set of causal graphs gives rise to a subcase of the planning problem. We give a complete classification theorem on causal graphs, showing that a set of graphs is either polynomial-time tractable, or is not polynomial-time tractable unless an established complexity-theoretic assumption fails; our theorem describes which graph sets correspond to each of the two cases. We also give a classification theorem for the case of reversible planning, and discuss the general direction of structurally restricted planning.     

Energy-optimal trajectory planning for car-like robots

When a battery-powered robot needs to operate for a long period of time, optimizing its energy consumption becomes critical. Driving motors are a major source of power consumption for mobile robots. In this paper, we study the problem of finding optimal paths and velocity profiles for car-like robots so as to minimize the energy consumed during motion. We start with an established model for energy consumption of DC motors. We first study the problem of finding the energy optimal velocity profiles, given a path for the robot. We present closed form solutions for the unconstrained case and for the case where there is a bound on maximum velocity. We then study a general problem of finding an energy optimal path along with a velocity profile, given a starting and goal position and orientation for the robot. Along the path, the instantaneous velocity of the robot may be bounded as a function of its turning radius, which in turn affects the energy consumption. Unlike minimum length paths, minimum energy paths may contain circular segments of varying radii. We show how to efficiently construct a graph which generalizes Dubins’ paths by including segments with arbitrary radii. Our algorithm uses the closed-form solution for the optimal velocity profiles as a subroutine to find the minimum energy trajectories, up to a fine discretization. We investigate the structure of energy-optimal paths and highlight instances where these paths deviate from the minimum length Dubins’ curves. In addition, we present a calibration method to find energy model parameters. Finally, we present results from experiments conducted on a custom-built robot for following optimal velocity profiles.     

Editing to Eulerian graphs

The Eulerian Editing problem asks, given a graph G and an integer k, whether G can be modified into an Eulerian graph using at most k edge additions and edge deletions. We show that this problem is polynomial-time solvable for both undirected and directed graphs. We generalize these results for problems with degree parity constraints and degree balance constraints, respectively. We also consider the variants where vertex deletions are permitted. Combined with known results, this leads to full complexity classifications for both undirected and directed graphs and for every subset of the three graph operations.     

Multi-Robot Graph Exploration and Map Building with Collision Avoidance: A Decentralized Approach

This paper proposes a decentralized multi-robot graph exploration approach in which each robot takes independent decision for efficient exploration avoiding inter-robot collision without direct communication between them. The information exchange between the robots is possible through the beacons available at visited vertices of the graph. The proposed decentralized technique guarantees completion of exploration of an unknown environment in finite number of edge traversals where graph structure of the environment is incrementally constructed. New condition for declaring completion of exploration is obtained. The paper also proposes a modification in incidence matrix so that it can be used as a data structure for information exchange. The modified incidence matrix after completion represents map of the environment. The proposed technique requires either lesser or equal number of edge traversals compared to the existing strategy for a tree exploration. A predefined constant speed change approach is proposed to address the inter-robot collision avoidance using local sensor on a robot. Simulation results verify the performance of the algorithm on various trees and graphs. Experiments with multiple robots show multi-robot exploration avoiding inter-robot collision.     

Approximation Algorithms for Treewidth

This paper presents algorithms whose input is an undirected graph, and whose output is a tree decomposition of width that approximates the optimal, the treewidth of that graph. The algorithms differ in their computation time and their approximation guarantees. The first algorithm works in polynomial-time and finds a factor-O(log OPT) approximation, where OPT is the treewidth of the graph. This is the first polynomial-time algorithm that approximates the optimal by a factor that does not depend on n, the number of nodes in the input graph. As a result, we get an algorithm for finding pathwidth within a factor of O(log OPT⋅log n) from the optimal. We also present algorithms that approximate the treewidth of a graph by constant factors of 3.66, 4, and 4.5, respectively and take time that is exponential in the treewidth. These are more efficient than previously known algorithms by an exponential factor, and are of practical interest. Finding triangulations of minimum treewidth for graphs is central to many problems in computer science. Real-world problems in artificial intelligence, VLSI design and databases are efficiently solvable if we have an efficient approximation algorithm for them. Many of those applications rely on weighted graphs. We extend our results to weighted graphs and weighted treewidth, showing similar approximation results for this more general notion. We report on experimental results confirming the effectiveness of our algorithms for large graphs associated with real-world problems.     

An optimal algorithm for solving the searchlight guarding problem on weighted two-terminal series-parallel graphs

In this paper, we consider a graph problem on a connected weighted undirected graph, called the searchlight guarding problem. Our problem is an extension of so-called graph searching/guarding problem by considering the time slot parameter in addition to the traditional building cost. Suppose that there is a fugitive who moves along the edges of the graph at any speed. We want to place a set of searchlights at the vertices to search the edges of the graph and capture the fugitive. It costs some building cost to place a searchlight at some vertex. The searchlight guarding problem is to allocate a set S of searchlights at the vertices such that the total costs of the vertices in S is minimized. If there is more than one set of searchlights with the minimum building cost, then find the one with the minimum searching time, that is, the time slots needed to capture the fugitive is the minimum. The problem is known to be NP-hard on weighted bipartite graphs, split graphs, and chordal graphs; and it is linear time solvable on weighted trees and interval graphs. In this paper, an algorithm is designed to solve the problem on weighted two-terminal series-parallel graphs. It works on the parsing tree structure of the given two-terminal series-parallel graph. The algorithm is divided into two phases. In the phase one, we first extract some useful properties of optimal solutions. Employing these properties, an algorithm is designed to find the set of searchlights with the minimum guarding cost and to assign the searching directions of all edges by the dynamic programming strategy. In the phase two, the searched time slots of all edges are determined by the breadth-first-search from the root of the parsing tree. The time complexities of both phases are linear. Thus, our algorithm is time optimal. Received: 12 March 1996 / 27 May 1997     

Anonymous graph exploration without collision by mobile robots

Considering autonomous mobile robots moving on a finite anonymous graph, this paper focuses on the Constrained Perpetual Graph Exploration problem (CPGE). That problem requires each robot to perpetually visit all the vertices of the graph, in such a way that no vertex hosts more than one robot at a time, and each edge is traversed by at most one robot at a time. The paper states an upper bound k on the number of robots that can be placed in the graph while keeping CPGE solvability. To make the impossibility result as strong as possible (no more than k robots can be initially placed in the graph), this upper bound is established under a strong assumption, namely, there is an omniscient daemon that is able to coordinate the robots movements at each round of the synchronous system. Interestingly, this upper bound is related to the topology of the graph. More precisely, the paper associates with each graph a labeled tree that captures the paths that have to be traversed by a single robot at a time (as if they were a simple edge). The length of the longest of these labeled paths reveals to be the key parameter to determine the upper bound k on the number of robots.