Suboptimal contraction sequences?

[manpen]

Dear Gabriel Bathie,

thank you for providing this interesting solver! I'm currently trying to build an archive of solved twin width instances. While doing so, I noticed that ---on my machine--- tinywidth occasionally produces correct contraction sequences with suboptimal twin-width. You can find a collection of test instances here. Each file includes the optimal twin width (as computed by multiple solvers) in its filename.

Below is a log of instances tinywidth produces suboptimal results on my machine (where tww exp is the expected twin width and tww comp the tww computed by tinywidth).

Could you please check whether you can reproduce these computations or whether I inadvertently introduced a bug during compilation. For your convenience I attached the first graph directly to this issue n015_m0053_tww003_ba03f68e185844a2.txt

Thank you and best, Manuel (Penschuck)

n015_m0053_tww003_ba03f68e185844a2.gr              time: 0.2s tww exp:  3 tww comp:  4 ---MISMATCH---
n018_m0088_tww004_f47c41158d04b0e2.gr              time: 0.2s tww exp:  4 tww comp:  5 ---MISMATCH---
n020_m0065_tww003_cir6_7634ffb65bde82fb.gr         time: 0.2s tww exp:  3 tww comp:  4 ---MISMATCH---
n015_m0038_tww003_7c66b955328e197a.gr              time: 0.2s tww exp:  3 tww comp:  4 ---MISMATCH---
n015_m0043_tww003_6d3a572782df1692.gr              time: 0.2s tww exp:  3 tww comp:  4 ---MISMATCH---
n015_m0050_tww003_5bac9e54824fabe8.gr              time: 0.2s tww exp:  3 tww comp:  4 ---MISMATCH---
n018_m0107_tww001_cir3_cf6767b8e680e822.gr         time: 0.2s tww exp:  1 tww comp:  2 ---MISMATCH---
n015_m0089_tww001_03fcef79891a8c0a.gr              time: 0.2s tww exp:  1 tww comp:  2 ---MISMATCH---
n018_m0126_tww002_fa6ad55254c2701a.gr              time: 0.3s tww exp:  2 tww comp:  3 ---MISMATCH---
n015_m0040_tww003_1549a2e658bf6f6d.gr              time: 0.2s tww exp:  3 tww comp:  4 ---MISMATCH---
n015_m0015_tww001_cir3_2d53a1d382909b1f.gr         time: 0.1s tww exp:  1 tww comp:  2 ---MISMATCH---
n020_m0056_tww004_54f9fead202b6cf5.gr              time: 0.3s tww exp:  4 tww comp:  5 ---MISMATCH---
n015_m0049_tww003_1b55c5119769f979.gr              time: 0.2s tww exp:  3 tww comp:  4 ---MISMATCH---

[GBathie]

Hi Manuel,

Thank you for opening this issue. I ran your example on my machine, and can confirm that the solver finds a suboptimal contraction sequence. From the (limited) debug information, it seems that the solver find a lower bound of 4, and hence declares that the solution is optimal. However, the lower bound recursively uses the branch and bound algorithm, so I'm not sure where the problem lies.

A first step towards debugging: I tried turning off kernelization, and the problem persists, hence the problem does likely not come from that part. However, the issue seems to disappear when always going into the "large graphs branch", which also uses the "dense graphs" algorithm in the lower bound. But in that case, the lower bound never finds a value of 4.

I would be lying if I said I will have time to look into this in the near future, so if you are willing to investigate it, you are welcome to do so ! Otherwise, I will do it... later.

Thank you for raising the issue anyway,
Best,
Gabriel

[manpen]

Hi Gabriel,

thank you for your feedback. It's too bad, I hoped I just made an easily fixable mistake when deploying the solver :(

Currently the bug is no show stopper for me, since the vast majority of contraction sequences are correct and I consider only solutions that have been solved by multiple independent algorithms anyhow --- therefore the buggy ones can be easily discarded.

Unfortunately I, too, won't have the time to debug the issue.

Best, Manuel