A practical greedy approximation for the directed Steiner tree problem

The directed Steiner tree (DST) NP-hard problem asks, considering a directed weighted graph with n nodes and m arcs, a node r called root and a set of k nodes X called terminals, for a minimum cost directed tree rooted at r spanning X. The best known polynomial approximation ratio for DST is a \(O(k^\varepsilon )\)-approximation greedy algorithm. However, a much faster k-approximation, returning the shortest paths from r to X, is generally used in practice. We give two new algorithms : a fast k-approximation called Greedy\(_\text {FLAC}\) running in \(O(m \log (n)k + \min (m, nk)nk^2)\) and a \(O(\sqrt{k})\)-approximation called Greedy\(_\text {FLAC}^\triangleright \) running in \(O(nm + n^2 \log (n)k +n^2 k^3)\). We provide computational results to show that, Greedy\(_\text {FLAC}\) rivals in practice with the running time of the fast k-approximation and returns solution with smaller cost in practice.     

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

First-Fit colorings of graphs with no cycles of a prescribed even length

The First-Fit (or Grundy) chromatic number of a graph G denoted by \(\chi _{{_\mathsf{FF}}}(G)\), is the maximum number of colors used by the First-Fit (greedy) coloring algorithm when applied to G. In this paper we first show that any graph G contains a bipartite subgraph of Grundy number \(\lfloor \chi _{{_\mathsf{FF}}}(G) /2 \rfloor +1\). Using this result we prove that for every \(t\ge 2\) there exists a real number \(c>0\) such that in every graph G on n vertices and without cycles of length 2t, any First-Fit coloring of G uses at most \(cn^{1/t}\) colors. It is noted that for \(t=2\) this bound is the best possible. A compactness conjecture is also proposed concerning the First-Fit chromatic number involving the even girth of graphs.     

1.61-approximation for min-power strong connectivity with two power levels

Given a directed simple graph \(G=(V,E)\) and a cost function \(c:E \rightarrow R_+\), the power of a vertex \(u\) in a directed spanning subgraph \(H\) is given by \(p_H(u) = \max _{uv \in E(H)} c(uv)\), and corresponds to the energy consumption required for wireless node \(u\) to transmit to all nodes \(v\) with \(uv \in E(H)\). The power of \(H\) is given by \(p(H) = \sum _{u \in V} p_H(u)\). Power Assignment seeks to minimize \(p(H)\) while \(H\) satisfies some connectivity constraint. In this paper, we assume \(E\) is bidirected (for every directed edge \(e \in E\), the opposite edge exists and has the same cost), while \(H\) is required to be strongly connected. Moreover, we assume \(c:E \rightarrow \{A,B\}\), where \(0 \le A < B\). We improve the best known approximation ratio from 1.75 (Chen et al. IEEE GLOBECOM 2005) to \(\pi ^2/6 - 1/36 + \epsilon \le 1.61\) using an adaptation of the algorithm developed by Khuller et al. [SIAM J Comput 24(4):859–872 1995, Discr Appl Math 69(3):281–289 1996] for (unweighted) Minimum Strongly Connected Subgraph.     

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

Further properties on the degree distance of graphs

In this paper, we study the degree distance of a connected graph \(G\), defined as \(D^{'} (G)=\sum _{u\in V(G)} d_{G} (u)D_{G} (u)\), where \(D_{G} (u)\) is the sum of distances between the vertex \(u\) and all other vertices in \(G\) and \(d_{G} (u)\) denotes the degree of vertex \(u\) in \(G\). Our main purpose is to investigate some properties of degree distance. We first investigate degree distance of tensor product \(G\times K_{m_0,m_1,\cdots ,m_{r-1}}\), where \(K_{m_0,m_1,\cdots ,m_{r-1}}\) is the complete multipartite graph with partite sets of sizes \(m_0,m_1,\cdots ,m_{r-1}\), and we present explicit formulas for degree distance of the product graph. In addition, we give some Nordhaus–Gaddum type bounds for degree distance. Finally, we compare the degree distance and eccentric distance sum for some graph families.     

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.     

Neighbor sum distinguishing total choosability of planar graphs

A total-k-coloring of a graph G is a mapping \(c: V(G)\cup E(G)\rightarrow \{1, 2,\dots , k\}\) such that any two adjacent or incident elements in \(V(G)\cup E(G)\) receive different colors. For a total-k-coloring of G, let \(\sum _c(v)\) denote the total sum of colors of the edges incident with v and the color of v. If for each edge \(uv\in E(G)\), \(\sum _c(u)\ne \sum _c(v)\), then we call such a total-k-coloring neighbor sum distinguishing. The least number k needed for such a coloring of G is the neighbor sum distinguishing total chromatic number, denoted by \(\chi _{\Sigma }^{''}(G)\). Pil?niak and Wo?niak conjectured \(\chi _{\Sigma }^{''}(G)\le \Delta (G)+3\) for any simple graph with maximum degree \(\Delta (G)\). In this paper, we prove that for any planar graph G with maximum degree \(\Delta (G)\), \(ch^{''}_{\Sigma }(G)\le \max \{\Delta (G)+3,16\}\), where \(ch^{''}_{\Sigma }(G)\) is the neighbor sum distinguishing total choosability of G.     

Bounding the total domination subdivision number of a graph in terms of its order

The total domination subdivision number \(\mathrm{sd}_{\gamma _{t}}(G)\) of a graph G is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the total domination number. In this paper we prove that \(\mathrm{sd}_{\gamma_{t}}(G)\leq \lfloor\frac{2n}{3}\rfloor\) for any simple connected graph G of order n≥3 other than K ₄. We also determine all simple connected graphs G with \(\mathrm{sd}_{\gamma_{t}}(G)=\lfloor\frac{2n}{3}\rfloor\).     

On the efficiency index of a graph

A graph \(G\) has an efficient dominating set \(D \subseteq V(G)\) if \(D\) dominates every vertex exactly once. In this paper we introduce the study of the family \({S_k}\) of graphs for which every \(G-S\) is efficiently dominatable for \(0 \le |S|\le k\). Assuming that \(G\) is efficiently dominatable, the efficiency index is the largest value k for which \(G\) is in \(S_k\). A graph \(G\) will be called super-efficient if every induced subgraph is efficiently dominatable. We give some characterizations for trees, grids, cylinders and torii to be super-efficient.     

On strongly planar not-all-equal 3SAT

In this paper we show that there is a polynomial time algorithm for the strongly planar not-all-equal 3SAT problem. Also, we prove that a restricted version of planar not-all-equal 3SAT is \( \mathbf {NP} \)-complete and in consequence of this result, we show that for a given planar bipartite graph \(G\), deciding whether there is a vertex-labeling by gap from \(\{1,2\}\) such that the induced proper coloring is a proper vertex 2-coloring is \( \mathbf {NP} \)-complete.     

An improved approximation algorithm for the shortest link scheduling in wireless networks under SINR and hypergraph models

Link scheduling is a fundamental problem in wireless ad hoc and sensor networks. In this paper, we focus on the shortest link scheduling (SLS) under Signal-to-Interference-plus-Noise-Ratio and hypergraph models, and propose an approximation algorithm \(SLS_{pc}\) (A link scheduling algorithm with oblivious power assignment for the shortest link scheduling) with oblivious power assignment for better performance than GOW* proposed by Blough et al. [IEEE/ACM Trans Netw 18(6):1701–1712, 2010]. For the average scheduling length of \(SLS_{pc}\) is 1 / m of GOW*, where \(m=\lfloor \varDelta _{max}\cdot p \rfloor \) is the expected number of the links in the set V returned by the algorithm HyperMaxLS (Maximal links schedule under hypergraph model) and \(0<p<1\) is the constant. In the worst, ideal and average cases, the ratios of time complexity of our algorithm \(SLS_{pc}\) to that of GOW* are \(O(\varDelta _{max}/\overline{k})\), \(O(1/(\overline{k}\cdot \varDelta _{max}))\) and \(O(\varDelta _{max}/(\overline{k}\cdot m))\), respectively. Where \(\overline{k}\) (\(1<\overline{k}<\varDelta _{max}\)) is a constant called the SNR diversity of an instance G.     

Online tradeoff scheduling on a single machine to minimize makespan and maximum lateness

In this paper, we consider the following single machine online tradeoff scheduling problem. A set of n independent jobs arrive online over time. Each job \(J_{j}\) has a release date \(r_{j}\), a processing time \(p_{j}\) and a delivery time \(q_{j}\). The characteristics of a job are unknown until it arrives. The goal is to find a schedule that minimizes the makespan \(C_{\max } = \max _{1 \le j \le n} C_{j}\) and the maximum lateness \(L_{\max } = \max _{1 \le j \le n} L_{j}\), where \(L_{j} = C_{j} + q_{j}\). For the problem, we present a nondominated \(( \rho , 1 + \displaystyle \frac{1}{\rho } )\)-competitive online algorithm for each \(\rho \) with \( 1 \le \rho \le \displaystyle \frac{\sqrt{5} + 1}{2}\).     

A $$(3,1)^{*}$$-choosable theorem on planar graphs

A list assignment of a graph G is a function L that assigns a list L(v) of colors to each vertex \(v\in V(G)\). An \((L,d)^*\)-coloring is a mapping \(\pi \) that assigns a color \(\pi (v)\in L(v)\) to each vertex \(v\in V(G)\) so that at most d neighbors of v receive color \(\pi (v)\). A graph G is said to be \((k,d)^*\)-choosable if it admits an \((L,d)^*\)-coloring for every list assignment L with \(|L(v)|\ge k\) for all \(v\in V(G)\). In this paper, we prove that every planar graph with neither adjacent triangles nor 6-cycles is \((3,1)^*\)-choosable. This is a partial answer to a question of Xu and Zhang (Discret Appl Math 155:74–78, 2007) that every planar graph without adjacent triangles is \((3,1)^*\)-choosable. Also, this improves a result in Lih et al. (Appl Math Lett 14:269–273, 2001) which says that every planar graph without 4- and 6-cycles is \((3,1)^*\)-choosable.     

Semi-online scheduling on two uniform machines with the known largest size

This paper investigates semi-online scheduling on two uniform machines with the known largest size. Denote by s _j the speed of each machine, j=1,2. Assume 0<s ₁≤s ₂, and let s=s ₂/s ₁ be the speed ratio. First, for the speed ratio \(s\in [1,\sqrt{2}]\), we present an optimal semi-online algorithm \(\mathcal{LSMP}\) with the competitive ratio \(\mathrm{max}\{\frac {2(s+1)}{2s+1},s\}\). Second, we present a semi-online algorithm \(\mathcal{HSMP}\). And for \(s\in(\sqrt{2},1+\sqrt{3})\), the competitive ratio of \(\mathcal{HSMP}\) is strictly smaller than that of the online algorithm \(\mathcal{LS}\). Finally, for the speed ratio s≥s ^*≈3.715, we show that the known largest size cannot help us to design a semi-online algorithm with the competitive ratio strictly smaller than that of \(\mathcal{LS}\). Moreover, we show a lower bound for \(s\in(\sqrt{2},s^{*})\).     

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

Towards the price of leasing online

We consider online optimization problems in which certain goods have to be acquired in order to provide a service or infrastructure. Classically, decisions for such problems are considered as final: one buys the goods. However, in many real world applications, there is a shift away from the idea of buying goods. Instead, leasing is often a more flexible and lucrative business model. Research has realized this shift and recently initiated the theoretical study of leasing models (Anthony and Gupta in Proceedings of the integer programming and combinatorial optimization: 12th International IPCO Conference, Ithaca, NY, USA, June 25–27, 2007; Meyerson in Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 23–25 Oct 2005, Pittsburgh, PA, USA, 2005; Nagarajan and Williamson in Discret Optim 10(4):361–370, 2013) We extend this line of work and suggest a more systematic study of leasing aspects for a class of online optimization problems. We provide two major technical results. We introduce the leasing variant of online set multicover and give an \(O\left( \log (mK)\log n\right) \)-competitive algorithm (with n, m, and K being the number of elements, sets, and leases, respectively). Our results also imply improvements for the non-leasing variant of online set cover. Moreover, we extend results for the leasing variant of online facility location. Nagarajan and Williamson (Discret Optim 10(4):361–370, 2013) gave an \(O\left( K\log n\right) \)-competitive algorithm for this problem (with n and K being the number of clients and leases, respectively). We remove the dependency on n (and, thereby, on time). In general, this leads to a bound of \(O\left( l_{\text {max}} \log l_{\text {max}} \right) \) (with the maximal lease length \(l_{\text {max}} \)). For many natural problem instances, the bound improves to \(O\left( K^2\right) \).     

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

Reconfiguration of dominating sets

We explore a reconfiguration version of the dominating set problem, where a dominating set in a graph G is a set S of vertices such that each vertex is either in S or has a neighbour in S. In a reconfiguration problem, the goal is to determine whether there exists a sequence of feasible solutions connecting given feasible solutions s and t such that each pair of consecutive solutions is adjacent according to a specified adjacency relation. Two dominating sets are adjacent if one can be formed from the other by the addition or deletion of a single vertex. For various values of k, we consider properties of \(D_k(G)\), the graph consisting of a node for each dominating set of size at most k and edges specified by the adjacency relation. Addressing an open question posed by Haas and Seyffarth, we demonstrate that \(D_{\varGamma (G)+1}(G)\) is not necessarily connected, for \(\varGamma (G)\) the maximum cardinality of a minimal dominating set in G. The result holds even when graphs are constrained to be planar, of bounded tree-width, or b-partite for \(b \ge 3\). Moreover, we construct an infinite family of graphs such that \(D_{\gamma (G)+1}(G)\) has exponential diameter, for \(\gamma (G)\) the minimum size of a dominating set. On the positive side, we show that \(D_{n-\mu }(G)\) is connected and of linear diameter for any graph G on n vertices with a matching of size at least \(\mu +1\).     

Improved floor-planning of graphs via adjacency-preserving transformations

Let G=(V,E) and G′=(V′,E′) be two graphs, an adjacency-preserving transformation from G to G′ is a one-to-many and onto mapping from V to V′ satisfying the following: (1) Each vertex v∈V in G is mapped to a non-empty subset \(\mathcal{A}(v)\subset V'\) in G′. The subgraph induced by \(\mathcal{A}(v)\) is a connected subgraph of G′; (2) if u≠v∈V, then \(\mathcal{A}(u)\cap\mathcal{A}(v)=\emptyset\); and (3) two vertices u and v are adjacent to each other in G if and only if subgraphs induced by \(\mathcal{A}(u)\) and \(\mathcal{A}(v)\) are connected in G′.In this paper, we study adjacency-preserving transformations from plane triangulations to irreducible triangulations (which are internally triangulated, with four exterior vertices and no separating triangles). As one shall see, our transformations not only preserve adjacency well, but also preserve the endowed realizers of plane triangulations well in the endowed transversal structures of the image irreducible triangulations, which may be desirable in some applications.We then present such an application in floor-planning of plane graphs. The expected grid size of the floor-plan of our linear time algorithm is improved to \((\frac{5n}{8}+O(1))\times (\frac{23n}{24}+O(1))\), though the worst case grid size bound of the algorithm remains \(\lfloor\frac{2n+1}{3}\rfloor\times(n-1)\), which is the same as the algorithm presented in Liao et al. (J. Algorithms 48:441–451, 2003).