Algorithms for the maximum k-club problem in graphs

Given a simple undirected graph G, a k-club is a subset of vertices inducing a subgraph of diameter at most k. The maximum k-club problem (MkCP) is to find a k-club of maximum cardinality in G. These structures, originally introduced to model cohesive subgroups in social network analysis, are of interest in network-based data mining and clustering applications. The maximum k-club problem is NP-hard, moreover, determining whether a given k-club is maximal (by inclusion) is NP-hard as well. This paper first provides a sufficient condition for testing maximality of a given k-club. Then it proceeds to develop a variable neighborhood search (VNS) heuristic and an exact algorithm for MkCP that uses the VNS solution as a lower bound. Computational experiments with test instances available in the literature show that the proposed algorithms are very effective on sparse instances and outperform the existing methods on most dense graphs from the testbed.     

The matching extension problem in general graphs is co-NP-complete

A simple connected graph G with 2n vertices is said to be k-extendable for an integer k with \(0<k<n\) if G contains a perfect matching and every matching of cardinality k in G is a subset of some perfect matching. Lakhal and Litzler (Inf Process Lett 65(1):11–16, 1998) discovered a polynomial algorithm that decides whether a bipartite graph is k-extendable. For general graphs, however, it has been an open problem whether there exists a polynomial algorithm. The new result presented in this paper is that the extendability problem is co-NP-complete.     

Generalized perfect domination in graphs

Let k be a positive integer and G=(V,E) be a graph. A vertex subset D of a graph G is called a perfect k-dominating set of G, if every vertex v of G, not in D, is adjacent to exactly k vertices of D. The minimum cardinality of a perfect k-dominating set of G is the perfect k-domination number γ _kp (G). In this paper, we give characterizations of graphs for which γ _kp (G)=γ(G)+k?2 and prove that the perfect k-domination problem is NP-complete even when restricted to bipartite graphs and chordal graphs. Also, by using dynamic programming techniques, we obtain an algorithm to determine the perfect k-domination number of trees.     

On nonlinear multi-covering problems

In this paper we define the exact k-coverage problem, and study it for the special cases of intervals and circular-arcs. Given a set system consisting of a ground set of n points with integer demands \(\{d_0,\dots ,d_{n-1}\}\) and integer rewards, subsets of points, and an integer k, select up to k subsets such that the sum of rewards of the covered points is maximized, where point i is covered if exactly \(d_i\) subsets containing it are selected. Here we study this problem and some related optimization problems. We prove that the exact k-coverage problem with unbounded demands is NP-hard even for intervals on the real line and unit rewards. Our NP-hardness proof uses instances where some of the natural parameters of the problem are unbounded (each of these parameters is linear in the number of points). We show that this property is essential, as if we restrict (at least) one of these parameters to be a constant, then the problem is polynomial time solvable. Our polynomial time algorithms are given for various generalizations of the problem (in the setting where one of the parameters is a constant).     

Note on the hardness of generalized connectivity

Let G be a nontrivial connected graph of order n and let k be an integer with 2??k??n. For a set S of k vertices of G, let ??(S) denote the maximum number ? of edge-disjoint trees T ₁,T ₂,??,T _? in G such that V(T _i )??V(T _j )=S for every pair i,j of distinct integers with 1??i,j???. Chartrand et al. generalized the concept of connectivity as follows: The k-connectivity, denoted by ?? _k (G), of G is defined by ?? _k (G)=min{??(S)}, where the minimum is taken over all k-subsets S of V(G). Thus ?? ₂(G)=??(G), where ??(G) is the connectivity of G, for which there are polynomial-time algorithms to solve it. This paper mainly focus on the complexity of determining the generalized connectivity of a graph. At first, we obtain that for two fixed positive integers k ₁ and k ₂, given a graph G and a k ₁-subset S of V(G), the problem of deciding whether G contains k ₂ internally disjoint trees connecting S can be solved by a polynomial-time algorithm. Then, we show that when k ₁ is a fixed integer of at least 4, but k ₂ is not a fixed integer, the problem turns out to be NP-complete. On the other hand, when k ₂ is a fixed integer of at least 2, but k ₁ is not a fixed integer, we show that the problem also becomes NP-complete.     

Online scheduling on parallel machines with two GoS levels

This paper investigates the online scheduling problem on parallel and identical machines with a new feature that service requests from various customers are entitled to many different grade of service (GoS) levels. Hence each job and machine are labeled with the GoS levels, and each job can be processed by a particular machine only when the GoS level of the job is not less than that of the machine. The goal is to minimize the makespan. In this paper, we consider the problem with two GoS levels. It assumes that the GoS levels of the first k machines and the last m−k machines are 1 and 2, respectively. And every job has a GoS level of 1 alternatively or 2. We first prove the lower bound of the problem under consideration is at least 2. Then we discuss the performance of algorithm AW presented in Azar et al. (J. Algorithms 18:221–237, 1995) for the problem and show it has a tight bound of 4−1/m. Finally, we present an approximation algorithm with competitive ratio . Research supported by Natural Science Foundation of Zhejiang Province (Y605316) and its preliminary version appeared in Proceedings of AAIM2006, LNCS, 4041, 11-21.     

Optimal key tree structure for two-user replacement and deletion problems

We study the optimal tree structure for the key management problem. In the key tree, when two or more leaves are deleted or replaced, the updating cost is defined to be the number of encryptions needed to securely update the remaining keys. The objective is to find the optimal tree structure where the worst case updating cost is minimum. We extend the result of 1-replacement problem in Snoeyink et al. (Proceedings of the twentieth annual IEEE conference on computer communications, pp. 422–431, 2001) to the k-user case. We first show that the k-deletion problem can be solved by handling k-replacement problem. Focusing on the k-replacement problem, we show that the optimal tree can be computed in $O(n^{(k+1)^{2}})$ time given a constant k. Then we derive a tight degree bound for optimal tree when replacing two users. By investigating the maximum number of leaves that can be placed on the tree given a fixed worst case replacement cost, we prove that a balanced tree with certain root degree 5≤d≤7 where the number of leaves in the subtrees differs by at most one and each subtree is a 2-3 tree can always achieve the minimum worst case 2-replacement cost. Thus the optimal tree for two-user replacement problem can be efficiently constructed in O(n) time.     

Enabling high-dimensional range queries using <Emphasis Type="Italic">k</Emphasis>NN indexing techniques: approaches and empirical results

Many modern search applications are high-dimensional and depend on efficient orthogonal range queries. These applications span web-based and scientific needs as well as uses for data mining. Although k-nearest neighbor queries are becoming increasingly common due to mobile and geospatial applications, orthogonal range queries in high-dimensional data remain extremely important and relevant. For efficient querying, data is typically stored in an index optimized for either kNN or range queries. This can be problematic when data is optimized for kNN retrieval and a user needs a range query or vice versa. Here, we address the issue of using a kNN-based index for range queries, as well as outline the general computational geometry problem of adapting these systems to range queries. We refer to these methods as space-based decompositions and provide a straightforward heuristic for this problem. Using iDistance as our applied kNN indexing technique, we also develop an optimal (data-based) algorithm designed specifically for its indexing scheme. We compare this method to the suggested naïve approach using real world datasets. The data-based algorithm consistently performs better.     

k-tuple total domination in cross products of graphs

For k??1 an integer, a set S of vertices in a graph G with minimum degree at least?k is a k-tuple total dominating set of G if every vertex of G is adjacent to at least k vertices in S. The minimum cardinality of a k-tuple total dominating set of G is the k-tuple total domination number of G. When k=1, the k-tuple total domination number is the well-studied total domination number. In this paper, we establish upper and lower bounds on the k-tuple total domination number of the cross product graph G×H for any two graphs G and H with minimum degree at least?k. In particular, we determine the exact value of the k-tuple total domination number of the cross product of two complete graphs.     

Relay node placement in two-tiered wireless sensor networks with base stations

This paper addresses the relay node placement problem in two-tiered wireless sensor networks with base stations, which aims to deploy a minimum number of relay nodes to achieve certain coverage and connectivity requirement. Under the assumption that the communication range of the sensor nodes is no more than that of the relay node, we present a polynomial time (5+?)-approximation algorithm for the 1-coverage 1-connected problem. Furthermore, we consider the fault tolerant problem in the network, we present a polynomial time (20+?)-approximation algorithm for the 2-coverage 2-connected problem, where ? is any given positive constant. For the k-coverage 2-connected situation, we present a polynomial time (15k?10+?)-approximation algorithm.     

Exact combinatorial algorithms and experiments for?finding maximum k-plexes

We propose new practical algorithms to find maximum-cardinality k-plexes in graphs. A k-plex denotes a vertex subset in a graph inducing a subgraph where every vertex has edges to all but at most k vertices in the k-plex. Cliques are 1-plexes. In analogy to the special case of finding maximum-cardinality cliques, finding maximum-cardinality k-plexes is NP-hard. Complementing previous work, we develop exact combinatorial algorithms, which are strongly based on methods from parameterized algorithmics. The experiments with our freely available implementation indicate the competitiveness of our approach, for many real-world graphs outperforming the previously used methods.     

A local search approximation algorithm for the uniform capacitated <Emphasis Type="Italic">k</Emphasis>-facility location problem

In the uniform capacitated k-facility location problem (UC-k-FLP), we are given a set of facilities and a set of clients. Every client has a demand. Every facility have an opening cost and an uniform capacity. For each client–facility pair, there is an unit service cost to serve the client with unit demand by the facility. The total demands served by a facility cannot exceed the uniform capacity. We want to open at most k facilities to serve all the demands of the clients without violating the capacity constraint such that the total opening and serving cost is minimized. The main contribution of this work is to present the first combinatorial bi-criteria approximation algorithm for the UC-k-FLP by violating the cardinality constraint.     

Parameterized complexity of k-anonymity: hardness and tractability

The problem of publishing personal data without giving up privacy is becoming increasingly important. A precise formalization that has been recently proposed is the k-anonymity, where the rows of a table are partitioned into clusters of sizes at least k and all rows in a cluster become the same tuple after the suppression of some entries. The natural optimization problem, where the goal is to minimize the number of suppressed entries, is hard even when the stored values are over a binary alphabet or the table consists of a bounded number of columns. In this paper we study how the complexity of the problem is influenced by different parameters. First we show that the problem is W[1]-hard when parameterized by the value of the solution (and k). Then we exhibit a fixed-parameter algorithm when the problem is parameterized by the number of columns and the number of different values in any column. Finally, we prove that k-anonymity is still APX-hard even when restricting to instances with 3 columns and k=3.     

Finding paths with minimum shared edges

Motivated by a security problem in geographic information systems, we study the following graph theoretical problem: given a graph G, two special nodes s and t in G, and a number k, find k paths from s to t in G so as to minimize the number of edges shared among the paths. This is a generalization of the well-known disjoint paths problem. While disjoint paths can be computed efficiently, we show that finding paths with minimum shared edges is NP-hard. Moreover, we show that it is even hard to approximate the minimum number of shared edges within a factor of $2^{\log^{1-\varepsilon}n}$ , for any constant ε>0. On the positive side, we show that there exists a (k?1)-approximation algorithm for the problem, using an adaption of a network flow algorithm. We design some heuristics to improve the quality of the output, and provide empirical results.     

Some variations on constrained minimum enclosing circle problem

Given a set P of n points and a straight line L, we study three important variations of minimum enclosing circle problem as follows:

1. Computing k identical circles of minimum radius with centers on L, whose union covers all the points in P.
2. Computing the minimum radius circle centered on L that can enclose at least k points of P.
3. If each point in P is associated with one of the k given colors, then compute a minimum radius circle with center on L such that at least one point of each color lies inside it.

We propose three algorithms for Problem (i). The first one runs in O(nklogn) time and O(n) space. The second one is efficient where k?n; it runs in O(nlogn+nk+k ²log³ n) time and O(nlogn) space. The third one is based on parametric search and it runs in O(nlogn+klog⁴ n) time. For Problem (ii), the time and space complexities of the proposed algorithm are O(nk) and O(n) respectively. For Problem (iii), our proposed algorithm runs in O(nlogn) time and O(n) space.     

Minimum paired-dominating set in chordal bipartite graphs and perfect elimination bipartite graphs

A set D?V of a graph G=(V,E) is a dominating set of G if every vertex in V?D has at least one neighbor in D. A dominating set D of G is a paired-dominating set of G if the induced subgraph, G[D], has a perfect matching. Given a graph G=(V,E) and a positive integer k, the paired-domination problem is to decide whether G has a paired-dominating set of cardinality at most k. The paired-domination problem is known to be NP-complete for bipartite graphs. In this paper, we, first, strengthen this complexity result by showing that the paired-domination problem is NP-complete for perfect elimination bipartite graphs. We, then, propose a linear time algorithm to compute a minimum paired-dominating set of a chordal bipartite graph, a well studied subclass of bipartite graphs.     

Star list chromatic number of planar subcubic graphs

A proper coloring of the vertices of a graph G is called a star-coloring if the union of every two color classes induces a star forest. The graph G is L-star-colorable if for a given list assignment L there is a star-coloring π such that π(v)∈L(v). If G is L-star-colorable for any list assignment L with |L(v)|≥k for all v∈V(G), then G is called k-star-choosable. The star list chromatic number of G, denoted by $\chi_{s}^{l}(G)$ , is the smallest integer k such that G is k-star-choosable. In this paper, we prove that every planar subcubic graph is 6-star-choosable.     

Some results on the injective chromatic number of?graphs

A k-coloring of a graph G=(V,E) is a mapping c:V??{1,2,??,k}. The coloring c is injective if, for every vertex v??V, all the neighbors of v are assigned with distinct colors. The injective chromatic number ?? _i (G) of G is the smallest k such that G has an injective k-coloring. In this paper, we prove that every K ₄-minor free graph G with maximum degree ????1 has $\chi_{i}(G)\le \lceil \frac{3}{2}\Delta\rceil$ . Moreover, some related results and open problems are given.     

Necessary Edges in k-Chordalisations of Graphs

A k-chordalisation of a graph G = (V,E) is a graph H = (V,F) obtained by adding edges to G, such that H is a chordal graph with maximum clique size at most k. This note considers the problem: given a graph G = (V,E) which pairs of vertices, non-adjacent in G, will be an edge in every k-chordalisation of G. Such a pair is called necessary for treewidth k. An equivalent formulation is: which edges can one add to a graph G such that every tree decomposition of G of width at most k is also a tree decomposition of the resulting graph G. Some sufficient, and some necessary and sufficient conditions are given for pairs of vertices to be necessary for treewidth k. For a fixed k, one can find in linear time for a given graph G the set of all necessary pairs for treewidth k. If k is given as part of the input, then this problem is coNP-hard. A few similar results are given when interval graphs (and hence pathwidth) are used instead of chordal graphs and treewidth.     

On the complete width and edge clique cover problems

A complete graph is the graph in which every two vertices are adjacent. For a graph \(G=(V,E)\), the complete width of G is the minimum k such that there exist k independent sets \(\mathtt {N}_i\subseteq V\), \(1\le i\le k\), such that the graph \(G'\) obtained from G by adding some new edges between certain vertices inside the sets \(\mathtt {N}_i\), \(1\le i\le k\), is a complete graph. The complete width problem is to decide whether the complete width of a given graph is at most k or not. In this paper we study the complete width problem. We show that the complete width problem is NP-complete on \(3K_2\)-free bipartite graphs and polynomially solvable on \(2K_2\)-free bipartite graphs and on \((2K_2,C_4)\)-free graphs. As a by-product, we obtain the following new results: the edge clique cover problem is NP-complete on \(\overline{3K_2}\)-free co-bipartite graphs and polynomially solvable on \(C_4\)-free co-bipartite graphs and on \((2K_2, C_4)\)-free graphs. We also give a characterization for k-probe complete graphs which implies that the complete width problem admits a kernel of at most \(2^k\) vertices. This provides another proof for the known fact that the edge clique cover problem admits a kernel of at most \(2^k\) vertices. Finally we determine all graphs of small complete width \(k\le 3\).