• norsk
    • English
  • norsk 
    • norsk
    • English
  • Logg inn
Vis innførsel 
  •   Hjem
  • University of Bergen Library
  • Registrations from Cristin
  • Vis innførsel
  •   Hjem
  • University of Bergen Library
  • Registrations from Cristin
  • Vis innførsel
JavaScript is disabled for your browser. Some features of this site may not work without it.

Rank vertex cover as a natural problem for algebraic compression

Meesum, Syed Mohammad; Panolan, Fahad; Saurabh, Saket; Zehavi, Meirav
Journal article, Peer reviewed
Published version
Thumbnail
Åpne
PDF (276.4Kb)
Permanent lenke
https://hdl.handle.net/11250/2722590
Utgivelsesdato
2019
Metadata
Vis full innførsel
Samlinger
  • Department of Informatics [738]
  • Registrations from Cristin [5233]
Originalversjon
10.1137/17M1154370
Sammendrag
The question of the existence of a polynomial kernelization of the Vertex Cover Above LP problem was a long-standing, notorious open problem in parameterized complexity. Some years ago, the breakthrough work by Kratsch and Wahlström on representative sets finally answered this question in the affirmative [FOCS 2012]. In this paper, we present an alternative, algebraic compression of the Vertex Cover Above LP problem into the Rank Vertex Cover problem. Here, the input consists of a graph $G$, a parameter $k$, and a bijection between $V(G)$ and the set of columns of a representation of a matroid $M$, and the objective is to find a vertex cover whose rank is upper bounded by $k$.
Utgiver
SIAM
Tidsskrift
SIAM Journal on Discrete Mathematics
Opphavsrett
Copyright 2019 Society for Industrial and Applied Mathematics

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