FPT algorithms to recognize well covered graphs
Discrete mathematics & theoretical computer science, ICGT 2018, Tome 21 (2019) no. 1
Voir la notice de l'article provenant de la source Episciences
Given a graph $G$, let $vc(G)$ and $vc^+(G)$ be the sizes of a minimum and a maximum minimal vertex covers of $G$, respectively. We say that $G$ is well covered if $vc(G)=vc^+(G)$ (that is, all minimal vertex covers have the same size). Determining if a graph is well covered is a coNP-complete problem. In this paper, we obtain $O^*(2^{vc})$-time and $O^*(1.4656^{vc^+})$-time algorithms to decide well coveredness, improving results of Boria et. al. (2015). Moreover, using crown decomposition, we show that such problems admit kernels having linear number of vertices. In 2018, Alves et. al. (2018) proved that recognizing well covered graphs is coW[2]-hard when the independence number $\alpha(G)=n-vc(G)$ is the parameter. Contrasting with such coW[2]-hardness, we present an FPT algorithm to decide well coveredness when $\alpha(G)$ and the degeneracy of the input graph $G$ are aggregate parameters. Finally, we use the primeval decomposition technique to obtain a linear time algorithm for extended $P_4$-laden graphs and $(q,q-4)$-graphs, which is FPT parameterized by $q$, improving results of Klein et al (2013).
@article{DMTCS_2019_21_1_a2,
author = {Araujo, Rafael and Costa, Eurinardo and Klein, Sulamita and Sampaio, Rudini and Souza, Ueverton S.},
title = {FPT algorithms to recognize well covered graphs},
journal = {Discrete mathematics & theoretical computer science},
publisher = {mathdoc},
volume = {21},
number = {1},
year = {2019},
doi = {10.23638/DMTCS-21-1-3},
language = {en},
url = {http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-21-1-3/}
}
TY - JOUR AU - Araujo, Rafael AU - Costa, Eurinardo AU - Klein, Sulamita AU - Sampaio, Rudini AU - Souza, Ueverton S. TI - FPT algorithms to recognize well covered graphs JO - Discrete mathematics & theoretical computer science PY - 2019 VL - 21 IS - 1 PB - mathdoc UR - http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-21-1-3/ DO - 10.23638/DMTCS-21-1-3 LA - en ID - DMTCS_2019_21_1_a2 ER -
%0 Journal Article %A Araujo, Rafael %A Costa, Eurinardo %A Klein, Sulamita %A Sampaio, Rudini %A Souza, Ueverton S. %T FPT algorithms to recognize well covered graphs %J Discrete mathematics & theoretical computer science %D 2019 %V 21 %N 1 %I mathdoc %U http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-21-1-3/ %R 10.23638/DMTCS-21-1-3 %G en %F DMTCS_2019_21_1_a2
Araujo, Rafael; Costa, Eurinardo; Klein, Sulamita; Sampaio, Rudini; Souza, Ueverton S. FPT algorithms to recognize well covered graphs. Discrete mathematics & theoretical computer science, ICGT 2018, Tome 21 (2019) no. 1. doi: 10.23638/DMTCS-21-1-3
Cité par Sources :