Spanners of bounded degree graphs

A k-spanner of a graph G is a spanning subgraph of G in which the distance between any pair of vertices is at most k times the distance in G. We prove that for fixed k,w, the problem of deciding if a given graph has a k-spanner of treewidth w is fixed-parameter tractable on graphs of bounded degree. In particular, this implies that finding a k-spanner that is a tree (a tree k-spanner) is fixed-parameter tractable on graphs of bounded degree. In contrast, we observe that if the graph has only one vertex of unbounded degree, then Treek-Spanner is NP-complete for k?4.     

Locally connected spanning trees in cographs, complements of bipartite graphs and doubly chordal graphs

A spanning tree T of a graph G=(V,E) is called a locally connected spanning tree if the set of all neighbors of v in T induces a connected subgraph of G for all v∈V. The problem of recognizing whether a graph admits a locally connected spanning tree is known to be NP-complete even when the input graphs are restricted to chordal graphs. In this paper, we propose linear time algorithms for finding locally connected spanning trees in cographs, complements of bipartite graphs and doubly chordal graphs, respectively.     

A linear-time algorithm to compute a MAD tree of an interval graph

The average distance of a connected graph G is the average of the distances between all pairs of vertices of G. We present a linear time algorithm that determines, for a given interval graph G, a spanning tree of G with minimum average distance (MAD tree). Such a tree is sometimes referred to as a minimum routing cost spanning tree.     

The General Steiner Tree-Star problem

The Steiner tree problem is defined as follows—given a graph G=(V,E) and a subset X⊂V of terminals, compute a minimum cost tree that includes all nodes in X. Furthermore, it is reasonable to assume that the edge costs form a metric. This problem is NP-hard and has been the study of many heuristics and algorithms. We study a generalization of this problem, where there is a “switch” cost in addition to the cost of the edges. Switches are placed at internal nodes of the tree (essentially, we may assume that all non-leaf nodes of the Steiner tree have a switch). The cost for placing a switch may vary from node to node. A restricted version of this problem, where the terminal set X cannot be connected to each other directly but only via the Steiner nodes V?X, is referred to as the Steiner Tree-Star problem. The General Steiner Tree-Star problem does not require the terminal set and Steiner node set to be disjoint. This generalized problem can be reduced to the node weighted Steiner tree problem, for which algorithms with performance guarantees of Θ(lnn) are known. However, such approach does not make use of the fact that the edge costs form a metric. In this paper we derive approximation algorithms with small constant factors for this problem. We show two different polynomial time algorithms with approximation factors of 5.16 and 5.     

Improved Approximation Algorithms for the Spanning Star Forest Problem

A star graph is a tree of diameter at most two. A star forest is a graph that consists of node-disjoint star graphs. In the spanning star forest problem, given an unweighted graph G, the objective is to find a star forest that contains all vertices of G and has the maximum number of edges. This problem is the complement of the dominating set problem in the following sense: On a graph with n vertices, the size of the maximum spanning star forest is equal to n minus the size of the minimum dominating set. We present a 0.71-approximation algorithm for this problem, improving upon the approximation factor of 0.6 of Nguyen et al. (SIAM J. Comput. 38:946–962, 2008). We also present a 0.64-approximation algorithm for the problem on node-weighted graphs. Finally, we present improved hardness of approximation results for the weighted (both edge-weighted and node-weighted) versions of the problem. Our algorithms use a non-linear rounding scheme, which might be of independent interest.     

A Linear-Time Algorithm for Finding Locally Connected Spanning Trees on Circular-Arc Graphs

Suppose that T is a spanning tree of a graph G. T is called a locally connected spanning tree of G if for every vertex of T, the set of all its neighbors in T induces a connected subgraph of G. In this paper, given an intersection model of a circular-arc graph, an O(n)-time algorithm is proposed that can determine whether the circular-arc graph contains a locally connected spanning tree or not, and produce one if it exists.     

An adaptive heuristic to the bounded-diameter minimum spanning tree problem

Given a graph G and a bound d?≥?2, the bounded-diameter minimum spanning tree problem seeks a spanning tree on G of minimum weight subject to the constraint that its diameter does not exceed d. This problem is NP-hard; several heuristics have been proposed to find near-optimal solutions to it in reasonable times. A decentralized learning automata-based algorithm creates spanning trees that honor the diameter constraint. The algorithm rewards a tree if it has the smallest weight found so far and penalizes it otherwise. As the algorithm proceeds, the choice probability of the tree converges to one; and the algorithm halts when this probability exceeds a predefined value. Experiments confirm the superiority of the algorithm over other heuristics in terms of both speed and solution quality.     

VNS and second order heuristics for the min-degree constrained minimum spanning tree problem

Given an undirected graph with weights associated with its edges, the min-degree constrained minimum spanning tree (md$\mathit{md}$-MST) problem consists in finding a minimum spanning tree of the given graph, imposing minimum degree constraints in all nodes except the leaves. This problem was recently proposed in Almeida et al. [Min-degree constrained minimum spanning tree problem: Complexity, proprieties and formulations. Operations Research Center, University of Lisbon, Working-paper no. 6; 2006], where its theoretical complexity was characterized and showed to be NP$\mathit{NP}$-hard.     

What Would Edmonds Do? Augmenting Paths and Witnesses for Degree-Bounded MSTs

Given a graph and degree upper bounds on vertices, the BDMST problem requires us to find a minimum cost spanning tree respecting the given degree bounds. This problem generalizes the Travelling Salesman Path Problem (TSPP), even in unweighted graphs, and so we expect that it is necessary to relax the degree constraints to get efficient algorithms. Könemann and Ravi (Proceedings of the Thirty Second Annual ACM Symposium on Theory of Computing, pp. 537–546, 2000; Proceedings of the Thirty-Fifth ACM Symposium on Theory of Computing, pp. 389–395, 2003) give bicriteria approximation algorithms for the problem using local search techniques of Fischer (Technical Report 14853, Cornell University, 1993). Their algorithms find solutions which make a tradeoff of the approximation factor for the cost of the resulting tree against the factor by which degree constraints are violated. In particular, they give an algorithm which, for a graph with a spanning tree of cost C and degree B, and for parameters b,w>1, produces a tree whose cost is at most wC and whose degree is at most \(\frac{w}{w-1}bB+\log_{b}n.\) A primary contribution of Könemann and Ravi is to use a Lagrangean relaxation to formally relate the BDMST problem to what we call the MDMST problem, which is the problem of finding an MST of minimum degree in a graph. In their solution to the MDMST problem, they make central use of a local-search approximation algorithm of Fischer.In this paper, we give the first approximation algorithms for the BDMST problem—both our algorithms find trees of optimal cost. We achieve this improvement using a primal-dual cost bounding methodology from Edmonds’ weighted matching algorithms which was not previously used in this context. In order to follow Edmonds’ approach, we develop algorithms for a variant of the MDMST problem in which there are degree lower bound requirements. This variant may be of independent interest; in particular, our results extend to a generalized version of the BDMST problem in which both upper and lower degree bounds are given.First we give a polynomial-time algorithm that finds a tree of optimal cost and with maximum degree at most \(\frac{b}{2-b}B+O(\log_{b}n)\) for any b∈(1,2). We also give a quasi-polynomial-time approximation algorithm which produces a tree of optimal cost C and maximum degree at most B+O(log?n/log?log?n). That is, the error is additive as well as restricted just to the degree. This further improvement in degree is obtained by using augmenting-path techniques that search over a larger solution space than Fischer’s local-search algorithm.     

Parallel construction of optimal independent spanning trees on Cartesian product of complete graphs

A set of k spanning trees rooted at the same vertex r in a graph G is said to be independent if for each vertex x other than r, the k paths from r to x, one path in each spanning tree, are internally disjoint. Using independent spanning trees (ISTs) one can design fault-tolerant broadcasting schemes and increase message security in a network. Thus, the problem of ISTs on graphs has been received much attention. Recently, Yang et al. proposed a parallel algorithm for generating optimal ISTs on the hypercube. In this paper, we propose a similar algorithm for generating optimal ISTs on Cartesian product of complete graphs. The algorithm can be easily implemented in parallel or distributed systems. Moreover, the proof of its correctness is simpler than that of Yang et al.     

Maintaining Spanning Trees of Small Diameter

Given a graph G with m edges and n nodes, a spanning tree T of G , and an edge e that is being deleted from or inserted into G , we give efficient O(n) algorithms to compute a possible swap for e that minimizes the diameter of the new spanning tree. This problem arises in high-speed networks, particularly in optical networks. Received January 1995; revised February 1997.     

Survivable network design: the capacitated minimum spanning network problem

We are given an undirected graph G=(V,E) with positive weights on its vertices representing demands, and non-negative costs on its edges. Also given are a capacity constraint k, and root vertex r∈V. In this paper, we consider the capacitated minimum spanning network (CMSN) problem, which asks for a minimum cost spanning network such that the removal of r and its incident edges breaks the network into a number of components (groups), each of which is 2-edge-connected with a total weight of at most k. We show that the CMSN problem is NP-hard, and present a 4-approximation algorithm for graphs satisfying triangle inequality. We also show how to obtain similar approximation results for a related 2-vertex-connected CMSN problem.     

Finding the k most vital edges with respect to minimum spanning tree

For a connected, undirected and weighted graph G = (V,E), the problem of finding the k most vital edges of G with respect to minimum spanning tree is to find k edges in G whose removal will cause greatest weight increase in the minimum spanning tree of the remaining graph. This problem is known to be NP-hard for arbitraryk. In this paper, we first describe a simple exact algorithm for this problem, based on t he approach of edge replacement in the minimum spanning tree of G. Next we present polynomial-time randomized algorithms that produce optimal and approximate solutions to this problem. For and , our algorithm producing optimal solution has a time complexity of O(mn) with probability of success at least , which is 0.90 for and asymptotically 1 when k goes to infinity. The algorithm producing approximate solution runs in time with probability of success at least , which is 0.998 for , and produces solution within factor 2 to the optimal one. Finally we show that both of our randomized algorithms can be easily parallelized. On a CREW PRAM, the first algorithm runs in O(n) time using processors, and the second algorithm runs in time using mn/logn processors and hence is RNC. Received 30 October 1995 / 5 November 1998     

An improved exact algorithm for the domatic number problem

The 3-domatic number problem asks whether a given graph can be partitioned into three dominating sets. We prove that this problem can be solved by a deterministic algorithm in time n^2.695 (up to polynomial factors) and in polynomial space. This result improves the previous bound of n^2.8805, which is due to Björklund and Husfeldt. To prove our result, we combine an algorithm by Fomin et al. with Yamamoto's algorithm for the satisfiability problem. In addition, we show that the 3-domatic number problem can be solved for graphs G with bounded maximum degree Δ(G) by a randomized polynomial-space algorithm, whose running time is better than the previous bound due to Riege and Rothe whenever Δ(G)?5. Our new randomized algorithm employs Schöning's approach to constraint satisfaction problems.     

Distributed algorithms for finding and maintaining a k-tree core in a dynamic network

A k-core C_k of a tree T is subtree with exactly k leaves for k?n_l, where n_l the number of leaves in T, and minimizes the sum of the distances of all nodes from C_k. In this paper first we propose a distributed algorithm for constructing a rooted spanning tree of a dynamic graph such that root of the tree is located near the center of the graph. Then we provide a distributed algorithm for finding k-core of that spanning tree. The spanning tree is constructed in two stages. In the first stage, a forest of trees is generated. In the next stage these trees are connected to form a single rooted tree. An interesting aspect of the first stage of proposed spanning algorithm is that it implicitly constructs the (convex) hull of those nodes which are not already included in the spanning forest. The process is repeated till all non root nodes of the graph have chosen a unique parent. We implemented the algorithms for finding spanning tree and its k-core. A core can be quite useful for routing messages in a dynamic network consisting of a set of mobile devices.     

The computational complexity of the backbone coloring problem for bounded-degree graphs with connected backbones

Given a graph G, a spanning subgraph H of G   and an integer λ≥2$\lambda \ge 2$, a λ-backbone coloring of G with backbone H is a proper vertex coloring of G   using colors 1,2,…$1,2,\dots$, in which the color difference between vertices adjacent in H is greater than or equal to λ. The backbone coloring problem is that of finding such a coloring whose maximum color does not exceed a given limit k  . In this paper, we study the backbone coloring problem for bounded-degree graphs with connected backbones and we give a complete computational complexity classification of this problem. We present a polynomial algorithm for optimal backbone coloring for subcubic graphs with arbitrary backbones. We also prove that the backbone coloring problem for graphs with arbitrary backbones and with fixed maximum degree (at least 4) is NP-complete. Furthermore, we show that for the special case of graphs with fixed maximum degree at least 5 and λ≥4$\lambda \ge 4$ the problem remains NP-complete even for spanning tree backbones.     

Maximum Series-Parallel Subgraph

Consider the NP-hard problem of, given a simple graph?G, to find a series-parallel subgraph of?G with the maximum number of edges. The algorithm that, given a connected graph?G, outputs a spanning tree of?G, is a $\frac{1}{2}$ -approximation. Indeed, if n is the number of vertices in G, any spanning tree in G has?n?1 edges and any series-parallel graph on?n vertices has at most?2n?3 edges. We present a $\frac{7}{12}$ -approximation for this problem and results showing the limits of our approach.     

Variations of the maximum leaf spanning tree problem for bipartite graphs

The maximum leaf spanning tree problem is known to be NP-complete. In [M.S. Rahman, M. Kaykobad, Complexities of some interesting problems on spanning trees, Inform. Process. Lett. 94 (2005) 93-97], a variation on this problem was posed. This variation restricts the problem to bipartite graphs and asks, for a fixed integer K, whether or not the graph contains a spanning tree with at least K leaves in one of the partite sets. We show not only that this problem is NP-complete, but that it remains NP-complete for planar bipartite graphs of maximum degree 4. We also consider a generalization of a related decision problem, which is known to be polynomial-time solvable. We show the problem is still polynomial-time solvable when generalized to weighted graphs.     

Parameterized Complexity of the Spanning Tree Congestion Problem

We study the problem of determining the spanning tree congestion of a?graph. We present some sharp contrasts in the parameterized complexity of this problem. First, we show that on apex-minor-free graphs, a general class of graphs containing planar graphs, graphs of bounded treewidth, and graphs of bounded genus, the problem to determine whether a given graph has spanning tree congestion at most k can be solved in linear time for every fixed k. We also show that for every fixed k and d the problem is solvable in linear time for graphs of degree at most d. In contrast, if we allow only one vertex of unbounded degree, the problem immediately becomes NP-complete for any fixed k??8. Moreover, the hardness result holds for graphs excluding the complete graph on 6 vertices as a minor. We also observe that for k??3 the problem becomes polynomially time solvable.     

Acyclic coloring of graphs of maximum degree five: Nine colors are enough

An acyclic coloring of a graph G is a coloring of its vertices such that: (i) no two neighbors in G are assigned the same color and (ii) no bicolored cycle can exist in G. The acyclic chromatic number of G is the least number of colors necessary to acyclically color G. In this paper, we show that any graph of maximum degree 5 has acyclic chromatic number at most 9, and we give a linear time algorithm that achieves this bound.