New analysis and computational study for the planar connected dominating set problem

The connected dominating set (CDS) problem is a well studied NP-hard problem with many important applications. Dorn et al. (Algorithmica 58:790–810 2010) introduce a branch-decomposition based algorithm design technique for NP-hard problems in planar graphs and give an algorithm (DPBF algorithm) which solves the planar CDS problem in \(O(2^{9.822\sqrt{n}}n+n^3)\) time and \(O(2^{8.11\sqrt{n}}n+n^3)\) time, with a conventional method and fast matrix multiplication in the dynamic programming step of the algorithm, respectively. We show that DPBF algorithm solves the planar CDS problem in \(O(2^{9.8\sqrt{n}}n+n^3)\) time with a conventional method and in \(O(2^{8.08\sqrt{n}}n+n^3)\) time with a fast matrix multiplication. For a graph \(G\), let \({\hbox {bw}}(G)\) be the branchwidth of \(G\) and \(\gamma _c(G)\) be the connected dominating number of \(G\). We prove \({\hbox {bw}}(G)\le 2\sqrt{10\gamma _c(G)}+32\). From this result, the planar CDS problem admits an \(O(2^{23.54\sqrt{\gamma _c(G)}}\gamma _c(G)+n^3)\) time fixed-parameter algorithm. We report computational study results on the practical performance of DPBF algorithm, which show that the size of instances can be solved by the algorithm mainly depends on the branchwidth of the instances, coinciding with the theoretical analysis. For graphs with small or moderate branchwidth, the CDS problem instances with size up to a few thousands edges can be solved in a practical time and memory space.     

A faster strongly polynomial time algorithm to solve the minimum cost tension problem

This paper presents a strongly polynomial time algorithm for the minimum cost tension problem, which runs in \(O(\max \{m^3n, m^2 \log n(m+n \log n)\})\) time, where n and m denote the number of nodes and number of arcs, respectively. Our algorithm improves upon the previous strongly polynomial time of \(O(n^4 m^3 \log n)\) due to Hadjiat and Maurras (Discret Math 165(166):377–394, 1997).     

Algorithms for testing occurrences of length 4 patterns in permutations

In this paper linear time sequential and optimal parallel algorithms for testing pattern involvement for all length 4 permutations are described. This is an improvement as the previous best sequential algorithms, for most of these pattern require \(O(n\log n)\) time. Our parallel algorithms can be implemented in \(O(\log n)\) time with \(n/\log n\) processors on the CREW PRAM model, or alternatively in \(O(\log \log \log n)\) time with \(n/\log \log \log n\) processors on a CRCW PRAM PRAM model. Parallel algorithm can also be implemented in constant time with \(n\log ^3 n\) processors on a CRCW PRAM model. The previous best parallel algorithms were available for only some of these patterns and took \(O(\log n)\) time with n processors on the CREW PRAM model.     

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

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.     

Constrained pairwise and center-star sequences alignment problems

This paper considers the minimax regret vertex 2-sink location problem in a dynamic path network with positive edge lengths and uniform edge capacity. Let \(P\) be an undirected path graph of \(n\) vertices, and the weight (initial supply) of every vertex is known as an interval. The problem is to find two vertices \(x\) and \(y\) as two sinks on the path such that all the weights can evacuate to \(x\) and \(y\) with minimum regret of evacuation time in case of an emergency for any possible weight distribution. We present an \(O(n^3\log n)\) time algorithm.     

Finding a contra-risk path between two nodes in undirected graphs

Given an undirected graph with a source node s and a sink node t. The anti-risk path problem is defined as the problem of finding a path between node s to node t with the least risk under the assumption that at most one edge of each path may be blocked. Xiao et al. (J Comb Optim 17:235–246, 2009) defined the problem and presented an \(O(mn+n^2 \log n)\) time algorithm to find an anti-risk path, where n and m are the number of nodes and edges, respectively. Recently, Mahadeokar and Saxena (J Comb Optim 27:798–807, 2014) solved the problem in \(O(m+n \log n)\) time. In this paper, first, a new version of the anti-risk path (called contra-risk path) is defined, which is more effective than an anti-risk path in many networks. Then, an algorithm to find a contra-risk path is presented, which runs in \(O(m+n \log n)\) time.     

Parameterized algorithms for min–max 2-cluster editing

For a given graph and an integer t, the Min–Max 2-Clustering problem asks if there exists a modification of a given graph into two maximal disjoint cliques by inserting or deleting edges such that the number of the editing edges incident to each vertex is at most t. It has been shown that the problem can be solved in polynomial time for \(t<n/4\), where n is the number of vertices. In this paper, we design parameterized algorithms for different ranges of t. Let \(k=t-n/4\). We show that the problem is polynomial-time solvable when roughly \(k<\sqrt{n/32}\). When \(k\in o(n)\), we design a randomized and a deterministic algorithm with sub-exponential time parameterized complexity, i.e., the problem is in SUBEPT. We also show that the problem can be solved in \(O({2}^{n/r}\cdot n^2)\) time for \(k<n/12\) and in \(O(n^2\cdot 2^{3n/4+k})\) time for \(n/12\le k< n/4\), where \(r=2+\lfloor (n/4-3k-2)/(2k+1) \rfloor \ge 2\).     

Distributed wireless link scheduling in the SINR model

We present an approximation algorithm for wireless link scheduling under the physical SINR interference model. In the link scheduling problem, it is given a set of \(n\) links in a metric space, each of which is a sender–receiver pair, and the objective is to schedule the links using the minimum amount of time. We focus on a variant of this fundamental problem where the power is fixed, i.e., the power assignment of links is given as part of the input. Specifically, we consider an important category of power assignments called length-monotone sublinear power assignment, which includes the widely studied uniform, mean and linear power assignments. We present a distributed algorithm that can schedule all links in \(O(\log \varDelta (I_{max}+\log ^3n))\) rounds with high probability, where \(\varDelta \) is the ratio between the longest link and the shortest link and \(I_{max}\) is the maximum nearly-equilength class affectance of the link set. It is shown that the proposed algorithm is \(O(\log \varDelta )\) approximate to the optimal schedule in dense networks with \(I_{max}\in \varOmega (\log ^3n)\). To the best of our knowledge, our algorithm is the first distributed one whose approximation ratio is independent of the network size \(n\). Our result also shows that the \(\varOmega (\log n)\) lower bound (Halldórsson and Mitra in: ICALP, 2011) on the approximation ratio does not hold for link sets with \(\log \varDelta \in o(\log n)\).     

An FPTAS for generalized absolute 1-center problem in vertex-weighted graphs

Given a vertex-weighted undirected connected graph \(G = (V, E, \ell , \rho )\), where each edge \(e \in E\) has a length \(\ell (e) > 0\) and each vertex \(v \in V\) has a weight \(\rho (v) > 0\), a subset \(T \subseteq V\) of vertices and a set S containing all the points on edges in a subset \(E' \subseteq E\) of edges, the generalized absolute 1-center problem (GA1CP), an extension of the classic vertex-weighted absolute 1-center problem (A1CP), asks to find a point from S such that the longest weighted shortest path distance in G from it to T is minimized. This paper presents a simple FPTAS for GA1CP by traversing the edges in \(E'\) using a positive real number as step size. The FPTAS takes \(O( |E| |V| + |V|^2 \log \log |V| + \frac{1}{\epsilon } |E'| |T| {\mathcal {R}})\) time, where \({\mathcal {R}}\) is an input parameter size of the problem instance, for any given \(\epsilon > 0\). For instances with a small input parameter size \({\mathcal {R}}\), applying the FPTAS with \(\epsilon = \Theta (1)\) to the classic vertex-weighted A1CP can produce a \((1 + \Theta (1))\)-approximation in at most O(|E| |V|) time when the distance matrix is known and \(O(|E| |V| + |V|^2 \log \log |V|)\) time when the distance matrix is unknown, which are smaller than Kariv and Hakimi’s \(O(|E| |V| \log |V|)\)-time algorithm and \(O(|E| |V| \log |V| + |V|^3)\)-time algorithm, respectively.     

An approximation algorithm for maximum weight budgeted connected set cover

This paper studies approximation algorithm for the maximum weight budgeted connected set cover (MWBCSC) problem. Given an element set \(X\), a collection of sets \({\mathcal {S}}\subseteq 2^X\), a weight function \(w\) on \(X\), a cost function \(c\) on \({\mathcal {S}}\), a connected graph \(G_{\mathcal {S}}\) (called communication graph) on vertex set \({\mathcal {S}}\), and a budget \(L\), the MWBCSC problem is to select a subcollection \({\mathcal {S'}}\subseteq {\mathcal {S}}\) such that the cost \(c({\mathcal {S'}})=\sum _{S\in {\mathcal {S'}}}c(S)\le L\), the subgraph of \(G_{\mathcal {S}}\) induced by \({\mathcal {S'}}\) is connected, and the total weight of elements covered by \({\mathcal {S'}}\) (that is \(\sum _{x\in \bigcup _{S\in {\mathcal {S'}}}S}w(x)\)) is maximized. We present a polynomial time algorithm for this problem with a natural communication graph that has performance ratio \(O((\delta +1)\log n)\), where \(\delta \) is the maximum degree of graph \(G_{\mathcal {S}}\) and \(n\) is the number of sets in \({\mathcal {S}}\). In particular, if every set has cost at most \(L/2\), the performance ratio can be improved to \(O(\log n)\).     

Dynamic matchings in left vertex weighted convex bipartite graphs

A left vertex weighted convex bipartite graph (LWCBG) is a bipartite graph \(G=(X,Y,E)\) in which the neighbors of each \(x\in X\) form an interval in \(Y\) where \(Y\) is linearly ordered, and each \(x\in X\) has an associated weight. This paper considers the problem of maintaining a maximum weight matching in a dynamic LWCBG. The graph is subject to the updates of vertex and edge insertions and deletions. Our dynamic algorithms maintain the update operations in \(O(\log ^2{|V|})\) amortized time per update, obtain the matching status of a vertex (whether it is matched) in constant worst-case time, and find the pair of a matched vertex (with which it is matched) in worst-case \(O(k)\) time, where \(k\) is not greater than the cardinality of the maximum weight matching. That achieves the same time bound as the best known solution for the problem of the unweighted version.     

Partial degree bounded edge pacing problem for graphs and $$$$-uniform hypergraphs

Given a graph \(G=(V,E)\) and a non-negative integer \(c_u\) for each \(u\in V\), partial degree bounded edge packing problem is to find a subgraph \(G^{\prime }=(V,E^{\prime })\) with maximum \(|E^{\prime }|\) such that for each edge \((u,v)\in E^{\prime }\), either \(deg_{G^{\prime }}(u)\le c_u\) or \(deg_{G^{\prime }}(v)\le c_v\). The problem has been shown to be NP-hard even for uniform degree constraint (i.e., all \(c_u\) being equal). In this work we study the general degree constraint case (arbitrary degree constraint for each vertex) and present two combinatorial approximation algorithms with approximation factors \(4\) and \(2\). Then we give a \(\log _2 n\) approximation algorithm for edge-weighted version of the problem and an efficient exact algorithm for edge-weighted trees with time complexity \(O(n\log n)\). We also consider a generalization of this problem to \(k\)-uniform hypergraphs and present a constant factor approximation algorithm based on linear programming using Lagrangian relaxation.     

Almost separable matrices

An \(m\times n\) matrix \(\mathsf {A}\) with column supports \(\{S_i\}\) is k-separable if the disjunctions \(\bigcup _{i \in \mathcal {K}} S_i\) are all distinct over all sets \(\mathcal {K}\) of cardinality k. While a simple counting bound shows that \(m > k \log _2 n/k\) rows are required for a separable matrix to exist, in fact it is necessary for m to be about a factor of k more than this. In this paper, we consider a weaker definition of ‘almost k-separability’, which requires that the disjunctions are ‘mostly distinct’. We show using a random construction that these matrices exist with \(m = O(k \log n)\) rows, which is optimal for \(k = O(n^{1-\beta })\). Further, by calculating explicit constants, we show how almost separable matrices give new bounds on the rate of nonadaptive group testing.     

The inverse 1-center problem on trees with variable edge lengths under Chebyshev norm and Hamming distance

This paper addresses the problem of modifying the edge lengths of a tree in minimum total cost such that a prespecified vertex becomes the 1-center of the perturbed tree. This problem is called the inverse 1-center problem on trees. We focus on the problem under Chebyshev norm and Hamming distance. From special properties of the objective functions, we can develop combinatorial algorithms to solve the problem. Precisely, if there does not exist any vertex coinciding with the prespecified vertex during the modification of edge lengths, the problem under Chebyshev norm or bottleneck Hamming distance is solvable in \(O(n\log n)\) time, where \(n+1\) is the number of vertices of the tree. Dropping this condition, the problem can be solved in \(O(n^{2})\) time.     

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

The longest commonly positioned increasing subsequences problem

Based on the well-known longest increasing subsequence problem and longest common increasing subsequence (LCIS) problem, we propose the longest commonly positioned increasing subsequences (LCPIS) problem. Let \(A=\langle a_1,a_2,\ldots ,a_n\rangle \) and \(B{=}\left\langle b_1,b_2,\ldots ,b_n\right\rangle \) be two input sequences. Let \({ Asub}=\left\langle a_{i_1},a_{i_2},\ldots ,a_{i_l}\right\rangle \) be a subsequence of A and \({ Bsub}=\left\langle b_{j_1},b_{j_2},\ldots ,b_{j_l}\right\rangle \) be a subsequence of B such that \(a_{i_k}\le a_{i_{k+1}}, b_{j_k}\le b_{j_{k+1}}(1\le k<l)\), and \(a_{i_k}\) and \(b_{j_k}\) (\(1\le k\le l\)) are commonly positioned (have the same index \(i_k=j_k\)) in A and B respectively but these two elements do not need to be equal. The LCPIS problem aims at finding a pair of subsequences Asub and \({ Bsub}\) as long as possible. When all the elements of the two input sequences are positive integers, this paper presents an algorithm with \(O(n\log n \log \log M)\) time to compute the LCPIS, where \(M={ min}\{{ max}_{1\le i\le n}a_i,{ max}_{1\le j\le n}b_j\}\). And we also show a dual relationship between the LCPIS problem and the LCIS problem.     

Upper bounds for the total rainbow connection of graphs

A two-agent scheduling problem on parallel machines is considered. Our objective is to minimize the makespan for agent A, subject to an upper bound on the makespan for agent B. When the number of machines, denoted by \(m\), is chosen arbitrarily, we provide an \(O(n)\) algorithm with performance ratio \(2-\frac{1}{m}\), i.e., the makespan for agent A given by the algorithm is no more than \(2-\frac{1}{m}\) times the optimal value, while the makespan for agent B is no more than \(2-\frac{1}{m}\) times the threshold value. This ratio is proved to be tight. Moreover, when \(m=2\), we present an \(O(nlogn)\) algorithm with performance ratio \(\frac{1+\sqrt{17}}{4}\approx 1.28\) which is smaller than \(\frac{3}{2}\). The ratio is weakly tight.     

An algorithm for finding a representation of a subtree distance

Generalizing the concept of tree metric, Hirai (Ann Combinatorics 10:111–128, 2006) introduced the concept of subtree distance. A nonnegative-valued mapping \(d:X\times X \rightarrow \mathbb {R}_+\) is called a subtree distance if there exist a weighted tree T and a family \(\{T_x\mid x \in X\}\) of subtrees of T indexed by the elements in X such that \(d(x,y)=d_T(T_x,T_y)\), where \(d_T(T_x,T_y)\ge 0\) is the distance between \(T_x\) and \(T_y\) in T. Hirai (2006) provided a characterization of subtree distances that corresponds to Buneman’s (J Comb Theory, Series B 17:48–50, 1974) four-point condition for tree metrics. Using this characterization, we can decide whether or not a given mapping is a subtree distance in O\((n^4)\) time. In this paper, we show an O\((n^3)\) time algorithm that finds a representation of a given subtree distance. This results in an O\((n^3)\) time algorithm for deciding whether a given mapping is a subtree distance.     

An $$O(n\log n)$$ algorithm for finding edge span of cacti

Let \(G=(V,E)\) be a nonempty graph and \(\xi :E\rightarrow \mathbb {N}\) be a function. In the paper we study the computational complexity of the problem of finding vertex colorings \(c\) of \(G\) such that:

1. (1)
   \(|c(u)-c(v)|\ge \xi (uv)\) for each edge \(uv\in E\);
    
2. (2)
   the edge span of \(c\), i.e. \(\max \{|c(u)-c(v)|:uv\in E\}\), is minimal.
    

We show that the problem is NP-hard for subcubic outerplanar graphs of a very simple structure (similar to cycles) and polynomially solvable for cycles and bipartite graphs. Next, we use the last two results to construct an algorithm that solves the problem for a given cactus \(G\) in \(O(n\log n)\) time, where \(n\) is the number of vertices of \(G\).