Polynomial-time complexity of distance- independent set reconfiguration on trees under token sliding
Polynomial-time complexity of distance- independent set reconfiguration on trees under token sliding
Let . In distance- independent set reconfiguration, denoted by , configurations are distance- independent sets, and under the token-sliding rule, denoted by , one token may slide along an edge in each move. The input graph is a tree. Polynomial-time reconfiguration conjecture. under on trees is in for . The complexity of this problem is stated in the source to remain unknown, so this is an open problem concerning reconfiguration on trees.
Sources & referencesView supporting material
Primary source
Duc A. Hoang, “On the Complexity of Distance-d Independent Set Reconfiguration”, arXiv:2208.07199 (2024).
Additional references
2 papers in this index state this conjecture (2021–2022). The statement above is taken from the most recent of them; the others are arXiv:2105.03402.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.