Algoritmos FPT para reconhecer grafos bem cobertos
Resumo
Dado um grafo G, sejam vc(G) e vc+(G) os tamanhos de uma cobertura mínima de vértices e de uma máxima cobertura minimal de vértices, respectivamente. Dizemos que G é bem coberto se vc(G) = vc+(G) (ou seja, todas as coberturas minimais são mínimas). É coNP-completo decidir se um grafo é bem coberto. Nesse artigo, obtemos algoritmos FPT de tempos O∗(2vc) e O∗(1.4656vc+) para decidir se um grafo é bem coberto, parametrizados por vc(G) e vc+(G), respectivamente, melhorando resultados de Boria et al. em 2015. Também obtemos algoritmo FPT parametrizado por α(G) = n - vc(G) em grafos d-degenerados, que inclui grafos com genus limitado (como grafos planares) e grafos com grau máximo limitado. Finalmente usamos a decomposição primeval para obter algoritmo linear para grafos P4-laden estendidos e grafos (q, q 4), que é FPT parametrizado por q, melhorando resultados de Klein et al. em 2013.
Referências
Bodlaender, H. L. (1998). A partial k-arboretum of graphs with bounded treewidth. Theoretical Computer Science, 209(1):1 – 45.
Boria, N., Croce, F. D., and Paschos, V. T. (2015). On the max min vertex cover problem. Discrete Applied Mathematics, 196:62 – 71.
Caro, Y., Sebő, A., and Tarsi, M. (1996). Recognizing greedy structures. Journal of Algorithms, 20(1):137 – 156.
Eppstein, D. (2000). Diameter and treewidth in minor-closed graph families. Algorithmica, 27:275–291.
Flum, J. and Grohe, M. (2006). Parameterized Complexity Theory (Texts in Theoretical Computer Science. An EATCS Series). Springer-Verlag New York, Inc.
Giakoumakis, V. (1996). P4-laden graphs: A new class of brittle graphs. Information Processing Letters, 60(1):29 – 36.
Klein, S., de Mello, C. P., and Morgana, A. (2013). Recognizing well covered graphs of families with special p4-components. Graphs and Combinatorics, 29:553–567.
Plummer, M. D. (1970). Some covering concepts in graphs. Journal of Combinatorial Theory, 8(1):91 – 98.
