Minimum Degree Spanning Tree Without Restricting Vertices Searched

Question

This is reposted 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), 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 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.

Answer 1

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)