dc.contributor.author Angel, Eric dc.contributor.author Bampis, Evripidis dc.contributor.author Escoffier, Bruno dc.contributor.author Lampis, Michail dc.date.accessioned 2017-03-14T13:57:38Z dc.date.available 2017-03-14T13:57:38Z dc.date.issued 2016 dc.identifier.uri https://basepub.dauphine.fr/handle/123456789/16339 dc.description Lecture Notes in Computer Science, Vol. 9941 en dc.language.iso en en dc.subject Parameterized complexity en dc.subject.ddc 003 en dc.title Parameterized Power Vertex Cover en dc.type Communication / Conférence dc.description.abstracten We 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.citationpages 97-108 en dc.relation.ispartoftitle Graph-Theoretic Concepts in Computer Science en dc.relation.ispartofeditor Heggernes, Pinar dc.relation.ispartofpublname Springer Berlin Heidelberg en dc.relation.ispartofpublcity Berlin en dc.relation.ispartofdate 2016-09 dc.relation.ispartofpages 307 en dc.relation.ispartofurl 10.1007/978-3-662-53536-3 en dc.subject.ddclabel Recherche opérationnelle en dc.relation.ispartofisbn 978-3-662-53535-6 en dc.relation.conftitle 42nd International Workshop, WG 2016 en dc.relation.confdate 2016-06 dc.relation.confcity Istanbul en dc.relation.confcountry Turkey en dc.relation.forthcoming non en dc.identifier.doi 10.1007/978-3-662-53536-3_9 en dc.description.ssrncandidate non en dc.description.halcandidate oui en dc.description.readership recherche en dc.description.audience International en dc.relation.Isversionofjnlpeerreviewed non en dc.relation.Isversionofjnlpeerreviewed non en dc.date.updated 2017-03-14T13:49:19Z hal.person.labIds 3344 hal.person.labIds 233 hal.person.labIds 233 hal.person.labIds 989 hal.identifier hal-01489609 *
﻿

## Files in this item

FilesSizeFormatView

There are no files associated with this item.