0
$\begingroup$

I have the problem of calculating a good approximation of the minimimum-weight spanning tree with vertex-degrees in $\lbrace 1,3\rbrace$ of a complete symmetric graph, without parallel edges or self-loops, with $n=2k$ vertices.

Question:

which heuristics for the problem of finding a good approximation to the minimum-weight spanning tree with vertex-degrees $1$ and $3$ of a complete weighted graph are known?

To clarify: I am not looking for "spanning trees of regular graphs" and also not for "spanning trees with many leaf nodes"; that is what googling "regular spanning tree" brings up.

Improve this question
$\endgroup$
2
  • $\begingroup$ I'd conjecture that no good approx guarantee can be achieved. In an unweighted graph, deciding if there is a $\{1, 2\}$-spanning tree is NP-hard (that's the Hamiltonian path problem). This is used to show that finding a min-weight $\{1, 2\}$-spanning tree in a complete graph, i.e. TSP, can't be approximated by essentially any ratio (by replacing non-edges with edges of huge weight). The same ideas should apply to $\{1, 3\}$-spanning trees. It's probably NP-hard to find one in unweighted graphs, making the weighted complete version inapproximable. Requires proof though. $\endgroup$
    – Manuel Lafond
    Commented Nov 22, 2021 at 20:30
  • $\begingroup$ Of course the inapproximability for $\lbrace 1, 2\rbrace$ edge weights is plausible, but there are also situations where the edgeweights allow for good approximation ratios, most prominently the planar Euclidean TSP and I am looking for heursitics for the problem stated as the above question that work well in specific situations. $\endgroup$
    – Manfred Weis
    Commented Nov 27, 2021 at 14:44

1 Answer 1

Reset to default
0
$\begingroup$

This should rather be seen as comment!

meanwhile some ideas came to my mind that I'd like to share in hope to provoke answers to my question.

$1$st idea: Tweak Prim's MST algorithm

  • start with a single edge
  • while there are undiscovered vertices
    • add to the $\lbrace 1,3\rbrace$-tree the pair $(\lambda_i, u_j).(\lambda_i, u_j)$ of edges of lightest weightsum that are adjacent to the same leaf node $\lambda_i$ and undiscovered vertices $u_j$ and $u_k$.

The complexity should be $O(n^2\log\,n)$ and I'm convinced that that heuristic must already be known.


$2$nd idea: "Wavefront expansion"

  • start with a single edge or a claw graph $K_{1,3}$
  • while there are undiscovered vertices
    • temporarily split the leaf-vertices
    • optimally match the copies of the leaf vertices to the set of undiscovered vertices
    • add the edges of that optimal matching to the $\lbrace1,3\rbrace$-tree.

The complexity is likely $O(n^3)$ and also that algorithm isn't very sophisticated and should have been mentioned already.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .