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.     

Constant factor approximation algorithms for the densest k-subgraph problem on proper interval graphs and bipartite permutation graphs

The densest k-subgraph problem asks for a k-vertex subgraph with the maximum number of edges. This problem is NP-hard on bipartite graphs, chordal graphs, and planar graphs. A 3-approximation algorithm is known for chordal graphs. We present -approximation algorithms for proper interval graphs and bipartite permutation graphs. The latter result relies on a new characterisation of bipartite permutation graphs which may be of independent interest.     

Maximum Induced Matchings for Chordal Graphs in Linear Time

The Maximum Induced Matching (MIM) Problem asks for a largest set of pairwise vertex-disjoint edges in a graph which are pairwise of distance at least two. It is well-known that the MIM problem is NP-complete even on particular bipartite graphs and on line graphs. On the other hand, it is solvable in polynomial time for various classes of graphs (such as chordal, weakly chordal, interval, circular-arc graphs and others) since the MIM problem on graph G corresponds to the Maximum Independent Set problem on the square G ^*=L(G)² of the line graph L(G) of G, and in some cases, G ^* is in the same graph class; for example, for chordal graphs G, G ^* is chordal. The construction of G ^*, however, requires time, where m is the number of edges in G. Is has been an open problem whether there is a linear-time algorithm for the MIM problem on chordal graphs. We give such an algorithm which is based on perfect elimination order and LexBFS.     

On the k-path cover problem for cacti

In this paper we investigate the k-path cover problem for graphs, which is to find the minimum number of vertex disjoint k-paths that cover all the vertices of a graph. The k-path cover problem for general graphs is NP-complete. Though notable applications of this problem to database design, network, VLSI design, ring protocols, and code optimization, efficient algorithms are known for only few special classes of graphs. In order to solve this problem for cacti, i.e., graphs where no edge lies on more than one cycle, we introduce the so-called Steiner version of the k-path cover problem, and develop an efficient algorithm for the Steiner k-path cover problem for cacti, which finds an optimal k-path cover for a given cactus in polynomial time.     

Detecting Fixed Patterns in Chordal Graphs in Polynomial Time

The Contractibility problem takes as input two graphs G and H, and the task is to decide whether H can be obtained from G by a sequence of edge contractions. The Induced Minor and Induced Topological Minor problems are similar, but the first allows both edge contractions and vertex deletions, whereas the latter allows only vertex deletions and vertex dissolutions. All three problems are NP-complete, even for certain fixed graphs H. We show that these problems can be solved in polynomial time for every fixed H when the input graph G is chordal. Our results can be considered tight, since these problems are known to be W[1]-hard on chordal graphs when parameterized by the size of H. To solve Contractibility and Induced Minor, we define and use a generalization of the classic Disjoint Paths problem, where we require the vertices of each of the k paths to be chosen from a specified set. We prove that this variant is NP-complete even when k=2, but that it is polynomial-time solvable on chordal graphs for every fixed k. Our algorithm for Induced Topological Minor is based on another generalization of Disjoint Paths called Induced Disjoint Paths, where the vertices from different paths may no longer be adjacent. We show that this problem, which is known to be NP-complete when k=2, can be solved in polynomial time on chordal graphs even when k is part of the input. Our results fit into the general framework of graph containment problems, where the aim is to decide whether a graph can be modified into another graph by a sequence of specified graph operations. Allowing combinations of the four well-known operations edge deletion, edge contraction, vertex deletion, and vertex dissolution results in the following ten containment relations: (induced) minor, (induced) topological minor, (induced) subgraph, (induced) spanning subgraph, dissolution, and contraction. Our results, combined with existing results, settle the complexity of each of the ten corresponding containment problems on chordal graphs.     

Parameterized complexity of the induced subgraph problem in directed graphs

In this Letter, we consider the parameterized complexity of the following problem: Given a hereditary property P on digraphs, an input digraph D and a positive integer k, does D have an induced subdigraph on k vertices with property P? We completely characterize hereditary properties for which this induced subgraph problem is W[1]-complete for two classes of directed graphs: general directed graphs and oriented graphs. We also characterize those properties for which the induced subgraph problem is W[1]-complete for general directed graphs but fixed parameter tractable for oriented graphs. These results are among the very few parameterized complexity results on directed graphs.     

Approximating the Sparsest k-Subgraph in Chordal Graphs

Given a simple undirected graph G = (V, E) and an integer k < |V|, the Sparsest k-Subgraph problem asks for a set of k vertices which induces the minimum number of edges. As a generalization of the classical independent set problem, Sparsest k-Subgraph is ????-hard and even not approximable unless ?????? in general graphs. Thus, we investigate Sparsest k-Subgraph in graph classes where independent set is polynomial-time solvable, such as subclasses of perfect graphs. Our two main results are the ????-hardness of Sparsest k-Subgraph on chordal graphs, and a greedy 2-approximation algorithm. Finally, we also show how to derive a P T A S for Sparsest k-Subgraph on proper interval graphs.     

The algorithmic complexity of mixed domination in graphs

Let G=(V,E) be a simple graph with vertex set V and edge set E. A subset W⊆V∪E is a mixed dominating set if every element x∈(V∪E)?W is either adjacent or incident to an element of W. The mixed domination problem is to find a minimum mixed dominating set of G. In this paper we first prove that a connected graph is a tree if and only if its total graph is strongly chordal, and thus we obtain a polynomial-time algorithm for this problem in trees. Further we design another linear-time labeling algorithm for this problem in trees. At the end of the paper, we show that the mixed domination problem is NP-complete even when restricted to split graphs, a subclass of chordal graphs.     

A Fully Dynamic Graph Algorithm for Recognizing Interval Graphs

We present the first dynamic graph algorithm for recognizing interval graphs. The algorithm runs in O(nlog?n) worst-case time per edge deletion or edge insertion, where n is the number of vertices in the graph. The algorithm uses a new representation of interval graphs called the train tree, which is based on the clique-separator graph representation of chordal graphs. The train tree has a number of useful properties and it can be constructed from the clique-separator graph in O(n) time.     

Bandwidth on AT-free graphs

We study the classical Bandwidth problem from the viewpoint of parametrised algorithms. Given a graph G=(V,E) and a positive integer k, the Bandwidth problem asks whether there exists a bijective function β:{1,…,∣V∣}→V such that for every edge uv∈E, ∣β⁻¹(u)−β⁻¹(v)∣≤k. It is known that under standard complexity assumptions, no algorithm for Bandwidth with running time of the form f(k)n^O(1) exists, even when the input is restricted to trees. We initiate the search for classes of graphs where such algorithms do exist. We present an algorithm with running time n⋅2^O(klogk) for Bandwidth on AT-free graphs, a well-studied graph class that contains interval, permutation, and cocomparability graphs. Our result is the first non-trivial algorithm that shows fixed-parameter tractability of Bandwidth on a graph class on which the problem remains NP-complete.     

Linear-time algorithms for problems on planar graphs with fixed disk dimension

The disk dimension of a planar graph G is the least number k for which G embeds in the plane minus k open disks, with every vertex on the boundary of some disk. Useful properties of graphs with a given disk dimension are derived, leading to an algorithm to obtain an outerplanar subgraph of a graph with disk dimension k by removing at most 2k−2 vertices. This reduction is used to obtain linear-time exact and approximation algorithms on graphs with fixed disk dimension. In particular, a linear-time approximation algorithm is presented for the pathwidth problem.     

Isomorphism of chordal (6, 3) graphs

A graph is chordal if it contains no chordless cycles of length at least four and (q, t) if no set of at mostq vertices induces more thant paths of length three. It is known that the isomorphism problem is isomorphism complete for chordal graphs and for (6, 3) graphs. We present polynomial methods to determine the automorphism partition and to test isomorphism of graphs which are both chordal and (6, 3). The approach is based on the study of simplicial partitions of chordal graphs. It is proved that for chordal (6, 3) graphs the automorphism partition coincides with the coarsest regular simplicial partition. This yields anO(n+m logn) isomorphism test.     

A good characterization of squares of strongly chordal split graphs

The square H² of a graph H is obtained from H by adding new edges between every two vertices having distance two in H. Lau and Corneil [Recognizing powers of proper interval, split and chordal graphs, SIAM J. Discrete Math. 18 (2004) 83-102] proved that recognizing squares of split graphs is an NP-complete problem. In contrast, we show that squares of strongly chordal split graphs can be recognized in quadratic-time by giving a structural characterization of these graph class.     

Locally connected spanning trees in cographs, complements of bipartite graphs and doubly chordal graphs

A spanning tree T of a graph G=(V,E) is called a locally connected spanning tree if the set of all neighbors of v in T induces a connected subgraph of G for all v∈V. The problem of recognizing whether a graph admits a locally connected spanning tree is known to be NP-complete even when the input graphs are restricted to chordal graphs. In this paper, we propose linear time algorithms for finding locally connected spanning trees in cographs, complements of bipartite graphs and doubly chordal graphs, respectively.     

Joint object placement and node dimensioning for Internet content distribution

This paper studies a resource allocation problem in a graph, concerning the joint optimization of capacity allocation decisions and object placement decisions, given a single capacity constraint. This problem has applications in Internet content distribution and other domains. The solution to the problem comes through a multi-commodity generalization of the single commodity k-median problem. A two-step algorithm is developed that is capable of solving the multi-commodity case optimally in polynomial time for the case of tree graphs, and approximately (within a constant factor of the optimal) in polynomial time for the case of general graphs.     

Parallel construction of optimal independent spanning trees on Cartesian product of complete graphs

A set of k spanning trees rooted at the same vertex r in a graph G is said to be independent if for each vertex x other than r, the k paths from r to x, one path in each spanning tree, are internally disjoint. Using independent spanning trees (ISTs) one can design fault-tolerant broadcasting schemes and increase message security in a network. Thus, the problem of ISTs on graphs has been received much attention. Recently, Yang et al. proposed a parallel algorithm for generating optimal ISTs on the hypercube. In this paper, we propose a similar algorithm for generating optimal ISTs on Cartesian product of complete graphs. The algorithm can be easily implemented in parallel or distributed systems. Moreover, the proof of its correctness is simpler than that of Yang et al.     

Two algorithms for minimum 2-connected r-hop dominating set

For a graph G=(V,E), a subset D⊆V is an r-hop dominating set if every vertex u∈V−D is at most r-hops away from D. It is a 2-connected r-hop dominating set if the subgraph of G induced by D is 2-connected. In this paper, we present two approximation algorithms to compute minimum 2-connected r-hop dominating set. The first one is a greedy algorithm using ear decomposition of 2-connected graphs. This algorithm is applicable to any 2-connected general graph. The second one is a three-phase algorithm which is only applicable to unit disk graphs. For both algorithms, performance ratios are given.     

On Independent Vertex Sets in Subclasses of Apple-Free Graphs

In a finite undirected graph, an apple consists of a chordless cycle of length at least 4, and an additional vertex which is not in the cycle and sees exactly one of the cycle vertices. A graph is apple-free if it contains no induced subgraph isomorphic to an apple. Apple-free graphs are a common generalization of chordal graphs, claw-free graphs and cographs and occur in various papers. The Maximum Weight Independent Set (MWS) problem is efficiently solvable on chordal graphs, on cographs as well as on claw-free graphs. In this paper, we obtain partial results on some subclasses of apple-free graphs where our results show that the MWS problem is solvable in polynomial time. The main tool is a combination of clique separators with modular decomposition. Our algorithms are robust in the sense that there is no need to recognize whether the input graph is in the given graph class; the algorithm either solves the MWS problem correctly or detects that the input graph is not in the given class.     

Diversified top-<Emphasis Type="Italic">k</Emphasis> clique search

Maximal clique enumeration is a fundamental problem in graph theory and has been extensively studied. However, maximal clique enumeration is time-consuming in large graphs and always returns enormous cliques with large overlaps. Motivated by this, in this paper, we study the diversified top-k clique search problem which is to find top-k cliques that can cover most number of nodes in the graph. Diversified top-k clique search can be widely used in a lot of applications including community search, motif discovery, and anomaly detection in large graphs. A naive solution for diversified top-k clique search is to keep all maximal cliques in memory and then find k of them that cover most nodes in the graph by using the approximate greedy max k-cover algorithm. However, such a solution is impractical when the graph is large. In this paper, instead of keeping all maximal cliques in memory, we devise an algorithm to maintain k candidates in the process of maximal clique enumeration. Our algorithm has limited memory footprint and can achieve a guaranteed approximation ratio. We also introduce a novel light-weight \(\mathsf {PNP}\)-\(\mathsf {Index}\), based on which we design an optimal maximal clique maintenance algorithm. We further explore three optimization strategies to avoid enumerating all maximal cliques and thus largely reduce the computational cost. Besides, for the massive input graph, we develop an I/O efficient algorithm to tackle the problem when the input graph cannot fit in main memory. We conduct extensive performance studies on real graphs and synthetic graphs. One of the real graphs contains 1.02 billion edges. The results demonstrate the high efficiency and effectiveness of our approach.     

Parameterized Complexity of the Spanning Tree Congestion Problem

We study the problem of determining the spanning tree congestion of a?graph. We present some sharp contrasts in the parameterized complexity of this problem. First, we show that on apex-minor-free graphs, a general class of graphs containing planar graphs, graphs of bounded treewidth, and graphs of bounded genus, the problem to determine whether a given graph has spanning tree congestion at most k can be solved in linear time for every fixed k. We also show that for every fixed k and d the problem is solvable in linear time for graphs of degree at most d. In contrast, if we allow only one vertex of unbounded degree, the problem immediately becomes NP-complete for any fixed k??8. Moreover, the hardness result holds for graphs excluding the complete graph on 6 vertices as a minor. We also observe that for k??3 the problem becomes polynomially time solvable.