Блог пользователя TAhmed33

Автор TAhmed33, история, 5 месяцев назад, По-английски

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.

  • Проголосовать: нравится
  • +46
  • Проголосовать: не нравится

»
5 месяцев назад, скрыть # |
 
Проголосовать: нравится +24 Проголосовать: не нравится

bro we should've tried harder and used it as div 1 F :wilted_rose:

»
5 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by TAhmed33 (previous revision, new revision, compare).

»
5 месяцев назад, скрыть # |
 
Проголосовать: нравится -8 Проголосовать: не нравится

Elegia could you please help him

»
5 месяцев назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +12 Проголосовать: не нравится

I sent this to Fable 5 Max, let's see what happens. He's been thinking for 15 minutes. Unfortunately it looks like he stopped thinking for some reason but hopefully will continue.

Update: no response was generated but my usage was consumed.

»
5 месяцев назад, скрыть # |
 
Проголосовать: нравится +60 Проголосовать: не нравится

Shockingly, after back and forth with 5.5 Pro and Fable, and about 20 bucks in credits, and verifying up to $$$n \lesssim 20$$$, and forcing the models to double-check their work, I got a solution.

Solution