2026-06-09T18:44:50Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23402 2025-10-02T12:54:11Z ddc:004 open_access

Mim-Width Is paraNP-Complete Bergougnoux, Benjamin Bonnet, Édouard Duron, Julien Mim-width lower bounds parameterized complexity ordered graphs 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. A key intermediate problem that we introduce and show NP-complete, Linear Degree Balancing, inputs an edge-weighted graph G and an integer τ, and asks whether V(G) can be linearly ordered such that every vertex of G has weighted backward and forward degrees at most τ. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Benjamin Bergougnoux and Édouard Bonnet and Julien Duron 2025 Is Part Of LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2025.25 urn:nbn:de:0030-drops-234020 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.25 eng https://creativecommons.org/licenses/by/4.0/legalcode