An efficient algorithm for distance total domination in block graphs

The \(k\)-distance total domination problem is to find a minimum vertex set \(D\) of a graph such that every vertex of the graph is within distance \(k\) from some vertex of \(D\) other than itself, where \(k\) is a fixed positive integer. In the present paper, by using a labeling method, we design an efficient algorithm for solving the \(k\)-distance total domination problem on block graphs, a superclass of trees.     

Improved approximations for buy-at-bul and shallow-light $$$$-Steiner trees and $$(,2)$$(,2)-subgraph

In this paper we give improved approximation algorithms for some network design problems. In the bounded-diameter or shallow-light \(k\)-Steiner tree problem (SL\(k\)ST), we are given an undirected graph \(G=(V,E)\) with terminals \(T\subseteq V\) containing a root \(r\in T\), a cost function \(c:E\rightarrow \mathbb {R}^+\), a length function \(\ell :E\rightarrow \mathbb {R}^+\), a bound \(L>0\) and an integer \(k\ge 1\). The goal is to find a minimum \(c\)-cost \(r\)-rooted Steiner tree containing at least \(k\) terminals whose diameter under \(\ell \) metric is at most \(L\). The input to the buy-at-bulk \(k\)-Steiner tree problem (BB\(k\)ST) is similar: graph \(G=(V,E)\), terminals \(T\subseteq V\) containing a root \(r\in T\), cost and length functions \(c,\ell :E\rightarrow \mathbb {R}^+\), and an integer \(k\ge 1\). The goal is to find a minimum total cost \(r\)-rooted Steiner tree \(H\) containing at least \(k\) terminals, where the cost of each edge \(e\) is \(c(e)+\ell (e)\cdot f(e)\) where \(f(e)\) denotes the number of terminals whose path to root in \(H\) contains edge \(e\). We present a bicriteria \((O(\log ^2 n),O(\log n))\)-approximation for SL\(k\)ST: the algorithm finds a \(k\)-Steiner tree with cost at most \(O(\log ^2 n\cdot \text{ opt }^*)\) where \(\text{ opt }^*\) is the cost of an LP relaxation of the problem and diameter at most \(O(L\cdot \log n)\). This improves on the algorithm of Hajiaghayi et al. (2009) (APPROX’06/Algorithmica’09) which had ratio \((O(\log ^4 n), O(\log ^2 n))\). Using this, we obtain an \(O(\log ^3 n)\)-approximation for BB\(k\)ST, which improves upon the \(O(\log ^4 n)\)-approximation of Hajiaghayi et al. (2009). We also consider the problem of finding a minimum cost \(2\)-edge-connected subgraph with at least \(k\) vertices, which is introduced as the \((k,2)\)-subgraph problem in Lau et al. (2009) (STOC’07/SICOMP09). This generalizes some well-studied classical problems such as the \(k\)-MST and the minimum cost \(2\)-edge-connected subgraph problems. We give an \(O(\log n)\)-approximation algorithm for this problem which improves upon the \(O(\log ^2 n)\)-approximation algorithm of Lau et al. (2009).     

$$$$-labeling number of Cartesian product of path and cycle

For positive numbers \(j\) and \(k\), an \(L(j,k)\)-labeling \(f\) of \(G\) is an assignment of numbers to vertices of \(G\) such that \(|f(u)-f(v)|\ge j\) if \(d(u,v)=1\), and \(|f(u)-f(v)|\ge k\) if \(d(u,v)=2\). The span of \(f\) is the difference between the maximum and the minimum numbers assigned by \(f\). The \(L(j,k)\)-labeling number of \(G\), denoted by \(\lambda _{j,k}(G)\), is the minimum span over all \(L(j,k)\)-labelings of \(G\). In this article, we completely determine the \(L(j,k)\)-labeling number (\(2j\le k\)) of the Cartesian product of path and cycle.     

A greedy algorithm for the minimum 2-connected m-fold dominating set problem

To save energy and alleviate interference in a wireless sensor network, connected dominating set (CDS) has been proposed as the virtual backbone. Since nodes may fail due to accidental damage or energy depletion, it is desirable to construct a fault tolerant CDS, which can be modeled as a \(k\)-connected \(m\)-fold dominating set \(((k,m)\)-CDS for short): a subset of nodes \(C\subseteq V(G)\) is a \((k,m)\)-CDS of \(G\) if every node in \(V(G)\setminus C\) is adjacent with at least \(m\) nodes in \(C\) and the subgraph of \(G\) induced by \(C\) is \(k\)-connected.In this paper, we present an approximation algorithm for the minimum \((2,m)\)-CDS problem with \(m\ge 2\). Based on a \((1,m)\)-CDS, the algorithm greedily merges blocks until the connectivity is raised to two. The most difficult problem in the analysis is that the potential function used in the greedy algorithm is not submodular. By proving that an optimal solution has a specific decomposition, we managed to prove that the approximation ratio is \(\alpha +2(1+\ln \alpha )\), where \(\alpha \) is the approximation ratio for the minimum \((1,m)\)-CDS problem. This improves on previous approximation ratios for the minimum \((2,m)\)-CDS problem, both in general graphs and in unit disk graphs.     

OFDP: a distributed algorithm for finding disjoint paths with minimum total length in wireless sensor networks

This paper investigates the MINimum-length-\(k\)-Disjoint-Paths (MIN-\(k\)-DP) problem: in a sensor network, given two nodes \(s\) and \(t\), a positive integer \(k\), finding \(k\) (node) disjoint paths connecting \(s\) and \(t\) with minimum total length. An efficient distributed algorithm named Optimally-Finding-Disjoint-Paths (OFDP) is proposed for this problem. OFDP guarantees correctness and optimality, i.e., (1) it will find \(k\) disjoint paths if there exist \(k\) disjoint paths in the network or the maximum number of disjoint paths otherwise; (2) the disjoint paths it outputs do have minimum total length. To the best of our knowledge, OFDP is the first distributed algorithm that can solve the MIN-\(k\)-DP problem with correctness and optimality guarantee. Compared with the existing centralized algorithms which also guarantee correctness and optimality, OFDP is shown to be much more efficient by simulation results.     

2-Edge connected dominating sets and 2-Connected dominating sets of a graph

A \(k\)-connected (resp. \(k\)-edge connected) dominating set \(D\) of a connected graph \(G\) is a subset of \(V(G)\) such that \(G[D]\) is \(k\)-connected (resp. \(k\)-edge connected) and each \(v\in V(G)\backslash D\) has at least one neighbor in \(D\). The \(k\) -connected domination number (resp. \(k\) -edge connected domination number) of a graph \(G\) is the minimum size of a \(k\)-connected (resp. \(k\)-edge connected) dominating set of \(G\), and denoted by \(\gamma _k(G)\) (resp. \(\gamma '_k(G)\)). In this paper, we investigate the relation of independence number and 2-connected (resp. 2-edge-connected) domination number, and prove that for a graph \(G\), if it is \(2\)-edge connected, then \(\gamma '_2(G)\le 4\alpha (G)-1\), and it is \(2\)-connected, then \(\gamma _2(G)\le 6\alpha (G)-3\), where \(\alpha (G)\) is the independent number of \(G\).     

Bounding the scaling window of random constraint satisfaction problems

The model \(k\)-CSP is a random CSP model with moderately growing arity \(k\) of constraints. By incorporating certain linear structure, \(k\)-CSP is revised to a random linear CSP, named \(k\)-hyper-\({\mathbb F}\)-linear CSP. It had been shown theoretically that the two models exhibit exact satisfiability phase transitions when the constraint density \(r\) is varied accordingly. In this paper, we use finite-size scaling analysis to characterize the threshold behaviors of the two models with finite problem size \(n\). A series of experimental studies are carried out to illustrate the scaling window of the model \(k\)-CSP.     

Atoms of cyclic edge connectivity in regular graphs

A cyclic edge-cut of a connected graph \(G\) is an edge set, the removal of which separates two cycles. If \(G\) has a cyclic edge-cut, then it is called cyclically separable. For a cyclically separable graph \(G\), the cyclic edge connectivity of a graph \(G\), denoted by \(\lambda _c(G)\), is the minimum cardinality over all cyclic edge cuts. Let \(X\) be a non-empty proper subset of \(V(G)\). If \([X,\overline{X}]=\{xy\in E(G)\ |\ x\in X, y\in \overline{X}\}\) is a minimum cyclic edge cut of \(G\), then \(X\) is called a \(\lambda _c\) -fragment of \(G\). A \(\lambda _c\)-fragment with minimum cardinality is called a \(\lambda _c\) -atom. Let \(G\) be a \(k (k\ge 3)\)-regular cyclically separable graph with \(\lambda _c(G)<g(k-2)\), where \(g\) is the girth of \(G\). A combination of the results of Nedela and Skoviera (Math Slovaca 45:481–499, 1995) and Xu and Liu (Australas J Combin 30:41–49, 2004) gives that if \(k\ne 5\) then any two distinct \(\lambda _c\)-atoms of \(G\) are disjoint. The remaining case of \(k=5\) is considered in this paper, and a new proof for Nedela and ?koviera’s result is also given. As a result, we obtain the following result. If \(X\) and \(X'\) are two distinct \(\lambda _c\)-atoms of \(G\) such that \(X\cap X'\ne \emptyset \), then \((k,g)=(5,3)\) and \(G[X]\cong K_4\). As corollaries, several previous results are easily obtained.     

The extremal spectral radii of $$$$-uniform supertrees

In this paper, we study some extremal problems of three kinds of spectral radii of \(k\)-uniform hypergraphs (the adjacency spectral radius, the signless Laplacian spectral radius and the incidence \(Q\)-spectral radius). We call a connected and acyclic \(k\)-uniform hypergraph a supertree. We introduce the operation of “moving edges” for hypergraphs, together with the two special cases of this operation: the edge-releasing operation and the total grafting operation. By studying the perturbation of these kinds of spectral radii of hypergraphs under these operations, we prove that for all these three kinds of spectral radii, the hyperstar \(\mathcal {S}_{n,k}\) attains uniquely the maximum spectral radius among all \(k\)-uniform supertrees on \(n\) vertices. We also determine the unique \(k\)-uniform supertree on \(n\) vertices with the second largest spectral radius (for these three kinds of spectral radii). We also prove that for all these three kinds of spectral radii, the loose path \(\mathcal {P}_{n,k}\) attains uniquely the minimum spectral radius among all \(k\)-th power hypertrees of \(n\) vertices. Some bounds on the incidence \(Q\)-spectral radius are given. The relation between the incidence \(Q\)-spectral radius and the spectral radius of the matrix product of the incidence matrix and its transpose is discussed.     

On judicious partitions of graphs

Let \(k, m\) be positive integers, let \(G\) be a graph with \(m\) edges, and let \(h(m)=\sqrt{2m+\frac{1}{4}}-\frac{1}{2}\). Bollobás and Scott asked whether \(G\) admits a \(k\)-partition \(V_{1}, V_{2}, \ldots , V_{k}\) such that \(\max _{1\le i\le k} \{e(V_{i})\}\le \frac{m}{k^2}+\frac{k-1}{2k^2}h(m)\) and \(e(V_1, \ldots , V_k)\ge {k-1\over k} m +{k-1\over 2k}h(m) -\frac{(k-2)^{2}}{8k}\). In this paper, we present a positive answer to this problem on the graphs with large number of edges and small number of vertices with degrees being multiples of \(k\). Particularly, if \(d\) is not a multiple of \(k\) and \(G\) is \(d\)-regular with \(m\ge {9\over 128}k^4(k-2)^2\), then \(G\) admits a \(k\)-partition as desired. We also improve an earlier result by showing that \(G\) admits a partition \(V_{1}, V_{2}, \ldots , V_{k}\) such that \(e(V_{1},V_{2},\ldots ,V_{k})\ge \frac{k-1}{k}m+\frac{k-1}{2k}h(m)-\frac{(k-2)^{2}}{2(k-1)}\) and \(\max _{1\le i\le k}\{e(V_{i})\}\le \frac{m}{k^{2}}+\frac{k-1}{2k^{2}}h(m)\).     

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\).     

Neighbor sum distinguishing total coloring of graphs embedded in surfaces of nonnegative Euler characteristic

A total coloring of a graph \(G\) is a coloring of its vertices and edges such that adjacent or incident vertices and edges are not colored with the same color. A total \([k]\)-coloring of a graph \(G\) is a total coloring of \(G\) by using the color set \([k]=\{1,2,\ldots ,k\}\). Let \(f(v)\) denote the sum of the colors of a vertex \(v\) and the colors of all incident edges of \(v\). A total \([k]\)-neighbor sum distinguishing-coloring of \(G\) is a total \([k]\)-coloring of \(G\) such that for each edge \(uv\in E(G)\), \(f(u)\ne f(v)\). Let \(G\) be a graph which can be embedded in a surface of nonnegative Euler characteristic. In this paper, it is proved that the total neighbor sum distinguishing chromatic number of \(G\) is \(\Delta (G)+2\) if \(\Delta (G)\ge 14\), where \(\Delta (G)\) is the maximum degree of \(G\).     

L(2,1)-labelings of the edge-multiplicity-paths-replacement of a graph

An L(2,1)-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 \(2\), and the difference between labels of vertices that are distance two apart is at least 1. The span of an L(2,1)-labeling of a graph \(G\) is the difference between the maximum and minimum integers used by it. The minimum span of an L(2,1)-labeling of \(G\) is denoted by \(\lambda (G)\). This paper focuses on L(2,1)-labelings-number of the edge-multiplicity-paths-replacement \(G(rP_{k})\) of a graph \(G\). In this paper, we obtain that \( r\Delta +1 \le \lambda (G(rP_{5}))\le r\Delta +2\), \(\lambda (G(rP_{k}))= r\Delta +1\) for \(k\ge 6\); and \(\lambda (G(rP_{4}))\le (\Delta +1)r+1\), \(\lambda (G(rP_{3}))\le (\Delta +1)r+\Delta \) for any graph \(G\) with maximum degree \(\Delta \). And the L(2,1)-labelings-numbers of the edge-multiplicity-paths-replacement \(G(rP_{k})\) are completely determined for \(1\le \Delta \le 2\). And we show that the class of graphs \(G(rP_{k})\) with \(k\ge 3 \) satisfies the conjecture: \(\lambda ^{T}_{2}(G)\le \Delta +2\) by Havet and Yu (Technical Report 4650, 2002).     

A simple greedy approximation algorithm for the minimum connected $$$$-Center problem

In this paper, we consider the connected \(k\)-Center (\(CkC\)) problem, which can be seen as the classic \(k\)-Center problem with the constraint of internal connectedness, i.e., two nodes in a cluster are required to be connected by an internal path in the same cluster. \(CkC\) was first introduced by Ge et al. (ACM Trans Knowl Discov Data 2:7, 2008), in which they showed the \(NP\)-completeness for this problem and claimed a polynomial time approximation algorithm for it. However, the running time of their algorithm might not be polynomial, as one key step of their algorithm involves the computation of an \(NP\)-hard problem. We first present a simple polynomial time greedy-based \(2\)-approximation algorithm for the relaxation of \(CkC\)—the \(CkC^*\). Further, we give a \(6\)-approximation algorithm for \(CkC\).     

Equality in a bound that relates the size and the restrained domination number of a graph

Let \(G=(V,E)\) be a graph. A set \(S\subseteq V\) is a restrained dominating set if every vertex in \(V-S\) is adjacent to a vertex in \(S\) and to a vertex in \(V-S\). The restrained domination number of \(G\), denoted \(\gamma _{r}(G)\), is the smallest cardinality of a restrained dominating set of \(G\). The best possible upper bound \(q(n,k)\) is established in Joubert (Discrete Appl Math 161:829–837, 2013) on the size \(m(G)\) of a graph \(G\) with a given order \(n \ge 5\) and restrained domination number \(k \in \{3, \ldots , n-2\}\). We extend this result to include the cases \(k=1,2,n\), and characterize graphs \(G\) of order \(n \ge 1\) and restrained domination number \(k \in \{1,\dots , n-2,n\}\) for which \(m(G)=q(n,k)\).     

A proper total coloring distinguishing adjacent vertices by sums of planar graphs without intersecting triangles

Let \(G=(V,E)\) be a graph and \(\phi \) be a total \(k\)-coloring of \(G\) using the color set \(\{1,\ldots , k\}\). Let \(\sum _\phi (u)\) denote the sum of the color of the vertex \(u\) and the colors of all incident edges of \(u\). A \(k\)-neighbor sum distinguishing total coloring of \(G\) is a total \(k\)-coloring of \(G\) such that for each edge \(uv\in E(G)\), \(\sum _\phi (u)\ne \sum _\phi (v)\). By \(\chi ^{''}_{nsd}(G)\), we denote the smallest value \(k\) in such a coloring of \(G\). Pil?niak and Wo?niak first introduced this coloring and conjectured that \(\chi _{nsd}^{''}(G)\le \Delta (G)+3\) for any simple graph \(G\). In this paper, we prove that the conjecture holds for planar graphs without intersecting triangles with \(\Delta (G)\ge 7\). Moreover, we also show that \(\chi _{nsd}^{''}(G)\le \Delta (G)+2\) for planar graphs without intersecting triangles with \(\Delta (G) \ge 9\). Our approach is based on the Combinatorial Nullstellensatz and the discharging method.     

The 2-surviving rate of planar graphs without 5-cycles

Let \(G\) be a connected graph with \(n\ge 2\) vertices. Let \(k\ge 1\) be an integer. Suppose that a fire breaks out at a vertex \(v\) of \(G\). A firefighter starts to protect vertices. At each step, the firefighter protects \(k\)-vertices not yet on fire. At the end of each step, the fire spreads to all the unprotected vertices that have a neighbour on fire. Let \(\hbox {sn}_k(v)\) denote the maximum number of vertices in \(G\) that the firefighter can save when a fire breaks out at vertex \(v\). The \(k\)-surviving rate \(\rho _k(G)\) of \(G\) is defined to be \(\frac{1}{n^2}\sum _{v\in V(G)} {\hbox {sn}}_{k}(v)\), which is the average proportion of saved vertices. In this paper, we prove that if \(G\) is a planar graph with \(n\ge 2\) vertices and without 5-cycles, then \(\rho _2(G)>\frac{1}{363}\).     

Approximation algorithms for minimum weight partial connected set cover problem

In the Minimum Weight Partial Connected Set Cover problem, we are given a finite ground set \(U\), an integer \(q\le |U|\), a collection \(\mathcal {E}\) of subsets of \(U\), and a connected graph \(G_{\mathcal {E}}\) on vertex set \(\mathcal {E}\), the goal is to find a minimum weight subcollection of \(\mathcal {E}\) which covers at least \(q\) elements of \(U\) and induces a connected subgraph in \(G_{\mathcal {E}}\). In this paper, we derive a “partial cover property” for the greedy solution of the Minimum Weight Set Cover problem, based on which we present (a) for the weighted version under the assumption that any pair of sets in \(\mathcal {E}\) with nonempty intersection are adjacent in \(G_{\mathcal {E}}\) (the Minimum Weight Partial Connected Vertex Cover problem falls into this range), an approximation algorithm with performance ratio \(\rho (1+H(\gamma ))+o(1)\), and (b) for the cardinality version under the assumption that any pair of sets in \(\mathcal {E}\) with nonempty intersection are at most \(d\)-hops away from each other (the Minimum Partial Connected \(k\)-Hop Dominating Set problem falls into this range), an approximation algorithm with performance ratio \(2(1+dH(\gamma ))+o(1)\), where \(\gamma =\max \{|X|:X\in \mathcal {E}\}\), \(H(\cdot )\) is the Harmonic number, and \(\rho \) is the performance ratio for the Minimum Quota Node-Weighted Steiner Tree problem.     

On the vertex cover $$P_3$$ problem parameterized by treewidth

Consider a graph G. A subset of vertices, F, is called a vertex cover \(P_t\) (\(VCP_t\)) set if every path of order t contains at least one vertex in F. Finding a minimum \(VCP_t\) set in a graph is is NP-hard for any integer \(t\ge 2\) and is called the \(MVCP_3\) problem. In this paper, we study the parameterized algorithms for the \(MVCP_3\) problem when the underlying graph G is parameterized by the treewidth. Given an n-vertex graph together with its tree decomposition of width at most p, we present an algorithm running in time \(4^{p}\cdot n^{O(1)}\) for the \(MVCP_3\) problem. Moreover, we show that for the \(MVCP_3\) problem on planar graphs, there is a subexponential parameterized algorithm running in time \(2^{O(\sqrt{k})}\cdot n^{O(1)}\) where k is the size of the optimal solution.