Hardness of <Emphasis Type="Italic">k</Emphasis>-Vertex-Connected Subgraph Augmentation Problem

Given a k-connected graph G=(V,E) and V ^′⊂V, k-Vertex-Connected Subgraph Augmentation Problem (k-VCSAP) is to find S⊂V∖V ^′ with minimum cardinality such that the subgraph induced by V ^′∪S is k-connected. In this paper, we study the hardness of k-VCSAP in undirect graphs. We first prove k-VCSAP is APX-hard. Then, we improve the lower bound in two ways by relying on different assumptions. That is, we prove no algorithm for k-VCSAP has a PR better than O(log (log n)) unless P=NP and O(log n) unless NP⊆DTIME(n ^{O(log log n)}), where n is the size of an input graph.     

Subhypergraph counts in extremal and random hypergraphs and the fractional <Emphasis Type="Italic">q</Emphasis>-independence

We study the extremal parameter N(n,m,H) which is the largest number of copies of a hypergraph H that can be formed of at most n vertices and m edges. Generalizing previous work of Alon (Isr. J. Math. 38:116–130, 1981), Friedgut and Kahn (Isr. J. Math. 105:251–256, 1998) and Janson, Oleszkiewicz and the third author (Isr. J. Math. 142:61–92, 2004), we obtain an asymptotic formula for N(n,m,H) which is strongly related to the solution α _q (H) of a linear programming problem, called here the fractional q-independence number of H. We observe that α _q (H) is a piecewise linear function of q and determine it explicitly for some ranges of q and some classes of H. As an application, we derive exponential bounds on the upper tail of the distribution of the number of copies of H in a random hypergraph.     

The <Emphasis Type="Italic">p</Emphasis>-maxian problem on block graphs

This paper deals with the p-maxian problem on block graphs with unit edge length. It is shown that the two points with maximum distance provide an optimal solution for the 2-maxian problem of block graphs except for K ₃. It can easily be extended to the p-maxian problem of block graphs. So we solve the p-maxian problem on block graphs in linear time.     

On minimum <Emphasis Type="Italic">m</Emphasis>-connected <Emphasis Type="Italic">k</Emphasis>-dominating set problem in unit disc graphs

Minimum m-connected k-dominating set problem is as follows: Given a graph G=(V,E) and two natural numbers m and k, find a subset S⊆V of minimal size such that every vertex in V∖S is adjacent to at least k vertices in S and the induced graph of S is m-connected. In this paper we study this problem with unit disc graphs and small m, which is motivated by the design of fault-tolerant virtual backbone for wireless sensor networks. We propose two approximation algorithms with constant performance ratios for m≤2. We also discuss how to design approximation algorithms for the problem with arbitrarily large m. This work was supported in part by the Research Grants Council of Hong Kong under Grant No. CityU 1165/04E, the National Natural Science Foundation of China under Grant No. 70221001, 10531070 and 10771209.     

Power Assignment for <Emphasis Type="Italic">k</Emphasis>-Connectivity in Wireless Ad Hoc Networks

The problem Min-Power k-Connectivity seeks a power assignment to the nodes in a given wireless ad hoc network such that the produced network topology is k-connected and the total power is the lowest. In this paper, we present several approximation algorithms for this problem. Specifically, we propose a 3k-approximation algorithm for any k, a (k + 12H (k)) -approximation algorithm for k(2k–1) n where n is the network size, a (k+2(k + 1)/2) -approximation algorithm for 2 k7, a 6-approximation algorithm for k = 3, and a 9-approximation algorithm for k = 4.This work is supported in part by Hong Kong Research Grant Council under grant No. CityU 1149/04E.This work is partially supported by NSF CCR-0311174.     

On the distance paired domination of generalized Petersen graphs <Emphasis Type="Italic">P</Emphasis>(<Emphasis Type="Italic">n</Emphasis>,1) and <Emphasis Type="Italic">P</Emphasis>(<Emphasis Type="Italic">n</Emphasis>,2)

Let G=(V,E) be a graph without an isolated vertex. A set D⊆V(G) is a k -distance paired dominating set of G if D is a k-distance dominating set of G and the induced subgraph 〈D〉 has a perfect matching. The minimum cardinality of a k-distance paired dominating set for graph G is the k -distance paired domination number, denoted by γ _p ^k (G). In this paper, we determine the exact k-distance paired domination number of generalized Petersen graphs P(n,1) and P(n,2) for all k≥1.     

The <Emphasis Type="Italic">w</Emphasis>-centroids and least <Emphasis Type="Italic">w</Emphasis>-central subtrees in weighted trees

Let T be a weighted tree with a positive number w(v) associated with each vertex v. A subtree S is a w-central subtree of the weighted tree T if it has the minimum eccentricity \(e_L(S)\) in median graph \(G_{LW}\). A w-central subtree with the minimum vertex weight is called a least w-central subtree of the weighted tree T. In this paper we show that each least w-central subtree of a weighted tree either contains a vertex of the w-centroid or is adjacent to a vertex of the w-centroid. Also, we show that any two least w-central subtrees of a weighted tree either have a nonempty intersection or are adjacent.     

Data aggregation for <Emphasis Type="Italic">p</Emphasis>-median problems

In this paper, we use a pseudo-Boolean formulation of the p-median problem and using data aggregation, provide a compact representation of p-median problem instances. We provide computational results to demonstrate this compactification in benchmark instances. We then use our representation to explain why some p-median problem instances are more difficult to solve to optimality than other instances of the same size. We also derive a preprocessing rule based on our formulation, and describe equivalent p-median problem instances, which are identical sized instances which are guaranteed to have identical optimal solutions.     

The <Emphasis Type="Italic">k</Emphasis>-metric dimension

The anti-Ramsey number AR(G, H) is defined to be the maximum number of colors in an edge coloring of G which doesn’t contain any rainbow subgraphs isomorphic to H. It is clear that there is an \(AR(K_{m,n},kK_2)\)-edge-coloring of \(K_{m,n}\) that doesn’t contain any rainbow \(kK_2\). In this paper, we show the uniqueness of this kind of \(AR(K_{m,n},kK_2)\)-edge-coloring of \(K_{m,n}\).     

The <Emphasis Type="Italic">k</Emphasis>-coloring fitness landscape

This paper deals with the fitness landscape analysis of the k-coloring problem. We study several standard instances extracted from the second DIMACS benchmark. Statistical indicators are used to investigate both global and local structure of fitness landscapes. An approximative distance on the k-coloring space is proposed to perform these statistical measures. Local search operator trajectories on various landscapes are then studied using the time series analysis. Results are used to better understand the behavior of metaheuristics based on local search when dealing with the graph coloring problem.     

A polynomial-time perfect sampler for the <Emphasis Type="Italic">Q</Emphasis>-Ising with a vertex-independent noise

We present a polynomial-time perfect sampler for the Q-Ising with a vertex-independent noise. The Q-Ising, one of the generalized models of the Ising, arose in the context of Bayesian image restoration in statistical mechanics. We study the distribution of Q-Ising on a two-dimensional square lattice over n vertices, that is, we deal with a discrete state space {1,…,Q} ⁿ for a positive integer Q. Employing the Q-Ising (having a parameter β) as a prior distribution, and assuming a Gaussian noise (having another parameter α), a posterior is obtained from the Bayes’ formula. Furthermore, we generalize it: the distribution of noise is not necessarily a Gaussian, but any vertex-independent noise. We first present a Gibbs sampler from our posterior, and also present a perfect sampler by defining a coupling via a monotone update function. Then, we show O(nlog n) mixing time of the Gibbs sampler for the generalized model under a condition that β is sufficiently small (whatever the distribution of noise is). In case of a Gaussian, we obtain another more natural condition for rapid mixing that α is sufficiently larger than β. Thereby, we show that the expected running time of our sampler is O(nlog n).     

Designing <Emphasis Type="Italic">k</Emphasis>-coverage schedules in wireless sensor networks

Some sensor network applications require k-coverage to ensure the quality of surveillance. Meanwhile, energy is another primary concern for sensor networks. In this paper, we investigate the Sensor Scheduling for k-Coverage (SSC) problem which requires to efficiently schedule the sensors, such that the monitored area can be k-covered throughout the whole network lifetime with the purpose of maximizing network lifetime. The SSC problem is NP-hard and we propose two heuristic algorithms under different scenarios. In addition, we develop a guideline for users to better design a sensor deployment plan to save energy by employing a density control scheme. Simulation results are presented to evaluate our proposed algorithms.     

Algorithms for connected <Emphasis Type="Italic">p</Emphasis>-centdian problem on block graphs

We consider the facility location problem of locating a set \(X_p\) of p facilities (resources) on a network (or a graph) such that the subnetwork (or subgraph) induced by the selected set \(X_p\) is connected. Two problems on a block graph G are proposed: one problem is to minimizes the sum of its weighted distances from all vertices of G to \(X_p\), another problem is to minimize the maximum distance from each vertex that is not in \(X_p\) to \(X_p\) and, at the same time, to minimize the sum of its distances from all vertices of G to \(X_p\). We prove that the first problem is linearly solvable on block graphs with unit edge length. For the second problem, it is shown that the set of Pareto-optimal solutions of the two criteria has cardinality not greater than n, and can be obtained in \(O(n^2)\) time, where n is the number of vertices of the block graph G.     

Computing the <Emphasis Type="Italic">k</Emphasis>-resilience of a synchronized multi-robot system

The vertex arboricity va(G) of a graph G is the minimum number of colors the vertices can be colored so that each color class induces a forest. It was known that \(va(G)\le 3\) for every planar graph G. In this paper, we prove that \(va(G)\le 2\) if G is a planar graph without intersecting 5-cycles.     

On list <Emphasis Type="Italic">r</Emphasis>-hued coloring of planar graphs

A list assignment of G is a function L that assigns to each vertex \(v\in V(G)\) a list L(v) of available colors. Let r be a positive integer. For a given list assignment L of G, an (L, r)-coloring of G is a proper coloring \(\phi \) such that for any vertex v with degree d(v), \(\phi (v)\in L(v)\) and v is adjacent to at least \( min\{d(v),r\}\) different colors. The list r-hued chromatic number of G, \(\chi _{L,r}(G)\), is the least integer k such that for every list assignment L with \(|L(v)|=k\), \(v\in V(G)\), G has an (L, r)-coloring. We show that if \(r\ge 32\) and G is a planar graph without 4-cycles, then \(\chi _{L,r}(G)\le r+8\). This result implies that for a planar graph with maximum degree \(\varDelta \ge 26\) and without 4-cycles, Wagner’s conjecture in [Graphs with given diameter and coloring problem, Technical Report, University of Dortmund, Germany, 1977] holds.     

The triangle <Emphasis Type="Italic">k</Emphasis>-club problem

Graph models have long been used in social network analysis and other social and natural sciences to render the analysis of complex systems easier. In applied studies, to understand the behaviour of social networks and the interactions that command that behaviour, it is often necessary to identify sets of elements which form cohesive groups, i.e., groups of actors that are strongly interrelated. The clique concept is a suitable representation for groups of actors that are all directly related pair-wise. However, many social relationships are established not only face-to-face but also through intermediaries, and the clique concept misses all the latter. To deal with these cases, it is necessary to adopt approaches that relax the clique concept. In this paper we introduce a new clique relaxation—the triangle k-club—and its associated maximization problem—the maximum triangle k-club problem. We propose integer programming formulations for the problem, stated in different variable spaces, and derive valid inequalities to strengthen their linear programming relaxations. Computational results on randomly generated and real-world graphs, with \(k=2\) and \(k=3\), are reported.     

An Improved Approximation Algorithm for Multicast <Emphasis Type="Italic">k</Emphasis>-Tree Routing

An improved approximation algorithm is presented in this paper for the multicast k-tree routing problem. The algorithm has a worst case performance ratio of (2.4 + ρ), where ρ is the best approximation ratio for the metric Steiner tree problem (and is about 1.55 so far). The previous best approximation algorithm for the multicast k-tree routing problem has a performance ratio of 4. Two techniques, weight averaging and tree partitioning, are developed to facilitate the algorithm design and analysis.Research supported by AICML, CFI, NSERC, PENCE, a Startup Grant from the University of Alberta, and NNSF Grant 60373012.     

Approximation algorithms for <Emphasis Type="Italic">k</Emphasis>-level stochastic facility location problems

In the k-level facility location problem (FLP), we are given a set of facilities, each associated with one of k levels, and a set of clients. We have to connect each client to a chain of opened facilities spanning all levels, minimizing the sum of opening and connection costs. This paper considers the k-level stochastic FLP, with two stages, when the set of clients is only known in the second stage. There is a set of scenarios, each occurring with a given probability. A facility may be opened in any stage, however, the cost of opening a facility in the second stage depends on the realized scenario. The objective is to minimize the expected total cost. For the stage-constrained variant, when clients must be served by facilities opened in the same stage, we present a \((4-o(1))\)-approximation, improving on the 4-approximation by Wang et al. (Oper Res Lett 39(2):160–161, 2011) for each k. In the case with \(k=2,\,3\), the algorithm achieves factors 2.56 and 2.78, resp., which improves the \((3+\epsilon )\)-approximation for \(k=2\) by Wu et al. (Theor Comput Sci 562:213–226, 2015). For the non-stage-constrained version, we give the first approximation for the problem, achieving a factor of 3.495 for the case with \(k = 2\), and \(2k-1+o(1)\) in general.     

Efficient approximation algorithms for computing <Emphasis Type="Italic">k</Emphasis> disjoint constrained shortest paths

Let \(G=(V,\, E)\) be a given directed graph in which every edge e is associated with two nonnegative costs: a weight w(e) and a length l(e). For a pair of specified distinct vertices \(s,\, t\in V\), the k-(edge) disjoint constrained shortest path (kCSP) problem is to compute k (edge) disjoint paths between s and t, such that the total length of the paths is minimized and the weight is bounded by a given weight budget \(W\in \mathbb {R}_{0}^{+}\). The problem is known to be \({\mathcal {NP}}\)-hard, even when \(k=1\) (Garey and Johnson in Computers and intractability, 1979). Approximation algorithms with bifactor ratio \(\left( 1\,+\,\frac{1}{r},\, r\left( 1\,+\,\frac{2(\log r\,+\,1)}{r}\right) (1\,+\,\epsilon )\right) \) and \((1\,+\,\frac{1}{r},\,1\,+\,r)\) have been developed for \(k=2\) in Orda and Sprintson (IEEE INFOCOM, pp. 727–738, 2004) and Chao and Hong (IEICE Trans Inf Syst 90(2):465–472, 2007), respectively. For general k, an approximation algorithm with ratio \((1,\, O(\ln n))\) has been developed for a weaker version of kCSP, the k bi-constraint path problem which is to compute k disjoint st-paths satisfying a given length constraint and a weight constraint simultaneously (Guo et al. in COCOON, pp. 325–336, 2013). This paper first gives an approximation algorithm with bifactor ratio \((2,\,2)\) for kCSP using the LP-rounding technique. The algorithm is then improved by adopting a more sophisticated method to round edges. It is shown that for any solution output by the improved algorithm, there exists a real number \(0\le \alpha \le 2\) such that the weight and the length of the solution are bounded by \(\alpha \) times and \(2-\alpha \) times of that of an optimum solution, respectively. The key observation of the ratio proof is to show that the fractional edges, in a basic solution against the proposed linear relaxation of kCSP, exactly compose a graph in which the degree of every vertex is exactly two. At last, by a novel enhancement of the technique in Guo et al. (COCOON, pp. 325–336, 2013), the approximation ratio is further improved to \((1,\,\ln n)\).     

Characterizations of <Emphasis Type="Italic">k</Emphasis>-cutwidth critical trees

The cutwidth problem for a graph G is to embed G into a path such that the maximum number of overlap edges (i.e., the congestion) is minimized. The investigations of critical graphs and their structures are meaningful in the study of a graph-theoretic parameters. We study the structures of k-cutwidth \((k>1)\) critical trees, and use them to characterize the set of all 4-cutwidth critical trees.