Geodesic
Parameterized Power Vertex Cover
Discrete mathematics & theoretical computer science, Tome 20 (2018) no. 2.

Voir la notice de l'article provenant de la source Episciences

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 parameterized complexity of Vertex Cover. On the positive side, when parameterized by the value of the optimal P, we give an O*(1.274^P)-time branching algorithm (O* is used to hide factors polynomial in the input size), and also an O*(1.325^P)-time 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.619^k) and O*(k^k)-time 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 n^o(t)-time algorithm for PVC. We give a method to overcome this hardness by designing an FPT approximation scheme which gives a (1+epsilon)-approximation to the optimal solution in time FPT in parameters t and 1/epsilon. 
@article{DMTCS_2018_20_2_a5,
     author = {Angel, Eric and Bampis, Evripidis and Escoffier, Bruno and Lampis, Michael},
     title = {Parameterized {Power} {Vertex} {Cover}},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {20},
     number = {2},
     year = {2018},
     doi = {10.23638/DMTCS-20-2-10},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-20-2-10/}
}
TY  - JOUR
AU  - Angel, Eric
AU  - Bampis, Evripidis
AU  - Escoffier, Bruno
AU  - Lampis, Michael
TI  - Parameterized Power Vertex Cover
JO  - Discrete mathematics & theoretical computer science
PY  - 2018
VL  - 20
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-20-2-10/
DO  - 10.23638/DMTCS-20-2-10
LA  - en
ID  - DMTCS_2018_20_2_a5
ER  - 
%0 Journal Article
%A Angel, Eric
%A Bampis, Evripidis
%A Escoffier, Bruno
%A Lampis, Michael
%T Parameterized Power Vertex Cover
%J Discrete mathematics & theoretical computer science
%D 2018
%V 20
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-20-2-10/
%R 10.23638/DMTCS-20-2-10
%G en
%F DMTCS_2018_20_2_a5
Angel, Eric; Bampis, Evripidis; Escoffier, Bruno; Lampis, Michael. Parameterized Power Vertex Cover. Discrete mathematics & theoretical computer science, Tome 20 (2018) no. 2. doi : 10.23638/DMTCS-20-2-10. http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-20-2-10/

Cité par Sources :