2026-07-23T16:56:32Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19310 2024-03-06T11:03:44Z ddc:004 open_access

Recognizing Unit Multiple Intervals Is Hard Ardévol Martínez, Virginia Rizzi, Romeo Sikora, Florian Vialette, Stéphane Interval graphs unit multiple interval graphs recognition NP-hardness Multiple interval graphs are a well-known generalization of interval graphs introduced in the 1970s to deal with situations arising naturally in scheduling and allocation. A d-interval is the union of d intervals on the real line, and a graph is a d-interval graph if it is the intersection graph of d-intervals. In particular, it is a unit d-interval graph if it admits a d-interval representation where every interval has unit length. Whereas it has been known for a long time that recognizing 2-interval graphs and other related classes such as 2-track interval graphs is NP-complete, the complexity of recognizing unit 2-interval graphs remains open. Here, we settle this question by proving that the recognition of unit 2-interval graphs is also NP-complete. Our proof technique uses a completely different approach from the other hardness results of recognizing related classes. Furthermore, we extend the result for unit d-interval graphs for any d ⩾ 2, which does not follow directly in graph recognition problems -as an example, it took almost 20 years to close the gap between d = 2 and d > 2 for the recognition of d-track interval graphs. Our result has several implications, including that recognizing (x, …, x) d-interval graphs and depth r unit 2-interval graphs is NP-complete for every x ⩾ 11 and every r ⩾ 4. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Virginia Ardévol Martínez and Romeo Rizzi and Florian Sikora and Stéphane Vialette 2023 Is Part Of LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2023.8 urn:nbn:de:0030-drops-193102 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.8 eng https://creativecommons.org/licenses/by/4.0/legalcode