Linear-Time Recognition of Circular-Arc Graphs

A graph G is a circular-arc graph if it is the intersection graph of a set of arcs on a circle. That is, there is one arc for each vertex of G, and two vertices are adjacent in G if and only if the corresponding arcs intersect. We give a linear-time algorithm for recognizing this class of graphs. When G is a member of the class, the algorithm gives a certificate in the form of a set of arcs that realize it.     

Improved Algorithms and Complexity Results for Power Domination in Graphs

The NP-complete Power Dominating Set problem is an “electric power networks variant” of the classical domination problem in graphs: Given an undirected graph G=(V,E), find a minimum-size set P?V such that all vertices in V are “observed” by the vertices in P. Herein, a vertex observes itself and all its neighbors, and if an observed vertex has all but one of its neighbors observed, then the remaining neighbor becomes observed as well. We show that Power Dominating Set can be solved by “bounded-treewidth dynamic programs.” For treewidth being upper-bounded by a constant, we achieve a linear-time algorithm. In particular, we present a simplified linear-time algorithm for Power Dominating Set in trees. Moreover, we simplify and extend several NP-completeness results, particularly showing that Power Dominating Set remains NP-complete for planar graphs, for circle graphs, and for split graphs. Specifically, our improved reductions imply that Power Dominating Set parameterized by |P| is W[2]-hard and it cannot be better approximated than Dominating Set.     

A Simpler Linear-Time Recognition of Circular-Arc Graphs

We give a linear-time recognition algorithm for circular-arc graphs based on the algorithm of Eschen and Spinrad (Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 128–137, 1993) and Eschen (PhD thesis, 1997). Our algorithm both improves the time bound of Eschen and Spinrad, and fixes some flaws in it. Our algorithm is simpler than the earlier linear-time recognition algorithm of McConnell (Algorithmica 37(2):93–147, 2003), which is the only linear time recognition algorithm previously known.     

Parameterized Domination in Circle Graphs

A circle graph is the intersection graph of a set of chords in a circle. Keil [Discrete Appl. Math., 42(1):51–63, 1993] proved that Dominating Set, Connected Dominating Set, and Total Dominating Set are NP-complete in circle graphs. To the best of our knowledge, nothing was known about the parameterized complexity of these problems in circle graphs. In this paper we prove the following results, which contribute in this direction:

• Dominating Set, Independent Dominating Set, Connected Dominating Set, Total Dominating Set, and Acyclic Dominating Set are W[1]-hard in circle graphs, parameterized by the size of the solution.
• Whereas both Connected Dominating Set and Acyclic Dominating Set are W[1]-hard in circle graphs, it turns out that Connected Acyclic Dominating Set is polynomial-time solvable in circle graphs.
• If T is a given tree, deciding whether a circle graph G has a dominating set inducing a graph isomorphic to T is NP-complete when T is in the input, and FPT when parameterized by t=|V(T)|. We prove that the FPT algorithm runs in subexponential time, namely $2^{\mathcal{O}(t \cdot\frac{\log\log t}{\log t})} \cdot n^{\mathcal{O}(1)}$ , where n=|V(G)|.

     

Linear-Time Recognition of Helly Circular-Arc Models and Graphs

A circular-arc model ℳ is a circle C together with a collection A\mathcal{A} of arcs of C. If A\mathcal{A} satisfies the Helly Property then ℳ is a Helly circular-arc model. A (Helly) circular-arc graph is the intersection graph of a (Helly) circular-arc model. Circular-arc graphs and their subclasses have been the object of a great deal of attention in the literature. Linear-time recognition algorithms have been described both for the general class and for some of its subclasses. However, for Helly circular-arc graphs, the best recognition algorithm is that by Gavril, whose complexity is O(n ³). In this article, we describe different characterizations for Helly circular-arc graphs, including a characterization by forbidden induced subgraphs for the class. The characterizations lead to a linear-time recognition algorithm for recognizing graphs of this class. The algorithm also produces certificates for a negative answer, by exhibiting a forbidden subgraph of it, within this same bound.     

A Linear-Time Algorithm for Finding Locally Connected Spanning Trees on Circular-Arc Graphs

Suppose that T is a spanning tree of a graph G. T is called a locally connected spanning tree of G if for every vertex of T, the set of all its neighbors in T induces a connected subgraph of G. In this paper, given an intersection model of a circular-arc graph, an O(n)-time algorithm is proposed that can determine whether the circular-arc graph contains a locally connected spanning tree or not, and produce one if it exists.     

The Kernelization Complexity of Connected Domination in Graphs with (no) Small Cycles

In the Parameterized Connected Dominating Set problem the input consists of a graph G and a positive integer k, and the question is whether there is a set S of at most k vertices in G—a connected dominating set of G—such that (i) S is a dominating set of G, and (ii) the subgraph G[S] induced by S is connected; the parameter is k. The underlying decision problem is a basic connectivity problem which is long known to be NP-complete, and it has been extensively studied using several algorithmic approaches. Parameterized Connected Dominating Set is W[2]-hard, and therefore it is unlikely (Downey and Fellows, Parameterized Complexity, Springer, 1999) that the problem has fixed-parameter tractable (FPT) algorithms or polynomial kernels in graphs in general. We investigate the effect of excluding short cycles, as subgraphs, on the kernelization complexity of Parameterized Connected Dominating Set. The girth of a graph G is the length of a shortest cycle in G. It turns out that the Parameterized Connected Dominating Set problem is hard on graphs with small cycles, and becomes progressively easier as the girth increases. More precisely, we obtain the following kernelization landscape: Parameterized Connected Dominating Set

• does not have a kernel of any size on graphs of girth three or four (since the problem is W[2]-hard);
• admits a kernel of size 2 ^k k ^3k on graphs of girth at least five;
• has no polynomial kernel (unless the Polynomial Hierarchy collapses to the third level) on graphs of girth at most six, and,
• has a cubic ( $\mathcal {O}(k^{3})$ ) vertex kernel on graphs of girth at least seven.

While there is a large and growing collection of parameterized complexity results available for problems on graph classes characterized by excluded minors, our results add to the very few known in the field for graph classes characterized by excluded subgraphs.     

On the Power of Non-adaptive Learning Graphs

We introduce a notion of the quantum query complexity of a certificate structure. This is a formalization of a well-known observation that many quantum query algorithms only require the knowledge of the position of possible certificates in the input string, not the precise values therein. Next, we derive a dual formulation of the complexity of a non-adaptive learning graph and use it to show that non-adaptive learning graphs are tight for all certificate structures. By this, we mean that there exists a function possessing the certificate structure such that a learning graph gives an optimal quantum query algorithm for it. For a special case of certificate structures generated by certificates of bounded size, we construct a relatively general class of functions having this property. The construction is based on orthogonal arrays and generalizes the quantum query lower bound for the k-sum problem derived recently by Belovs and ?palek (Proceeding of 4th ACM ITCS, 323–328, 2013). Finally, we use these results to show that the learning graph for the triangle problem by Lee et al. (Proceeding of 24th ACM-SIAM SODA, 1486–1502, 2013) is almost optimal in the above settings. This also gives a quantum query lower bound for the triangle sum problem.     

Domination in quadrangle-free helly graphs

In memory of Martin Farber     

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.     

Recognizing d-Interval Graphs and d-Track Interval Graphs

A d-interval is the union of d disjoint intervals on the real line. A d-track interval is the union of d disjoint intervals on d disjoint parallel lines called tracks, one interval on each track. As generalizations of the ubiquitous interval graphs, d-interval graphs and d-track interval graphs have wide applications, traditionally to scheduling and resource allocation, and more recently to bioinformatics. In this paper, we prove that recognizing d-track interval graphs is NP-complete for any constant d≥2. This confirms a conjecture of Gyárfás and West in 1995. Previously only the complexity of the case d=2 was known. Our proof in fact implies that several restricted variants of this graph recognition problem, i.e., recognizing balanced d-track interval graphs, unit d-track interval graphs, and (2,…,2) d-track interval graphs, are all NP-complete. This partially answers another question recently raised by Gambette and Vialette. We also prove that recognizing depth-two 2-track interval graphs is NP-complete, even for the unit case. In sharp contrast, we present a simple linear-time algorithm for recognizing depth-two unit d-interval graphs. These and other results of ours give partial answers to a question of West and Shmoys in 1984 and a similar question of Gyárfás and West in 1995. Finally, we give the first bounds on the track number and the unit track number of a graph in terms of the number of vertices, the number of edges, and the maximum degree, and link the two numbers to the classical concepts of arboricity.     

Deterministic Rendezvous in Graphs

Two mobile agents having distinct identifiers and located in nodes of an unknown anonymous connected graph, have to meet at some node of the graph. We seek fast deterministic algorithms for this rendezvous problem, under two scenarios: simultaneous startup, when both agents start executing the algorithm at the same time, and arbitrary startup, when starting times of the agents are arbitrarily decided by an adversary. The measure of performance of a rendezvous algorithm is its cost: for a given initial location of agents in a graph, this is the number of steps since the startup of the later agent until rendezvous is achieved. We first show that rendezvous can be completed at cost O(n + log l) on any n-node tree, where l is the smaller of the two identifiers, even with arbitrary startup. This complexity of the cost cannot be improved for some trees, even with simultaneous startup. Efficient rendezvous in trees relies on fast network exploration and cannot be used when the graph contains cycles. We further study the simplest such network, i.e., the ring. We prove that, with simultaneous startup, optimal cost of rendezvous on any ring is Θ(D log l), where D is the initial distance between agents. We also establish bounds on rendezvous cost in rings with arbitrary startup. For arbitrary connected graphs, our main contribution is a deterministic rendezvous algorithm with cost polynomial in n, τ and log l, where τ is the difference between startup times of the agents. We also show a lower bound Ω (n²) on the cost of rendezvous in some family of graphs. If simultaneous startup is assumed, we construct a generic rendezvous algorithm, working for all connected graphs, which is optimal for the class of graphs of bounded degree, if the initial distance between agents is bounded.     

Edge-Packing in Planar Graphs

Maximum G Edge-Packing (EPack _G ) is the problem of finding the maximum number of edge-disjoint isomorphic copies of a fixed guest graph G in a host graph H . This paper investigates the computational complexity of edge-packing for planar guests and planar hosts. Edge-packing is solvable in polynomial time when both G and H are trees. Edge-packing is solvable in linear time when H is outerplanar and G is either a 3-cycle or a k -star (a graph isomorphic to K _1,k ). Edge-packing is NP-complete when H is planar and G is either a cycle or a tree with edges. A strategy for developing polynomial-time approximation algorithms for planar hosts is exemplified by a linear-time approximation algorithm that finds a k -star edge-packing of size at least half the optimal. Received May 1995, and in revised form November 1995, and in final form December 1997.     

TSP Heuristics: Domination Analysis and Complexity

   Abstract. We show that the 2-Opt and 3-Opt heuristics for the traveling salesman problem (TSP) on the complete graph K _n produce a solution no worse than the average cost of a tour in K _n in a polynomial number of iterations. As a consequence, we get that the domination numbers of the 2- Opt , 3- Opt , Carlier—Villon, Shortest Path Ejection Chain, and Lin—Kernighan heuristics are all at least (n-2)! / 2 . The domination number of the Christofides heuristic is shown to be no more than

TSP Heuristics: Domination Analysis and Complexity

We show that the 2-Opt and 3-Opt heuristics for the traveling salesman problem (TSP) on the complete graph Kn produce a solution no worse than the average cost of a tour in Kn in a polynomial number of iterations. As a consequence, we get that the domination numbers of the 2- Opt , 3- Opt , Carlier—Villon, Shortest Path Ejection Chain, and Lin—Kernighan heuristics are all at least (n-2)! / 2 . The domination number of the Christofides heuristic is shown to be no more than $\lceil{n}/{2}\rceil !$ , and for the Double Tree heuristic and a variation of the Christofides heuristic the domination numbers are shown to be one (even if the edge costs satisfy the triangle inequality). Further, unless P = NP, no polynomial time approximation algorithm exists for the TSP on the complete digraph $\vec{K}_n$ with domination number at least (n-1)!-k for any constant k or with domination number at least (n-1)! - (( k /(k+1))(n+r))!-1 for any non-negative constants r and k such that (n+r) $\equiv$ 0 mod (k+1). The complexities of finding the median value of costs of all the tours in $\vec{K}_n$ and of similar problems are also studied.     

Straight-Line Drawing Algorithms for Hierarchical Graphs and Clustered Graphs

Hierarchical graphs and clustered graphs are useful non-classical graph models for structured relational information. Hierarchical graphs are graphs with layering structures; clustered graphs are graphs with recursive clustering structures. Both have applications in CASE tools, software visualization and VLSI design. Drawing algorithms for hierarchical graphs have been well investigated. However, the problem of planar straight-line representation has not been solved completely. In this paper we answer the question: does every planar hierarchical graph admit a planar straight-line hierarchical drawing? We present an algorithm that constructs such drawings in linear time. Also, we answer a basic question for clustered graphs, that is, does every planar clustered graph admit a planar straight-line drawing with clusters drawn as convex polygons? We provide a method for such drawings based on our algorithm for hierarchical graphs.     

Tree Spanners for Bipartite Graphs and Probe Interval Graphs

A tree t-spanner T in a graph G is a spanning tree of G such that the distance between every pair of vertices in T is at most t times their distance in G. The tree t-spanner problem asks whether a graph admits a tree t-spanner, given t. We first substantially strengthen the known results for bipartite graphs. We prove that the tree t-spanner problem is NP-complete even for chordal bipartite graphs for t ≥ 5, and every bipartite ATE-free graph has a tree 3-spanner, which can be found in linear time. The previous best known results were NP-completeness for general bipartite graphs, and that every convex graph has a tree 3-spanner. We next focus on the tree t-spanner problem for probe interval graphs and related graph classes. The graph classes were introduced to deal with the physical mapping of DNA. From a graph theoretical point of view, the classes are natural generalizations of interval graphs. We show that these classes are tree 7-spanner admissible, and a tree 7-spanner can be constructed in (m log n) time.