Rafael Araujo ; Eurinardo Costa ; Sulamita Klein ; Rudini Sampaio ; Ueverton S. Souza - FPT algorithms to recognize well covered graphs

dmtcs:4905 - Discrete Mathematics & Theoretical Computer Science, April 2, 2019, vol. 21 no. 1, ICGT 2018 - https://doi.org/10.23638/DMTCS-21-1-3
FPT algorithms to recognize well covered graphsArticle

Authors: Rafael Araujo ; Eurinardo Costa ; Sulamita Klein ; Rudini Sampaio ORCID; Ueverton S. Souza

    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).


    Volume: vol. 21 no. 1, ICGT 2018
    Published on: April 2, 2019
    Accepted on: March 25, 2019
    Submitted on: October 22, 2018
    Keywords: Computer Science - Data Structures and Algorithms

    1 Document citing this article

    Consultation statistics

    This page has been seen 714 times.
    This article's PDF has been downloaded 288 times.