Show simple item record

Twin-width and polynomial kernels

hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorBonnet, Edouard
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorKim, Eun Jung
dc.contributor.authorReinald, Amadeus
dc.contributor.authorThomassé, Stéphan
dc.contributor.authorWatrigant, Rémi
dc.date.accessioned2022-02-28T09:25:56Z
dc.date.available2022-02-28T09:25:56Z
dc.date.issued2021
dc.identifier.urihttps://basepub.dauphine.psl.eu/handle/123456789/22786
dc.language.isoenen
dc.subjectTwin-widthen
dc.subjectkernelizationen
dc.subjectDominating Seten
dc.subjectlower boundsen
dc.subject.ddc004en
dc.titleTwin-width and polynomial kernelsen
dc.typeCommunication / Conférence
dc.description.abstractenWe study the existence of polynomial kernels, for parameterized problems without a polynomial kernel on general graphs, when restricted to graphs of bounded twin-width. Our main result is that a polynomial kernel for k-Dominating Set on graphs of twin-width at most 4 would contradict a standard complexity-theoretic assumption. The reduction is quite involved, especially to get the twin-width upper bound down to 4, and can be tweaked to work for Connected k-Dominating Set and Total k-Dominating Set (albeit with a worse upper bound on the twin-width). The k-Independent Set problem admits the same lower bound by a much simpler argument, previously observed [ICALP '21], which extends to k-Independent Dominating Set, k-Path, k-Induced Path, k-Induced Matching, etc. On the positive side, we obtain a simple quadratic vertex kernel for Connected k-Vertex Cover and Capacitated k-Vertex Cover on graphs of bounded twin-width. Interestingly the kernel applies to graphs of Vapnik-Chervonenkis density 1, and does not require a witness sequence. We also present a more intricate O(k^1.5) vertex kernel for Connected k-Vertex Cover. Finally we show that deciding if a graph has twin-width at most 1 can be done in polynomial time, and observe that most optimization/decision graph problems can be solved in polynomial time on graphs of twin-width at most 1.en
dc.identifier.citationpages6:1-6:13en
dc.relation.ispartofeditorGolovach, Petr A.
dc.relation.ispartofeditorZehavi, Meirav
dc.relation.ispartofpublnameSchloss Dagstuhl--Leibniz-Zentrum fuer Informatiken
dc.subject.ddclabelInformatique généraleen
dc.relation.ispartofisbn978-3-95977-216-7en
dc.relation.conftitle16th International Symposium on Parameterized and Exact Computation, IPEC 2021en
dc.relation.confdate2021-09
dc.relation.confcityLisbonen
dc.relation.confcountryPortugalen
dc.relation.forthcomingnonen
dc.description.ssrncandidatenon
dc.description.halcandidatenonen
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewednonen
dc.date.updated2022-02-28T09:22:56Z
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut


Files in this item

Thumbnail
Name:
Twin-width_bonnet.pdf
Size:
1.099Mb
Format:
PDF
View/Open

This item appears in the following Collection(s)

Show simple item record