Long cycles in hypercubes with optimal number of?faulty vertices

Let f(n) be the maximum integer such that for every set F of at most f(n) vertices of the hypercube Q _n , there exists a cycle of length at least 2 ⁿ ?2|F| in Q _n ?F. Casta?eda and Gotchev conjectured that $f(n)=\binom{n}{2}-2$ . We prove this conjecture. We also prove that for every set F of at most (n ²+n?4)/4 vertices of Q _n , there exists a path of length at least 2 ⁿ ?2|F|?2 in Q _n ?F between any two vertices such that each of them has at most 3 neighbors in F. We introduce a new technique of potentials which could be of independent interest.     

Approximation algorithm for uniform bounded facility location problem

The uniform bounded facility location problem (UBFLP) seeks for the optimal way of locating facilities to minimize total costs (opening costs plus routing costs), while the maximal routing costs of all clients are at most a given bound M. After building a mixed 0–1 integer programming model for UBFLP, we present the first constant-factor approximation algorithm with an approximation guarantee of 6.853+? for UBFLP on plane, which is composed of the algorithm by Dai and Yu (Theor. Comp. Sci. 410:756–765, 2009) and the schema of Xu and Xu (J. Comb. Optim. 17:424–436, 2008). We also provide a heuristic algorithm based on Benders decomposition to solve UBFLP on general graphes, and the computational experience shows that the heuristic works well.     

A note on anti-coordination and social interactions

This note confirms a conjecture of (Bramoullé in Games Econ Behav 58:30–49, 2007). The problem, which we name the maximum independent cut problem, is a restricted version of the MAX-CUT problem, requiring one side of the cut to be an independent set. We show that the maximum independent cut problem does not admit any polynomial time algorithm with approximation ratio better than n ^1?? , where n is the number of nodes, and ? arbitrarily small, unless $\mathrm{P} = \mathrm{NP}$ . For the rather special case where each node has a degree of at most four, the problem is still APX-hard.     

(p,q)-total labeling of complete graphs

Given a graph G and positive integers p,q with p≥q, the (p,q)-total number $\lambda_{p,q}^{T}(G)$ of G is the width of the smallest range of integers that suffices to label the vertices and the edges of G such that the labels of any two adjacent vertices are at least q apart, the labels of any two adjacent edges are at least q apart, and the difference between the labels of a vertex and its incident edges is at least p. Havet and Yu (Discrete Math 308:496–513, 2008) first introduced this problem and determined the exact value of $\lambda_{p,1}^{T}(K_{n})$ except for even n with p+5≤n≤6p ²?10p+4. Their proof for showing that $\lambda _{p,1}^{T}(K_{n})\leq n+2p-3$ for odd n has some mistakes. In this paper, we prove that if n is odd, then $\lambda_{p}^{T}(K_{n})\leq n+2p-3$ if p=2, p=3, or $4\lfloor\frac{p}{2}\rfloor+3\leq n\leq4p-1$ . And we extend some results that were given in Havet and Yu (Discrete Math 308:496–513, 2008). Beside these, we give a lower bound for $\lambda_{p,q}^{T}(K_{n})$ under the condition that q<p<2q.     

A note on fault-free mutually independent Hamiltonian cycles in hypercubes with faulty edges

In the paper “Fault-free Mutually Independent Hamiltonian Cycles in Hypercubes with Faulty Edges” (J. Comb. Optim. 13:153–162, 2007), the authors claimed that an n-dimensional hypercube can be embedded with (n−1−f)-mutually independent Hamiltonian cycles when f≤n−2 faulty edges may occur accidentally. However, there are two mistakes in their proof. In this paper, we give examples to explain why the proof is deficient. Then we present a correct proof. This work was supported in part by the National Science Council of the Republic of China under Contract NSC 95-2221-E-233-002.     

A primal-dual approximation algorithm for the Asymmetric Prize-Collecting TSP

We present a primal-dual ?log(n)?-approximation algorithm for the version of the asymmetric prize collecting traveling salesman problem, where the objective is to find a directed tour that visits a subset of vertices such that the length of the tour plus the sum of penalties associated with vertices not in the tour is as small as possible. The previous algorithm for the problem (V.H. Nguyen and T.T Nguyen in Int. J. Math. Oper. Res. 4(3):294–301, 2012) which is not combinatorial, is based on the Held-Karp relaxation and heuristic methods such as the Frieze et al.’s heuristic (Frieze et al. in Networks 12:23–39, 1982) or the recent Asadpour et al.’s heuristic for the ATSP (Asadpour et al. in 21st ACM-SIAM symposium on discrete algorithms, 2010). Depending on which of the two heuristics is used, it gives respectively 1+?log(n)? and $3+ 8\frac{\log(n)}{\log(\log(n))}$ as an approximation ratio. Our algorithm achieves an approximation ratio of ?log(n)? which is weaker than $3+ 8\frac{\log(n)}{\log(\log(n))}$ but represents the first combinatorial approximation algorithm for the Asymmetric Prize-Collecting TSP.     

An improved distributed data aggregation scheduling in wireless sensor networks

This paper focuses on the distributed data aggregation collision-free scheduling problem, which is one of very important issues in wireless sensor networks. Bo et al. (Proc. IEEE INFOCOM, 2009) proposed an approximate distributed algorithm for the problem and Xu et al. (Proc. ACM FOWANC, 2009) proposed a centralized algorithm and its distributed implementation to generate a collision-free scheduling for the problem, which are the only two existing distributed algorithms. Unfortunately, there are a few mistakes in their performance analysis in Bo et al. (Proc. IEEE INFOCOM, 2009), and the distributed algorithm can not get the same latency as the centralized algorithm because the distributed implementation was not an accurate implementation of the centralized algorithm (Xu et al. in Proc. ACM FOWANC, 2009). According to those, we propose an improved distributed algorithm to generate a collision-free schedule for data aggregation in wireless sensor networks. Not an arbitrary tree in Bo et al. (Proc. IEEE INFOCOM, 2009) but a breadth first search tree (BFS) rooted at the sink node is adopted, the bounded latency 61R+5Δ?67 of the schedule is obtained, where R is the radius of the network with respect to the sink node and Δ is the maximum node degree. We also correct the latency bound of the schedule in Bo et al. (Proc. IEEE INFOCOM, 2009) as 61D+5Δ?67, where D is a diameter of the network and prove that our algorithm is more efficient than the algorithm (Bo et al. in Proc. IEEE INFOCOM, 2009). We also give a latency bound for the distributed implementation in Xu et al. (Proc. ACM FOWANC, 2009).     

Independent dominating sets in regular graphs

Let G be a simple, regular graph of order n and degree δ. The independent domination number i(G) is defined to be the minimum cardinality among all maximal independent sets of vertices of G. We establish new upper bounds, as functions of n and δ, for the independent domination number of regular graphs with $n/6<\delta< (3-\sqrt{5})n/2$ . Our two main theorems complement recent results of Goddard et al. (Ann. Comb., 2011) for larger values of δ.     

A new approximation algorithm for the Selective Single-Sink Buy-at-Bulk problem in network design

The Selective Single-Sink Buy-at-Bulk problem was proposed by Awerbuch and Azar (FOCS 1997). For a long time, the only known non-trivial approach to approximate this problem is the tree-embedding method initiated by Bartal (FOCS 1996). In this paper, we give a thoroughly different approximation approach for the problem with approximation ratio $O(\sqrt{q})$ , where q is the number of source terminals in the problem instance. Our approach is based on a mixed strategy of LP-rounding and the greedy method. When the number q (which is always at most n) is relatively small (say, q=o(log² n)), our approximation ratio $O(\sqrt{q})$ is better than the currently known best ratio O(logn), where n is the number of vertices in the input graph.     

The paths embedding of the arrangement graphs with prescribed vertices in given position

Let n and k be positive integers with n?k≥2. The arrangement graph A _n,k is recognized as an attractive interconnection networks. Let x, y, and z be three different vertices of A _n,k . Let l be any integer with $d_{A_{n,k}}(\mathbf{x},\mathbf{y}) \le l \le \frac{n!}{(n-k)!}-1-d_{A_{n,k}}(\mathbf{y},\mathbf{z})$ . We shall prove the following existance properties of Hamiltonian path: (1)?for n?k≥3 or (n,k)=(3,1), there exists a Hamiltonian path R(x,y,z;l) from x to z such that d _R(x,y,z;l)(x,y)=l; (2) for n?k=2 and n≥5, there exists a Hamiltonian path R(x,y,z;l) except for the case that x, y, and z are adjacent to each other.     

Are there more almost separable partitions than separable partitions?

A partition of a set of n points in d-dimensional space into p parts is called an (almost) separable partition if the convex hulls formed by the parts are (almost) pairwise disjoint. These two partition classes are the most encountered ones in clustering and other partition problems for high-dimensional points and their usefulness depends critically on the issue whether their numbers are small. The problem of bounding separable partitions has been well studied in the literature (Alon and Onn in Discrete Appl. Math. 91:39–51, 1999; Barnes et al. in Math. Program. 54:69–86, 1992; Harding in Proc. Edinb. Math. Soc. 15:285–289, 1967; Hwang et al. in SIAM J. Optim. 10:70–81, 1999; Hwang and Rothblum in J. Comb. Optim. 21:423–433, 2011a). In this paper, we prove that for d≤2 or p≤2, the maximum number of almost separable partitions is equal to the maximum number of separable partitions.     

Shifting strategy for geometric graphs without?geometry

We give a simple framework which is an alternative to the celebrated and widely used shifting strategy of Hochbaum and Maass (J. ACM 32(1):103?C136, 1985) which has yielded efficient algorithms with good approximation bounds for numerous optimization problems in low-dimensional Euclidean space. Our framework does not require the input graph/metric to have a geometric realization??it only requires that the input graph satisfy some weak property referred to as growth boundedness. Growth bounded graphs form an important graph class that has been used to model wireless networks. We show how to apply the framework to obtain a polynomial time approximation scheme (PTAS) for the maximum (weighted) independent set problem on this important graph class; the problem is W[1]-complete. Via a more sophisticated application of our framework, we show how to obtain a PTAS for the maximum (weighted) independent set for intersection graphs of (low-dimensional) fat objects that are expressed without geometry. Erlebach et al. (SIAM J. Comput. 34(6):1302?C1323, 2005) and Chan (J. Algorithms 46(2):178?C189, 2003) independently gave a PTAS for maximum weighted independent set problem for intersection graphs of fat geometric objects, say ball graphs, which required a geometric representation of the input. Our result gives a positive answer to a question of Erlebach et al. (SIAM J. Comput. 34(6):1302?C1323, 2005) who asked if a PTAS for this problem can be obtained without access to a geometric representation.     

L(d,1)-labelings of the edge-path-replacement of a graph

For two positive integers j and k with j≥k, an L(j,k)-labeling of a graph G is an assignment of nonnegative integers to V(G) such that the difference between labels of adjacent vertices is at least j, and the difference between labels of vertices that are distance two apart is at least k. The span of an L(j,k)-labeling of a graph G is the difference between the maximum and minimum integers used by it. The L(j,k)-labelings-number of G is the minimum span over all L(j,k)-labelings of G. This paper focuses on L(d,1)-labelings-number of the edge-path-replacement G(P _k ) of a graph G. Note that G(P ₃) is the incidence graph of G. L(d,1)-labelings of the edge-path-replacement G(P _k ) of a graph, called (d,1)-total labeling of G, was introduced in 2002 by Havet and Yu (Workshop graphs and algorithms, 2003; Discrete Math 308:493–513, 2008). Havet and Yu (Discrete Math 308:498–513, 2008) obtained the bound $\Delta+ d-1\leq\lambda^{T}_{d}(G)\leq2\Delta+ d-1$ and conjectured $\lambda^{T}_{d}(G)\leq\Delta+2d-1$ . In (Lü in J Comb Optim, to appear; Zhejiang University, submitted), we worked on L(2,1)-labelings-number and L(1,1)-labelings-number of the edge-path-replacement G(P _k ) of a graph G, and obtained that λ(G(P _k ))≤Δ+2 for k≥5, and conjecture λ(G(P ₄))≤Δ+2 for any graph G with maximum degree Δ. In this paper, we will study L(d,1)-labelings-number of the edge-path-replacement G(P _k ) of a graph G for d≥3 and k≥4.     

Acyclic edge coloring of planar graphs without 4-cycles

An acyclic edge coloring of a graph G is a proper edge coloring such that no bichromatic cycles are produced. The acyclic chromatic index a′(G) of G is the smallest integer k such that G has an acyclic edge coloring using k colors. Fiam?ik (Math. Slovaca 28:139–145, 1978) and later Alon, Sudakov and Zaks (J. Graph Theory 37:157–167, 2001) conjectured that a′(G)≤Δ+2 for any simple graph G with maximum degree Δ. In this paper, we confirm this conjecture for planar graphs G with Δ≠4 and without 4-cycles.     

Acyclic edge coloring of planar graphs without a 3-cycle adjacent to a 6-cycle

An acyclic edge coloring of a graph \(G\) is a proper edge coloring such that no bichromatic cycles are produced. The acyclic chromatic index \(a'(G)\) of \(G\) is the smallest integer \(k\) such that \(G\) has an acyclic edge coloring using \(k\) colors. Fiam? ik (Math Slovaca 28:139–145, 1978) and later Alon et al. (J Graph Theory 37:157–167, 2001) conjectured that \(a'(G)\le \Delta +2\) for any simple graph \(G\) with maximum degree \(\Delta \) . In this paper, we confirm this conjecture for planar graphs without a \(3\) -cycle adjacent to a \(6\) -cycle.     

Minimum degree, edge-connectivity and radius

Let G be a connected graph on n≥4 vertices with minimum degree δ and radius r. Then $\delta r\leq4\lfloor\frac{n}{2}\rfloor-4$ , with equality if and only if one of the following holds:

1. G is K ₅,
2. G?K _n ?M, where M is a perfect matching, if n is even,
3. δ=n?3 and Δ≤n?2, if n is odd.

This solves a conjecture on the product of the edge-connectivity and radius of a graph, which was posed by Sedlar, Vuki?evi?, Aouchice, and Hansen.     

FPT algorithms for Connected Feedback Vertex Set

We study the recently introduced Connected Feedback Vertex Set (CFVS) problem from the view-point of parameterized algorithms. CFVS is the connected variant of the classical Feedback Vertex Set problem and is defined as follows: given a graph G=(V,E) and an integer k, decide whether there exists F?V, |F|??k, such that G[V?F] is a forest and G[F] is connected. We show that Connected Feedback Vertex Set can be solved in time O(2 ^O(k) n ^O(1)) on general graphs and in time $O(2^{O(\sqrt{k}\log k)}n^{O(1)})$ on graphs excluding a fixed graph H as a minor. Our result on general undirected graphs uses, as a subroutine, a parameterized algorithm for Group Steiner Tree, a well studied variant of Steiner Tree. We find the algorithm for Group Steiner Tree of independent interest and believe that it could be useful for obtaining parameterized algorithms for other connectivity problems.     

Equivalence of two conjectures on equitable coloring of graphs

A graph G is said to be equitably k-colorable if there exists a proper k-coloring of G such that the sizes of any two color classes differ by at most one. Let Δ(G) denote the maximum degree of a vertex in G. Two Brooks-type conjectures on equitable Δ(G)-colorability have been proposed in Chen and Yen (Discrete Math., 2011) and Kierstead and Kostochka (Combinatorica 30:201–216, 2010) independently. We prove the equivalence of these conjectures.     

Some results on the target set selection problem

In this paper we consider a fundamental problem in the area of viral marketing, called Target Set Selection problem. We study the problem when the underlying graph is a block-cactus graph, a chordal graph or a Hamming graph. We show that if G is a block-cactus graph, then the Target Set Selection problem can be solved in linear time, which generalizes Chen’s result (Discrete Math. 23:1400–1415, 2009) for trees, and the time complexity is much better than the algorithm in Ben-Zwi et al. (Discrete Optim., 2010) (for bounded treewidth graphs) when restricted to block-cactus graphs. We show that if the underlying graph G is a chordal graph with thresholds θ(v)≤2 for each vertex v in G, then the problem can be solved in linear time. For a Hamming graph G having thresholds θ(v)=2 for each vertex v of G, we precisely determine an optimal target set S for (G,θ). These results partially answer an open problem raised by Dreyer and Roberts (Discrete Appl. Math. 157:1615–1627, 2009).     

Fault-free mutually independent Hamiltonian cycles in hypercubes with faulty edges

Two Hamiltonian paths are said to be fully independent if the ith vertices of both paths are distinct for all i between 1 and n, where n is the number of vertices of the given graph. Hamiltonian paths in a set are said to be mutually fully independent if two arbitrary Hamiltonian paths in the set are fully independent. On the other hand, two Hamiltonian cycles are independent starting at v if both cycles start at a common vertex v and the ith vertices of both cycles are distinct for all i between 2 and n. Hamiltonian cycles in a set are said to be mutually independent starting at v if any two different cycles in the set are independent starting at v. The n-dimensional hypercube is widely used as the architecture for parallel machines. In this paper, we study its fault-tolerant property and show that an n-dimensional hypercube with at most n−2 faulty edges can embed a set of fault-free mutually fully independent Hamiltonian paths between two adjacent vertices, and can embed a set of fault-free mutually independent Hamiltonian cycles starting at a given vertex. The number of tolerable faulty edges is optimal with respect to a worst case. An extended abstract of this paper appeared in Proceedings of the 2006 International Conference on Innovative Computing, Information and Control (ICICIC), pp. 288–292, IEEE Computer Society Press.