Given a tree on $n$ nodes, perform the following operation as many times as you like (including zero times): Choose four nodes connected in a chain, and contract them to a single node, merging their adjacency lists. Output the minimum size you can reduce the tree to.↵
↵
Does anyone know how to find a polynomial time solution for this, or prove that the problem is NP-Complete? It seems very difficult for me. Has anyone seen this problem, or something equivalent, before?↵
↵
I tried it for very long, and then I gave it to several IGMs and they couldn't solve it, and ChatGPT 5.5 Pro can neither solve it nor prove NP-completeness.
↵
Does anyone know how to find a polynomial time solution for this, or prove that the problem is NP-Complete? It seems very difficult for me. Has anyone seen this problem, or something equivalent, before?↵
↵
I tried it for very long, and then I gave it to several IGMs and they couldn't solve it, and ChatGPT 5.5 Pro can neither solve it nor prove NP-completeness.
