The reviewed record of science sign in
Pith

arxiv: 2501.05638 · v1 · pith:YNTRCXD6 · submitted 2025-01-10 · cs.CC · cs.DM· cs.DS· math.CO

Mim-Width is paraNP-complete

Benjamin Bergougnoux , \'Edouard Bonnet , Julien Duron This is my paper

Reviewed by Pith T0 review T1 audit T2 compute T3 formal T4 kernel pith:YNTRCXD6record.jsonopen to challenge →

classification cs.CC cs.DMcs.DSmath.CO
keywords mim-widthgraphslinearparanp-completesim-widthboundedcomputeconstant
0
0 comments X
read the original abstract

We show that it is NP-hard to distinguish graphs of linear mim-width at most 1211 from graphs of sim-width at least 1216. This implies that Mim-Width, Sim-Width, One-Sided Mim-Width, and their linear counterparts are all paraNP-complete, i.e., NP-complete to compute even when upper bounded by a constant.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.