Termination conjecture for the refined Disk Tree algorithm

Let GG be a graph with tree-length tl(G)tl(G), and let (Ti,ϕi)(T_i,\phi_i), HiH_i, SiS_i, Bk(xi)B_k(x_i), and property PiP_i be as in the (k,)(k,\ell)-Disk Tree algorithm. Suppose that k==tl(G)k=\ell=tl(G), and that whenever there is an option between removing zz or yy while iteratively removing vertices from SiBk(xi)S_i\cap B_k(x_i) until TiT_i satisfies PiP_i, the algorithm removes zz if d(z,xi)>d(y,xi)d(z,x_i)>d(y,x_i). Termination conjecture for the refined Disk Tree algorithm. Under these conditions, there exists an rr such that Hr=GH_r=G. This would establish termination at the tree-length parameter and support the conjectured 22-approximation refinement.

Sources & referencesView supporting material

Primary source

Matthew Yancey, “Negatively Curved Graphs”, arXiv:1512.01281 (2021).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.