Minimum edge ranking spanning trees of split graphs

Given a graph G, the minimum edge ranking spanning tree problem (MERST) is to find a spanning tree of G whose edge ranking is minimum. However, this problem is known to be NP-hard for general graphs. In this paper, we show that the problem MERST has a polynomial time algorithm for split graphs, which have useful applications in practice. The result is also significant in the sense that this is a first non-trivial graph class for which the problem MERST is found to be polynomially solvable. We also show that the problem MERST for threshold graphs can be solved in linear time, where threshold graphs are known to be split.     

Np-hardness proof and an approximation algorithm for the minimum vertex ranking spanning tree problem

The minimum vertex ranking spanning tree problem (MVRST) is to find a spanning tree of G whose vertex ranking is minimum. In this paper, we show that MVRST is NP-hard. To prove this, we polynomially reduce the 3-dimensional matching problem to MVRST. Moreover, we present a (⌈D_s/2⌉+1)/(⌊log₂(D_s+1)⌋+1)-approximation algorithm for MVRST where D_s is the minimum diameter of spanning trees of G.     

Approximating the Minimum-Degree Steiner Tree to within One of Optimal

The problem of constructing a spanning tree for a graph G = (V, E) with n vertices whose maximal degree is the smallest among all spanning trees of G is considered. This problem is easily shown to be NP-hard. In the Steiner version of this problem, along with the input graph, a set of distinguished vertices D V is given. A minimum-degree Steiner tree is a tree of minimum degree which spans at least the set D. Iterative polynomial time approximation algorithms for the problems are given. The algorithms compute trees whose maximal degree is at most Δ* + 1, where Δ* is the degree of some optimal tree for the respective problems. Unless P = NP, this is the best bound achievable in polynomial time.     

On spanning tree problems with multiple objectives

We investigate two versions of multiple objective minimum spanning tree problems defined on a network with vectorial weights. First, we want to minimize the maximum ofQ linear objective functions taken over the set of all spanning trees (max-linear spanning tree problem, ML-ST). Secondly, we look for efficient spanning trees (multi-criteria spanning tree problem, MC-ST).Problem ML-ST is shown to be NP-complete. An exact algorithm which is based on ranking is presented. The procedure can also be used as an approximation scheme. For solving the bicriterion MC-ST, which in the worst case may have an exponential number of efficient trees, a two-phase procedure is presented. Based on the computation of extremal efficient spanning trees we use neighbourhood search to determine a sequence of solutions with the property that the distance between two consecutive solutions is less than a given accuracy.Partially supported by Deutsche Forschungsgemeinschaft and HCº Contract no. ERBCHRXCT 930087.Partially supported by Alexander von Humboldt-Stiftung.     

A Network-Flow Technique for Finding Low-Weight Bounded-Degree Spanning Trees

Given a graph with edge weights satisfying the triangle inequality, and a degree bound for each vertex, the problem of computing a low-weight spanning tree such that the degree of each vertex is at most its specified bound is considered. In particular, modifying a given spanning treeTusingadoptionsto meet the degree constraints is considered. A novel network-flow-based algorithm for finding a good sequence of adoptions is introduced. The method yields a better performance guarantee than any previous algorithm. If the degree constraintd(v) for eachvis at least 2, the algorithm is guaranteed to find a tree whose weight is at most the weight of the given tree times 2 − min{(d(v) − 2)/(deg_T(v) − 2) : deg_T(v) > 2}, where deg_T(v) is the initial degree ofv. Equally importantly, it takes this approach to the limit in the following sense: if any performance guarantee that is solely a function of the topology and edge weights of a given tree holds foranyalgorithm at all, then it also holds for the given algorithm. Examples are provided in which no lighter tree meeting the degree constraint exists. Linear-time algorithms are provided with the same worst-case performance guarantee. ChoosingTto be a minimum spanning tree yields approximation algorithms with factors less than 2 for the general problem on geometric graphs with distances induced by variousL_pnorms. Finally, examples of Euclidean graphs are provided in which the ratio of the lengths of an optimal Traveling Salesman path and a minimum spanning tree can be arbitrarily close to 2.     

An O(m log n) algorithm for the max + sum spanning tree problem

In a graph in which each edge has two weights, the max + sum spanning tree problem seeks a spanning tree that has the minimum value for the combined total of the maximum of one of the edge weights and the sum of the other weights among all the spanning trees in the graph. Exploiting an efficient data structure, an O(m log n) algorithm is presented for solving this problem. This improves the currently known bound of O(mn).     

Classification of interpolation theorems for spanning trees and other families of spanning subgraphs

We say that a graphical invariant i of a graph interpolates over a family F of graphs if i satisfies the following property: If m and M are the minimum and maximum values (respectively) of i over all graphs in F then for each k, m ? k ? M, there is a graph H in F for which i(H)= k. In previous works it was shown that when F is the set of spanning trees of a connected graph G, a large number of invariants interpolate (some of these invariants require the additional assumption that G be 2-connected). Although the proofs of all these results use the same basic idea of gradually transforming one tree into another via a sequence of edge exchanges, some of these processes require sequences that use more properties of trees than do others. We show that the edge exchange proofs can be divided into three types, in accordance with the extent to which the exchange sequence depends upon properties of spanning trees. This idea is then used to obtain new interpolation results for some invariants, and to show how the exchange methods and interpolation results on spanning trees can be extended to other families of spanning subgraphs.     

Edge ranking of weighted trees

In this paper we consider the edge ranking problem of weighted trees. We prove that a special instance of this problem, namely edge ranking of multitrees is NP-hard already for multitrees with diameter at most 10. Note that the same problem but for trees is linearly solvable. We give an O(logn)-approximation polynomial time algorithm for edge ranking of weighted trees.     

Oriented walk double covering and bidirectional double tracing

An oriented walk double covering of a graph G is a set of oriented closed walks, that, traversed successively, combined will have traced each edge of G once in each direction. A bidirectional double tracing of a graph G is an oriented walk double covering that consists of a single closed walk. A retracting in a closed walk is the immediate succession of an edge by its inverse. Every graph with minimum degree 2 has a retracting free oriented walk double covering and every connected graph has a bidirectional double tracing. The minimum number of closed walks in a retracting free oriented walk double covering of G is denoted by c(G). The minimum number of retractings in a bidirectional double tracing of G is denoted by r(G). We shall prove that for all connected noncycle graphs G with minimum degree at least 2, r(G) = c(G) − 1. The problem of characterizing those graphs G for which r(G) = 0 was raised by Ore. Thomassen solved this problem by relating it to the existence of certain spanning trees. We generalize this result, and relate the parameters r(G), c(G) to spanning trees of G. This relation yields a polynomial time algorithm to determine the parameters c(G) and r(G). © 1998 John Wiley & Sons, Inc. J. Graph Theory 29: 89–102, 1998     

On the complexity of rainbow spanning forest problem

Given a graph \(G=(V,E,L)\) and a coloring function \(\ell : E \rightarrow L\), that assigns a color to each edge of G from a finite color set L, the rainbow spanning forest problem (RSFP) consists of finding a rainbow spanning forest of G such that the number of components is minimum. A spanning forest is rainbow if all its components (trees) are rainbow. A component whose edges have all different colors is called rainbow component. The RSFP on general graphs is known to be NP-complete. In this paper we use the 3-SAT Problem to prove that the RSFP is NP-complete on trees and we prove that the problem is solvable in polynomial time on paths, cycles and if the optimal solution value is equal to 1. Moreover, we provide an approximation algorithm for the RSFP on trees and we show that it approximates the optimal solution within 2.     

Sufficient conditions for graphs to be λ′‐optimal,super‐edge‐connected,and maximally edge‐connected

The restricted‐edge‐connectivity of a graph G, denoted by λ′(G), is defined as the minimum cardinality over all edge‐cuts S of G, where G‐S contains no isolated vertices. The graph G is called λ′‐optimal, if λ′(G) = ξ(G), where ξ(G) is the minimum edge‐degree in G. A graph is super‐edge‐connected, if every minimum edge‐cut consists of edges adjacent to a vertex of minimum degree. In this paper, we present sufficient conditions for arbitrary, triangle‐free, and bipartite graphs to be λ′‐optimal, as well as conditions depending on the clique number. These conditions imply super‐edge‐connectivity, if δ (G) ≥ 3, and the equality of edge‐connectivity and minimum degree. Different examples will show that these conditions are best possible and independent of other results in this area. © 2005 Wiley Periodicals, Inc. J Graph Theory 48: 228–246, 2005     

The complexity of a minimum reload cost diameter problem

We consider the minimum diameter spanning tree problem under the reload cost model which has been introduced by Wirth and Steffan [H.-C. Wirth, J. Steffan, Reload cost problems: Minimum diameter spanning tree, Discrete Appl. Math. 113 (2001) 73-85]. In this model an undirected edge-coloured graph G is given, together with a nonnegative symmetrical integer matrix R specifying the costs of changing from a colour to another one. The reload cost of a path in G arises at its internal nodes, when passing from the colour of one incident edge to the colour of the other. We prove that, unless P=NP, the problem of finding a spanning tree of G having a minimum diameter with respect to reload costs, when restricted to graphs with maximum degree 4, cannot be approximated within any constant α<2 if the reload costs are unrestricted, and cannot be approximated within any constant β<5/3 if the reload costs satisfy the triangle inequality. This solves a problem left open by Wirth and Steffan [H.-C. Wirth, J. Steffan, Reload cost problems: minimum diameter spanning tree, Discrete Appl. Math. 113 (2001) 73-85].     

A Characterization of the degree sequences of 2‐trees

A graph G is a 2‐tree if G = K₃, or G has a vertex v of degree 2, whose neighbors are adjacent, and G/ v is a 2‐ tree. A characterization of the degree sequences of 2‐trees is given. This characterization yields a linear‐time algorithm for recognizing and realizing degree sequences of 2‐trees. © 2008 Wiley Periodicals, Inc. J Graph Theory 58:191‐209, 2008     

Partial inverse maximum spanning tree in which weight can only be decreased under $$l_p$$-norm

The maximum or minimum spanning tree problem is a classical combinatorial optimization problem. In this paper, we consider the partial inverse maximum spanning tree problem in which the weight function can only be decreased. Given a graph, an acyclic edge set, and an edge weight function, the goal of this problem is to decrease weights as little as possible such that there exists with respect to function containing the given edge set. If the given edge set has at least two edges, we show that this problem is APX-Hard. If the given edge set contains only one edge, we present a polynomial time algorithm.     

On routing in VLSI design and communication networks

In this paper, we study the global routing problem in VLSI design and the multicast routing problem in communication networks. First we propose new and realistic models for both problems. In the global routing problem in VLSI design, we are given a lattice graph and subsets of the vertex set. The goal is to generate trees spanning these vertices in the subsets to minimize a linear combination of overall wirelength (edge length) and the number of bends of trees with respect to edge capacity constraints. In the multicast routing problem in communication networks, a graph is given to represent the network, together with subsets of the vertex set. We are required to find trees to span the given subsets and the overall edge length is minimized with respect to capacity constraints. Both problems are APX-hard. We present the integer linear programming (LP) formulation of both problems and solve the LP relaxations by the fast approximation algorithms for min-max resource-sharing problems in [K. Jansen, H. Zhang, Approximation algorithms for general packing problems and their application to the multicast congestion problem, Math. Programming, to appear, doi:10.1007/s10107-007-0106-8] (which is a generalization of the approximation algorithm proposed by Grigoriadis and Khachiyan [Coordination complexity of parallel price-directive decomposition, Math. Oper. Res. 2 (1996) 321-340]). For the global routing problem, we investigate the particular property of lattice graphs and propose a combinatorial technique to overcome the hardness due to the bend-dependent vertex cost. Finally, we develop asymptotic approximation algorithms for both problems with ratios depending on the best known approximation ratio for the minimum Steiner tree problem. They are the first known theoretical approximation bound results for the problems of minimizing the total costs (including both the edge and the bend costs) while spanning all given subsets of vertices.     

Polynomial area bounds for MST embeddings of trees

In their seminal paper on geometric minimum spanning trees, Monma and Suri (1992) [31] showed how to embed any tree of maximum degree 5 as a minimum spanning tree in the Euclidean plane. The embeddings provided by their algorithm require area O(n²²)×O(n²²) and the authors conjectured that an improvement below cn×cn is not possible, for some constant c>0. In this paper, we show how to construct MST embeddings of arbitrary trees of maximum degree 3 and 4 within polynomial area.     

An Inverse-Ackermann Type Lower Bound For Online Minimum Spanning Tree Verification*

Given a spanning tree T of some graph G, the problem of minimum spanning tree verification is to decide whether T = MST(G). A celebrated result of Komlós shows that this problem can be solved with a linear number of comparisons. Somewhat unexpectedly, MST verification turns out to be useful in actually computing minimum spanning trees from scratch. It is this application that has led some to wonder whether a more flexible version of MST verification could be used to derive a faster deterministic minimum spanning tree algorithm. In this paper we consider the online MST verification problem in which we are given a sequence of queries of the form “Is e in the MST of T ∪{e}?”, where the tree T is fixed. We prove that there are no linear-time solutions to the online MST verification problem, and in particular, that answering m queries requires Ω(mα(m,n)) time, where α(m,n) is the inverse-Ackermann function and n is the size of the tree. On the other hand, we show that if the weights of T are permuted randomly there is a simple data structure that preprocesses the tree in expected linear time and answers queries in constant time. * A preliminary version of this paper appeared in the proceedings of the 43rd IEEE Symposium on Foundations of Computer Science (FOCS 2002), pages 155–163. † This work was supported by Texas Advanced Research Program Grant 003658-0029-1999, NSF Grant CCR-9988160, and an MCD Graduate Fellowship.     

On the inverse problem of minimum spanning tree with partition constraints

In this paper we first discuss the properties of minimum spanning tree and minimum spanning tree with partition constraints. We then concentrate on the inverse problem of minimum spanning tree with partition constraints in which we need to adjust the weights of the edges in a network as less as possible so that a given spanning tree becomes the minimum one among all spanning trees that satisfy the partition restriction. Based on the calculation of maximum cost flow in networks, we propose a strongly polynomial algorithm for solving the problem.The author gratefully acknowledges the partial support of Croucher Foundation.     

On spanning tree congestion of graphs

Let G be a connected graph and T be a spanning tree of G. For e∈E(T), the congestion of e is the number of edges in G connecting two components of T−e. The edge congestion ofGinT is the maximum congestion over all edges in T. The spanning tree congestion ofG is the minimum congestion of G in its spanning trees. In this paper, we show the spanning tree congestion for the complete k-partite graphs and the two-dimensional tori. We also address lower bounds of spanning tree congestion for the multi-dimensional grids and the hypercubes.     

Multicuts in unweighted graphs and digraphs with bounded degree and bounded tree-width

The Multicut problem can be defined as: given a graph G and a collection of pairs of distinct vertices {s_i,t_i} of G, find a minimum set of edges of G whose removal disconnects each s_i from the corresponding t_i. Multicut is known to be NP-hard and Max SNP-hard even when the input graph is restricted to being a tree. The main result of the paper is a polynomial-time approximation scheme (PTAS) for Multicut in unweighted graphs with bounded degree and bounded tree-width. That is, for any ε>0, we present a polynomial-time (1+ε)-approximation algorithm. In the particular case when the input is a bounded-degree tree, we have a linear-time implementation of the algorithm. We also provide some hardness results: we prove that Multicut is still NP-hard for binary trees and that it is Max SNP-hard if we drop any of the three conditions (unweighted, bounded-degree, bounded tree-width). Finally we show that some of these results extend to the vertex version of Multicut and to a directed version of Multicut.