<p>This is not an answer, but some experimental evidence on why I think this <em>might</em> be an <span class="math-container">$OPT+1$</span> approximation.</p>
<p>I wrote some python code that runs the local search algorithm (without restricting the vertices searched) and solves the problem optimally with ILP. I tried it on thousands of small random graphs and the local search was always <span class="math-container">$OPT$</span> or <span class="math-container">$OPT+1$</span>. Here is the code:</p>
<pre><code>import networkx as nx
from pulp import *

def local_search(G):
    T = nx.algorithms.tree.mst.minimum_spanning_tree(G)

    while True:
        noChange = True
        for w in G:
            for u,v in G.edges():
                Tset = set(T.edges())
                if (u,v) not in Tset:
                    T.add_edge(u,v)
                    C = nx.algorithms.cycles.find_cycle(T)
                    T.remove_edge(u,v)
                    C_vertices = set([x for y in C for x in y ])
                    if w in C_vertices and T.degree[w]&gt;=max(T.degree[u], T.degree[v])+2:
                        T.add_edge(u,v)
                        for x,y in C:
                            if x==w or y==w:
                                T.remove_edge(x,y)
                                break 
                        noChange = False
        if noChange:
            break
    return max([T.degree[u] for u in G]), T

def opt_soln(G):
    prob = LpProblem(&quot;The Minimum Degree Spanning Degree&quot;,LpMinimize)
    z = LpVariable(&quot;maxIndegree&quot;,1,None,LpInteger)
    variables = {
        tuple(sorted([u,v])) : LpVariable(f&quot;x_{(u,v)}&quot;,0,1,LpInteger) for u,v in G.edges()
    }
    vertex_to_edges = {
        u : [variables[tuple(sorted([u,v]))] for v in G.neighbors(u)] for u in G
    }
    prob += z
    prob += lpSum(variables.values()) == (len(G)-1)
    for u in G:
        prob += lpSum(vertex_to_edges[u]) &lt;= z
    prob.solve()
    return value(prob.objective)


tries = 1000
for _ in range(tries):
    n = 34
    p = 0.1
    d = 10
    G = nx.generators.random_graphs.fast_gnp_random_graph(n, p)
    #G = nx.generators.random_graphs.random_regular_graph(d, n)
    if not nx.is_connected(G):
        continue 
    delta_T, T = local_search(G)
    delta_star = opt_soln(G)
    if delta_T-  int(delta_star)&gt;1:
        print(delta_star, delta_T)
    #nx.draw(T)
</code></pre>

CC BY-SA 4.0
2021-02-24T04:34:44.397Z
2021-02-24T04:34:44.397Z
user3508551
<p>This is <a href="https://cs.stackexchange.com/questions/135287/minimum-degree-spanning-tree-without-restricting-vertices-searched">reposted</a> from cs.stackexchange. I asked the question more than two weeks ago and got no answers, so I thought to repost here.</p>
<p>I am currently self studying approximation algorithms from <em>The Design of Approximation Algorithms</em> (Williamson and Schmoys; page 50 <a href="https://www.designofapproxalgs.com/book.pdf" rel="nofollow noreferrer">here</a>), specifically the minimum-degree spanning trees (MDST) problem. Given a graph <span class="math-container">$G$</span>, we need to find a spanning tree <span class="math-container">$T$</span> that minimizes the maximum degree of any vertex in <span class="math-container">$T$</span>.</p>
<p>I understand that the local search algorithm attempts to look at vertices with degree at least <span class="math-container">$\Delta(T)-\lceil \log_2(n)\rceil $</span> and try to improve it, and only stops when one cannot improve any such vertex. I understand that this restriction is done to polynomially bound the run time of the algorithm.</p>
<p>My question is, what approximation ratio can we get if we try to improve any vertex? I understand that we cannot show that it runs in polynomial time, but what approximation ratio would hold? Obviously the <span class="math-container">$2OPT+\lceil \log_2(n)\rceil$</span> still holds, but can we improve the ratio by trying all vertices? I tried to read the <a href="https://www.researchgate.net/publication/220779201_Approximating_the_Minimum_Degree_Spanning_Tree_to_Within_One_from_the_Optimal_Degree" rel="nofollow noreferrer">original</a> paper which had another local search algorithm with cost <span class="math-container">$OPT+1$</span>, but I am not able to prove that this locally optimal tree for all vertices is also an <span class="math-container">$OPT+1$</span> algorithm.</p>

<approximation-algorithms>
Minimum Degree Spanning Tree Without Restricting Vertices Searched
user3508551
# Minimum Degree Spanning Tree Without Restricting Vertices Searched

(Asked by: username_0 on 2021-02-24)

This is [reposted](https://cs.stackexchange.com/questions/135287/minimum-degree-spanning-tree-without-restricting-vertices-searched) from cs.stackexchange. I asked the question more than two weeks ago and got no answers, so I thought to repost here.

I am currently self studying approximation algorithms from *The Design of Approximation Algorithms* (Williamson and Schmoys; page 50 [here](https://www.designofapproxalgs.com/book.pdf)), specifically the minimum-degree spanning trees (MDST) problem. Given a graph $G$, we need to find a spanning tree $T$ that minimizes the maximum degree of any vertex in $T$.

I understand that the local search algorithm attempts to look at vertices with degree at least $\Delta(T)-\lceil \log\_2(n)\rceil $ and try to improve it, and only stops when one cannot improve any such vertex. I understand that this restriction is done to polynomially bound the run time of the algorithm.

My question is, what approximation ratio can we get if we try to improve any vertex? I understand that we cannot show that it runs in polynomial time, but what approximation ratio would hold? Obviously the $2OPT+\lceil \log\_2(n)\rceil$ still holds, but can we improve the ratio by trying all vertices? I tried to read the [original](https://www.researchgate.net/publication/220779201_Approximating_the_Minimum_Degree_Spanning_Tree_to_Within_One_from_the_Optimal_Degree) paper which had another local search algorithm with cost $OPT+1$, but I am not able to prove that this locally optimal tree for all vertices is also an $OPT+1$ algorithm.

**Tags:** approximation-algorithms


---

## 1 answers

### Answer by username_0 on 2021-02-24. Score: 0

This is not an answer, but some experimental evidence on why I think this might be an $OPT+1$ approximation.
I wrote some python code that runs the local search algorithm (without restricting the vertices searched) and solves the problem optimally with ILP. I tried it on thousands of small random graphs and the local search was always $OPT$ or $OPT+1$. Here is the code:
import networkx as nx
from pulp import *

def local_search(G):
    T = nx.algorithms.tree.mst.minimum_spanning_tree(G)

    while True:
        noChange = True
        for w in G:
            for u,v in G.edges():
                Tset = set(T.edges())
                if (u,v) not in Tset:
                    T.add_edge(u,v)
                    C = nx.algorithms.cycles.find_cycle(T)
                    T.remove_edge(u,v)
                    C_vertices = set([x for y in C for x in y ])
                    if w in C_vertices and T.degree[w]>=max(T.degree[u], T.degree[v])+2:
                        T.add_edge(u,v)
                        for x,y in C:
                            if x==w or y==w:
                                T.remove_edge(x,y)
                                break 
                        noChange = False
        if noChange:
            break
    return max([T.degree[u] for u in G]), T

def opt_soln(G):
    prob = LpProblem("The Minimum Degree Spanning Degree",LpMinimize)
    z = LpVariable("maxIndegree",1,None,LpInteger)
    variables = {
        tuple(sorted([u,v])) : LpVariable(f"x_{(u,v)}",0,1,LpInteger) for u,v in G.edges()
    }
    vertex_to_edges = {
        u : [variables[tuple(sorted([u,v]))] for v in G.neighbors(u)] for u in G
    }
    prob += z
    prob += lpSum(variables.values()) == (len(G)-1)
    for u in G:
        prob += lpSum(vertex_to_edges[u]) <= z
    prob.solve()
    return value(prob.objective)


tries = 1000
for _ in range(tries):
    n = 34
    p = 0.1
    d = 10
    G = nx.generators.random_graphs.fast_gnp_random_graph(n, p)
    #G = nx.generators.random_graphs.random_regular_graph(d, n)
    if not nx.is_connected(G):
        continue 
    delta_T, T = local_search(G)
    delta_star = opt_soln(G)
    if delta_T-  int(delta_star)>1:
        print(delta_star, delta_T)
    #nx.draw(T)


---

