• norsk
    • English
  • norsk 
    • norsk
    • English
  • Logg inn
Vis innførsel 
  •   Hjem
  • Faculty of Mathematics and Natural Sciences
  • Department of Informatics
  • Department of Informatics
  • Vis innførsel
  •   Hjem
  • Faculty of Mathematics and Natural Sciences
  • Department of Informatics
  • Department of Informatics
  • Vis innførsel
JavaScript is disabled for your browser. Some features of this site may not work without it.

Subquadratic Kernels for Implicit 3-Hitting Set and 3-Set Packing Problems

Fomin, Fedor; Le, Tien-Nam; Lokshtanov, Daniel; Saurabh, Saket; Thomasse, Stephan; Zehavi, Meirav
Peer reviewed, Journal article
Accepted version
Thumbnail
Åpne
Accepted version (708.4Kb)
Permanent lenke
https://hdl.handle.net/1956/22048
Utgivelsesdato
2019
Metadata
Vis full innførsel
Samlinger
  • Department of Informatics [740]
Originalversjon
https://doi.org/10.1145/3293466
Sammendrag
We consider four well-studied NP-complete packing/covering problems on graphs: Feedback Vertex Set in Tournaments (FVST), Cluster Vertex Deletion (CVD), Triangle Packing in Tournaments (TPT) and Induced P3-Packing. For these four problems, kernels with O(k2) vertices have been known for a long time. In fact, such kernels can be obtained by interpreting these problems as finding either a packing of k pairwise disjoint sets of size 3 (3-Set Packing) or a hitting set of size at most k for a family of sets of size at most 3 (3-Hitting Set). In this article, we give the first kernels for FVST, CVD, TPT, and Induced P3-Packing with a subquadratic number of vertices. Specifically, we obtain the following results. • FVST admits a kernel with O(k3/2) vertices. • CVD admits a kernel with O(k5/3) vertices. • TPT admits a kernel with O(k3/2) vertices. • Induced P3-Packing admits a kernel with O(k5/3) vertices. Our results resolve an open problem from WorKer 2010 on the existence of kernels with O(k2−ϵ) vertices for FVST and CVD. All of our results are based on novel uses of old and new “expansion lemmas” and a weak form of crown decomposition where (i) almost all of the head is used by the solution (as opposed to all), (ii) almost none of the crown is used by the solution (as opposed to none), and (iii) if H is removed from G, then there is almost no interaction between the head and the rest (as opposed to no interaction at all).
Utgiver
ACM
Tidsskrift
ACM Transactions on Algorithms (TALG)
Opphavsrett
Copyright 2019 Association for Computing Machinery

Kontakt oss | Gi tilbakemelding

Personvernerklæring
DSpace software copyright © 2002-2019  DuraSpace

Levert av  Unit
 

 

Bla i

Hele arkivetDelarkiv og samlingerUtgivelsesdatoForfattereTitlerEmneordDokumenttyperTidsskrifterDenne samlingenUtgivelsesdatoForfattereTitlerEmneordDokumenttyperTidsskrifter

Min side

Logg inn

Statistikk

Besøksstatistikk

Kontakt oss | Gi tilbakemelding

Personvernerklæring
DSpace software copyright © 2002-2019  DuraSpace

Levert av  Unit