Unit interval vertex deletion: fewer vertices are relevant

DOI10.1016/J.JCSS.2018.01.001zbMATH Open1391.68058arXiv1607.01162OpenAlexW2964327184WikidataQ130160419 ScholiaQ130160419MaRDI QIDQ1747495

Author name not available (Why is that?)

Publication date: 8 May 2018

Published in: (Search for Journal in Brave)

Abstract: The unit interval vertex deletion problem asks for a set of at most $k$ vertices whose deletion from an $n$-vertex graph makes it a unit interval graph. We develop an $O(k^4)$-vertex kernel for the problem, significantly improving the $O(k^{53})$-vertex kernel of Fomin, Saurabh, and Villanger [ESA'12; SIAM J. Discrete Math 27(2013)]. We introduce a novel way of organizing cliques of a unit interval graph. Our constructive proof for the correctness of our algorithm, using interval models, greatly simplifies the destructive proofs, based on forbidden induced subgraphs, for similar problems in literature.

Full work available at URL: https://arxiv.org/abs/1607.01162

zbMATH Keywords

No records found.

Mathematics Subject Classification ID

No records found.

This page was built for publication: Unit interval vertex deletion: fewer vertices are relevant

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1747495)