Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userReorganizing topologies of Steiner trees to accelerate their elimination
173
0
0.0
(
0
)
Added by
Aymeric Grodet
Publication date
2015
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We describe a technique to reorganize topologies of Steiner trees by exchanging neighbors of adjacent Steiner points. We explain how to use the systematic way of building trees, and therefore topologies, to find the correct topology after nodes have been exchanged. Topology reorganizations can be inserted into the enumeration scheme commonly used by exact algorithms for the Euclidean Steiner tree problem in $d$-space, providing a method of improvement different than the usual approaches. As an example, we show how topology reorganizations can be used to dynamically change the exploration of the usual branch-and-bound tree when two Steiner points collide during the optimization process. We also turn our attention to the erroneous use of a pre-optimization lower bound in the original algorithm and give an example to confirm its usage is incorrect. In order to provide numerical results on correct solutions, we use planar equilateral points to quickly compute this lower bound, even in dimensions higher than two. Finally, we describe planar twin trees, identical trees yielded by different topologies, whose generalization to higher dimensions could open a new way of building Steiner trees.
rate research
Read More
In the classical Steiner tree problem, given an undirected, connected graph $G=(V,E)$ with non-negative edge costs and a set of emph{terminals} $Tsubseteq V$, the objective is to find a minimum-cost tree $E subseteq E$ that spans the terminals. The problem is APX-hard; the best known approximation algorithm has a ratio of $rho = ln(4)+varepsilon < 1.39$. In this paper, we study a natural generalization, the emph{multi-level Steiner tree} (MLST) problem: given a nested sequence of terminals $T_{ell} subset dots subset T_1 subseteq V$, compute nested trees $E_{ell}subseteq dots subseteq E_1subseteq E$ that span the corresponding terminal sets with minimum total cost. The MLST problem and variants thereof have been studied under various names including Multi-level Network Design, Quality-of-Service Multicast tree, Grade-of-Service Steiner tree, and Multi-Tier tree. Several approximation results are known. We first present two simple $O(ell)$-approximation heuristics. Based on these, we introduce a rudimentary composite algorithm that generalizes the above heuristics, and determine its approximation ratio by solving a linear program. We then present a method that guarantees the same approximation ratio using at most $2ell$ Steiner tree computations. We compare these heuristics experimentally on various instances of up to 500 vertices using three different network generation models. We also present various integer linear programming (ILP) formulations for the MLST problem, and compare their running times on these instances. To our knowledge, the composite algorithm achieves the best approximation ratio for up to $ell=100$ levels, which is sufficient for most applications such as network visualization or designing multi-level infrastructure.
We consider a natural variant of the well-known Feedback Vertex Set problem, namely the problem of deleting a small subset of vertices or edges to a full binary tree. This version of the problem is motivated by real-world scenarios that are best modeled by full binary trees. We establish that bo
In the literature on parameterized graph problems, there has been an increased effort in recent years aimed at exploring novel notions of graph edit-distance that are more powerful than the size of a modulator to a specific graph class. In this line of research, Bulian and Dawar [Algorithmica, 2016] introduced the notion of elimination distance and showed that deciding whether a given graph has elimination distance at most $k$ to any minor-closed class of graphs is fixed-parameter tractable parameterized by $k$ [Algorithmica, 2017]. There has been a subsequent series of results on the fixed-parameter tractability of elimination distance to various graph classes. However, one class of graph classes to which the computation of elimination distance has remained open is the class of graphs that are characterized by the exclusion of a family ${cal F}$ of finite graphs as topological minors. In this paper, we settle this question by showing that the problem of determining elimination distance to such graphs is also fixed-parameter tractable.
Among other results, we prove the following theorem about Steiner minimal trees in $d$-dimensional Euclidean space: if two finite sets in $mathbb{R}^d$ have unique and combinatorially equivalent Steiner minimal trees, then there is a homotopy between the two sets that maintains the uniqueness and the combinatorial structure of the Steiner minimal tree throughout the homotopy.
Graph neural networks have been successful in many learning problems and real-world applications. A recent line of research explores the power of graph neural networks to solve combinatorial and graph algorithmic problems such as subgraph isomorphism, detecting cliques, and the traveling salesman problem. However, many NP-complete problems are as of yet unexplored using this method. In this paper, we tackle the Steiner Tree Problem. We employ four learning frameworks to compute low cost Steiner trees: feed-forward neural networks, graph neural networks, graph convolutional networks, and a graph attention model. We use these frameworks in two fundamentally different ways: 1) to train the models to learn the actual Steiner tree nodes, 2) to train the model to learn good Steiner point candidates to be connected to the constructed tree using a shortest path in a greedy fashion. We illustrate the robustness of our heuristics on several random graph generation models as well as the SteinLib data library. Our finding suggests that the out-of-the-box application of GNN methods does worse than the classic 2-approximation method. However, when combined with a greedy shortest path construction, it even does slightly better than the 2-approximation algorithm. This result sheds light on the fundamental capabilities and limitations of graph learning techniques on classical NP-complete problems.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
