The complete inclusion structure of leaf power classes

Let k≥2 be an integer and G=(V,E) be a finite simple graph. A tree T is a k-leaf root of G, if V is the set of leaves of T and, for any two distinct x,yV, the distance between x and y in T is at most k if and only if xyE. We say that G is a k-leaf power if there is a k-leaf root of G. The main result of this paper is that, for all 2≤k<k^′, the classes of k- and k^′-leaf powers are inclusion-incomparable, if and only if k^′≤2k−3 and k^′−k is an odd number. With this result, an open problem from the literature about the inclusion structure of these graph classes is solved completely. In addition, the intersection of the smallest pair of inclusion-incomparable classes is studied.     

A 3.4713-approximation algorithm for the capacitated multicast tree routing problem

Given an underlying communication network represented as an edge-weighted graph G=(V,E), a source node sV, a set of destination nodes DV, and a capacity k which is a positive integer, the capacitated multicast tree routing problem asks for a minimum cost routing scheme for source s to send data to all destination nodes, under the constraint that in each routing tree at most k destination nodes are allowed to receive the data copies. The cost of the routing scheme is the sum of the costs of all individual routing trees therein. Improving on our previous approximation algorithm for the problem, we present a new algorithm which achieves a worst case performance ratio of , where ρ denotes the best known approximation ratio for the Steiner minimum tree problem. Since ρ is about 1.55 at the writing of the paper, the ratio achieved by our new algorithm is less than 3.4713. In comparison, the previously best ratio was .     

Maximum Dispersion and Geometric Maximum Weight Cliques

We consider a facility location problem, where the objective is to disperse a number of facilities, i.e., select a given number k of locations from a discrete set of n candidates, such that the average distance between selected locations is maximized. In particular, we present algorithmic results for the case where vertices are represented by points in d-dimensional space, and edge weights correspond to rectilinear distances. Problems of this type have been considered before, with the best result being an approximation algorithm with performance ratio 2. For the case where k is fixed, we establish a linear-time algorithm that finds an optimal solution. For the case where k is part of the input, we present a polynomial-time approximation scheme.     

Approximation Algorithms for Steiner Connected Dominating Set

Steiner connected dominating set （SCDS） is a generalization of the famous connected dominating set problem, where only a specified set of required vertices has to be dominated by a connected dominating set, and known to be NP- hard. This paper firstly modifies the SCDS algorithm of Guha and Khuller and achieves a worst case approximation ratio of （2 ＋ 1/（m - 1））H（min（△, k）） ＋O（1）, which outperforms the previous best result （c ＋ 1）H（min（△, k）） ＋ O（1） in the case of m ≥ 1 ＋1/（c - 1）, where c is the best approximation ratio for Steiner tree, A is the maximum degree of the graph, k is the cardinality of the set of required vertices, m is an optional integer satisfying 0 ≤ m ≤ min（△, k） and H is the harmonic function. This paper also proposes another approximation algorithm which is based on a greedy approach. The second algorithm can establish a worst case approximation ratio of 2 ln（min（△, k）） ＋ O（1）, which can also be improved to 2 lnk if the optimal solution is greater than c·e^2c＋1/2（c＋1）.     

Approximating the Minimum Chain Completion problem

A bipartite graph G=(U,V,E) is a chain graph [M. Yannakakis, Computing the minimum fill-in is NP-complete, SIAM J. Algebraic Discrete Methods 2 (1) (1981) 77–79] if there is a bijection such that Γ(π(1))Γ(π(2))Γ(π(|U|)), where Γ is a function that maps a node to its neighbors.We give approximation algorithms for two variants of the Minimum Chain Completion problem, where we are given a bipartite graph G(U,V,E), and the goal is find the minimum set of edges F that need to be added to G such that the bipartite graph G^′=(U,V,E^′) (E^′=EF) is a chain graph.     

The k-neighbourhood-covering problem on interval graphs

Let G=(V, E) be a simple connected graph and k be a fixed positive integer. A vertex w is said to be a k-neighbourhood-cover (kNC) of an edge (u, v) if d(u, w)≤k and d(v, w)≤k. A set C ? V is called a kNC set if every edge in E is kNC by some vertices of C. The decision problem associated with this problem is NP-complete for general graphs and it remains NP-complete for chordal graphs. In this article, we design an O(n) time algorithm to solve minimum kNC problem on interval graphs by using a data structure called interval tree.     

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.     

Algorithms for Placing Monitors in a Flow Network

In the Flow Edge-Monitor Problem, we are given an undirected graph G=(V,E), an integer k>0 and some unknown circulation ψ on G. We want to find a set of k edges in G, so that if we place k monitors on those edges to measure the flow along them, the total number of edges for which the flow can be uniquely determined is maximized. In this paper, we first show that the Flow Edge-Monitor Problem is NP-hard. Then we study an algorithm called σ-Greedy that, in each step, places monitors on σ edges for which the number of edges where the flow is determined is maximized. We show that the approximation ratio of 1-Greedy is 3 and that the approximation ratio of 2-Greedy is 2.     

Maintaining the Classes of 4-Edge-Connectivity in a Graph On-Line

Two vertices of an undirected graph are called k -edge-connected if there exist k edge-disjoint paths between them (equivalently, they cannot be disconnected by the removal of less than k edges from the graph). Equivalence classes of this relation are called classes of k -edge-connectivity or k -edge-connected components. This paper describes graph structures relevant to classes of 4 -edge-connectivity and traces their transformations as new edges are inserted into the graph. Data structures and an algorithm to maintain these classes incrementally are given. Starting with the empty graph, any sequence of q Same-4-Class? queries and n Insert-Vertex and m Insert-Edge updates can be performed in O(q + m + n log n) total time. Each individual query requires O(1) time in the worst-case. In addition, an algorithm for maintaining the classes of k -edge-connectivity (k arbitrary) in a (k-1) -edge-connected graph is presented. Its complexity is O(q + m + n) , with O(M +k ² n log (n/k)) preprocessing, where M is the number of edges initially in the graph and n is the number of its vertices. Received July 5, 1995; revised October 21, 1996.     

Elementary approximation algorithms for prize collecting Steiner tree problems

This paper deals with approximation algorithms for the prize collecting generalized Steiner forest problem, defined as follows. The input is an undirected graph G=(V,E), a collection T={T₁,…,T_k}, each a subset of V of size at least 2, a weight function , and a penalty function . The goal is to find a forest F that minimizes the cost of the edges of F plus the penalties paid for subsets T_i whose vertices are not all connected by F. Our main result is a -approximation for the prize collecting generalized Steiner forest problem, where n2 is the number of vertices in the graph. This obviously implies the same approximation for the special case called the prize collecting Steiner forest problem (all subsets T_i are of size 2). The approximation algorithm is obtained by applying the local ratio method, and is much simpler than the best known combinatorial algorithm for this problem.Our approach gives a -approximation for the prize collecting Steiner tree problem (all subsets T_i are of size 2 and there is some root vertex r that belongs to all of them). This latter algorithm is in fact the local ratio version of the primal-dual algorithm of Goemans and Williamson [M.X. Goemans, D.P. Williamson, A general approximation technique for constrained forest problems, SIAM Journal on Computing 24 (2) (April 1995) 296–317]. Another special case of our main algorithm is Bar-Yehuda's local ratio -approximation for the generalized Steiner forest problem (all the penalties are infinity) [R. Bar-Yehuda, One for the price of two: a unified approach for approximating covering problems, Algorithmica 27 (2) (June 2000) 131–144]. Thus, an important contribution of this paper is in providing a natural generalization of the framework presented by Goemans and Williamson, and later by Bar-Yehuda.     

Sum Coloring Interval and k -Claw Free Graphs with Application to Scheduling Dependent Jobs

We consider the sum coloring and sum multicoloring problems on several fundamental classes of graphs, including the classes of interval and k-claw free graphs. We give an algorithm that approximates sum coloring within a factor of 1.796, for any graph in which the maximum k-colorable subgraph problem is polynomially solvable. In particular, this improves on the previous best known ratio of 2 for interval graphs. We introduce a new measure of coloring, robust throughput}, that indicates how quickly the graph is colored, and show that our algorithm approximates this measure within a factor of 1.4575. In addition, we study the contiguous (or non-preemptive) sum multicoloring problem on k-claw free graphs. This models, for example, the scheduling of dependent jobs on multiple dedicated machines, where each job requires the exclusive use of at most k machines. Assuming that k is a fixed constant, we obtain the first constant factor approximation for the problem.     

Worst case analysis of a greedy algorithm for graph thickness

In this paper, we consider a greedy algorithm for thickness of graphs. The greedy algorithm we consider here takes a maximum planar subgraph away from the current graph in each iteration and repeats this process until the current graph has no edge. The greedy algorithm outputs the number of iterations which is an upper bound of thickness for an input graph G=(V,E). We show that the performance ratio of the greedy algorithm is .     

Location-Oblivious Distributed Unit Disk Graph Coloring

We present the first location-oblivious distributed unit disk graph coloring algorithm having a provable performance ratio of three (i.e. the number of colors used by the algorithm is at most three times the chromatic number of the graph). This is an improvement over the standard sequential coloring algorithm that has a worst case lower bound on its performance ratio of 4−3/k (for any k>2, where k is the chromatic number of the unit disk graph achieving the lower bound) (Tsai et al., in Inf. Process. Lett. 84(4):195–199, 2002). We present a slightly better worst case lower bound on the performance ratio of the sequential coloring algorithm for unit disk graphs with chromatic number 4. Using simulation, we compare our algorithm with other existing unit disk graph coloring algorithms.     

Simplicial powers of graphs

In a graph, a vertex is simplicial if its neighborhood is a clique. For an integer k≥1, a graph G=(V_G,E_G) is the k-simplicial power of a graph H=(V_H,E_H) (H a root graph of G) if V_G is the set of all simplicial vertices of H, and for all distinct vertices x and y in V_G, xyE_G if and only if the distance in H between x and y is at most k. This concept generalizes k-leaf powers introduced by Nishimura, Ragde and Thilikos which were motivated by the search for underlying phylogenetic trees; k-leaf powers are the k-simplicial powers of trees. Recently, a lot of work has been done on k-leaf powers and their roots as well as on their variants phylogenetic roots and Steiner roots. For k≤5, k-leaf powers can be recognized in linear time, and for k≤4, structural characterizations are known. For k≥6, the recognition and characterization problems of k-leaf powers are still open. Since trees and block graphs (i.e., connected graphs whose blocks are cliques) have very similar metric properties, it is natural to study k-simplicial powers of block graphs. We show that leaf powers of trees and simplicial powers of block graphs are closely related, and we study simplicial powers of other graph classes containing all trees such as ptolemaic graphs and strongly chordal graphs.     

Unbalanced Graph Partitioning

We investigate the unbalanced cut problems. A cut (A,B) is called unbalanced if the size of its smaller side is at most k (called k-size) or exactly k (called Ek-size), where k is an input parameter. We consider two closely related unbalanced cut problems, in which the quality of a cut is measured with respect to the sparsity and the conductance, respectively. We show that even if the input graph is restricted to be a tree, the Ek-Sparsest Cut problem (to find an Ek-size cut with the minimum sparsity) is still NP-hard. We give a bicriteria approximation algorithm for the k-Sparsest Cut problem (to find a k-size cut with the minimum sparsity), which outputs a cut whose sparsity is at most O(logn) times the optimum and whose smaller side has size at most O(logn)k. As a consequence, this leads to a (O(logn),O(logn))-bicriteria approximation algorithm for the Min k-Conductance problem (to find a k-size cut with the minimum conductance).     

Improved Approximation Algorithms for the Min-max Tree Cover and Bounded Tree Cover Problems

In this paper we provide improved approximation algorithms for the Min-Max Tree Cover and Bounded Tree Cover problems. Given a graph G=(V,E) with weights w:E→?⁺, a set T ₁,T ₂,…,T _k of subtrees of G is called a tree cover of G if $V=\bigcup_{i=1}^{k} V(T_{i})$ . In the Min-Max k-tree Cover problem we are given graph G and a positive integer k and the goal is to find a tree cover with k trees, such that the weight of the largest tree in the cover is minimized. We present a 3-approximation algorithm for this improving the two different approximation algorithms presented in Arkin et al. (J. Algorithms 59:1–18, 2006) and Even et al. (Oper. Res. Lett. 32(4):309–315, 2004) with ratio 4. The problem is known to have an APX-hardness lower bound of $\frac{3}{2}$ (Xu and Wen in Oper. Res. Lett. 38:169–173, 2010). In the Bounded Tree Cover problem we are given graph G and a bound λ and the goal is to find a tree cover with minimum number of trees such that each tree has weight at most λ. We present a 2.5-approximation algorithm for this, improving the 3-approximation bound in Arkin et al. (J. Algorithms 59:1–18, 2006).     

Mining collective knowledge: inferring functional labels from online review for business

Uncertain graph has been widely used to represent graph data with inherent uncertainty in structures. Reliability search is a fundamental problem in uncertain graph analytics. This paper investigates on a new problem with broad real-world applications, the top-k reliability search problem on uncertain graphs, that is, finding the k vertices v with the highest reliabilities of connections from a source vertex s to v. Note that the existing algorithm for the threshold-based reliability search problem is inefficient for the top-k reliability search problem. We propose a new algorithm to efficiently solve the top-k reliability search problem. The algorithm adopts two important techniques, namely the BFS sharing technique and the offline sampling technique. The BFS sharing technique exploits overlaps among different sampled possible worlds of the input uncertain graph and performs a single BFS on all possible worlds simultaneously. The offline sampling technique samples possible worlds offline and stores them using a compact structure. The algorithm also takes advantages of bit vectors and bitwise operations to improve efficiency. In addition, we generalize the top-k reliability search problem from single-source case to the multi-source case and show that the multi-source case of the problem can be equivalently converted to the single-source case of the problem. Moreover, we define two types of the reverse top-k reliability search problems with different semantics on uncertain graphs. We propose appropriate solutions for both of them. Extensive experiments carried out on both real and synthetic datasets verify that the optimized algorithm outperforms the baselines by 1–2 orders of magnitude in execution time while achieving comparable accuracy. Meanwhile, the optimized algorithm exhibits linear scalability with respect to the size of the input uncertain graph.     

Maximum Dispersion and Geometric Maximum Weight Cliques

We consider a facility location problem, where the objective is to “disperse” a number of facilities, i.e., select a given number k of locations from a discrete set of n candidates, such that the average distance between selected locations is maximized. In particular, we present algorithmic results for the case where vertices are represented by points in d-dimensional space, and edge weights correspond to rectilinear distances. Problems of this type have been considered before, with the best result being an approximation algorithm with performance ratio 2. For the case where k is fixed, we establish a linear-time algorithm that finds an optimal solution. For the case where k is part of the input, we present a polynomial-time approximation scheme.     

Weighted Matching in the Semi-Streaming Model

We present an approximation algorithm to find a weighted matching of a graph in the one-pass semi-streaming model. The semi-streaming model forbids random access to the input graph and restricts the memory to ${\mathcal{O}}(n\cdot\operatorname{polylog}n)$ bits where n denotes the number of the vertices of the input graph. We obtain an approximation ratio of 5.58 while the previously best algorithm achieves a ratio of 5.82.     

Finding multiple induced disjoint paths in general graphs

In an undirected graph, paths P₁,P₂,…,Pk are induced disjoint if each one of them is chordless (i.e., is an induced path) and any two of them have neither common nodes nor adjacent nodes. This paper investigates the Maximum Induced Disjoint Paths (MIDP) problem: in an undirected graph G=(V,E), given k node pairs {s₁,t₁},…,{sk,tk}, connect maximum number of these node pairs via induced disjoint paths. Till now, the only things known about MIDP are: i) it is NP-hard; ii) it is NP-hard even when k=2; iii) it can be solved in polynomial time when k is a fixed constant and the given graph is a directed planar graph (Kobayashi, 2009 [9]). This paper proves that for general k and any ?>0, it is NP-hard to approximate MIDP within m1/2−?, where m=|E|. Two algorithms for MIDP are given by this paper: a greedy algorithm whose approximation ratio is and an on-line algorithm which has a good lower bound.