Show simple item record

dc.contributor.authorAngel, Eric
dc.contributor.authorBampis, Evripidis
dc.contributor.authorEscoffier, Bruno
dc.contributor.authorLampis, Michail
dc.date.accessioned2017-03-14T13:57:38Z
dc.date.available2017-03-14T13:57:38Z
dc.date.issued2016
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/16339
dc.descriptionLecture Notes in Computer Science, Vol. 9941en
dc.language.isoenen
dc.subjectParameterized complexityen
dc.subject.ddc003en
dc.titleParameterized Power Vertex Coveren
dc.typeCommunication / Conférence
dc.description.abstractenWe study a recently introduced generalization of the Vertex Cover(VC) problem, called Power Vertex Cover(PVC). In this problem, each edge of the input graph is supplied with a positive integer demand. A solution is an assignment of (power) values to the vertices, so that for each edge one of its endpoints has value as high as the demand, and the total sum of power values assigned is minimized.We investigate how this generalization affects the complexity of Vertex Cover from the point of view of parameterized algorithms. On the positive side, when parameterized by the value of the optimal P, we give an O∗(1.274P)branching algorithm (O∗ is used to hide factors polynomial in the input size), and also an O∗(1.325P) algorithm for the more general asymmetric case of the problem, where the demand of each edge may differ for its two endpoints. When the parameter is the number of vertices k that receive positive value, we give O∗(1.619k) and O∗(kk) algorithms for the symmetric and asymmetric cases respectively, as well as a simple quadratic kernel for the asymmetric case.We also show that PVC becomes significantly harder than classical VC when parameterized by the graph’s treewidth t. More specifically, we prove that unless the ETH is false, there is no no(t)algorithm for PVC. We give a method to overcome this hardness by designing an FPT approximation scheme which obtains a (1+ϵ)-approximation to the optimal solution in time FPT in parameters t and 1/ϵ.en
dc.identifier.citationpages97-108en
dc.relation.ispartoftitleGraph-Theoretic Concepts in Computer Scienceen
dc.relation.ispartofeditorHeggernes, Pinar
dc.relation.ispartofpublnameSpringer Berlin Heidelbergen
dc.relation.ispartofpublcityBerlinen
dc.relation.ispartofdate2016-09
dc.relation.ispartofpages307en
dc.relation.ispartofurl10.1007/978-3-662-53536-3en
dc.subject.ddclabelRecherche opérationnelleen
dc.relation.ispartofisbn978-3-662-53535-6en
dc.relation.conftitle42nd International Workshop, WG 2016en
dc.relation.confdate2016-06
dc.relation.confcityIstanbulen
dc.relation.confcountryTurkeyen
dc.relation.forthcomingnonen
dc.identifier.doi10.1007/978-3-662-53536-3_9en
dc.description.ssrncandidatenonen
dc.description.halcandidateouien
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewednonen
dc.relation.Isversionofjnlpeerreviewednonen
dc.date.updated2017-03-14T13:49:19Z
hal.person.labIds3344
hal.person.labIds233
hal.person.labIds233
hal.person.labIds989
hal.identifierhal-01489609*


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record