Conjunto de arcos de realimentação sob restrições de forçamento é FPT

Resumo


O problema do conjunto de arcos de realimentação (FAS) consiste em encontrar um subconjunto de arcos de tamanho mínimo que contenha ao menos um elemento de cada circuito direcionado de um grafo direcionado. Estudamos o problema FAS sujeito a restrições de forçamento, as quais determinam que ao menos um elemento de certos pares de arcos deve estar presente em uma solução viável. Sabe-se que o problema de arcos de realimentação é FPT. Mostramos que o problema com restrições de forçamento também é FPT quando parametrizado pelo tamanho da solução.
Palavras-chave: Conjunto de arcos de realimentação, Tratabilidade por parâmetro fixo, Restrições disjuntivas

Referências

Chen, J., Liu, Y., Lu, S., O’Sullivan, B., and Razgon, I. (2008). A fixed-parameter algorithm for the directed feedback vertex set problem. J. ACM, 55.

Darmann, A., Pferschy, U., Schauer, J., and Woeginger, G. J. (2011). Paths, trees and matchings under disjunctive constraints. Discrete Applied Mathematics, 159(16):1726–1735. CTW 2009.

Downey, R. and Fellows, M. (1992). Fixed parameter tractability and completeness. In Congressus Numerantium, volume 87, pages 191–225.

Even, G., Naor, J., and Schieber, B. (1998). Approximating minimum feedback sets and multicuts in directed graphs. Algorithmica, 20:151–174.

Karp, R. (1972). Reducibility among combinatorial problems. In Complexity of Computer Computations, volume 40, pages 85–103.

Mapa, S. M. S. and Urrutia, S. (2015). On the maximum acyclic subgraph problem under disjunctive constraints. Information Processing Letters, 115(2):119–124.

Mehlhorn, K. (1984). Data structures and algorithms 2. In Brauer, W., Rozenberg, G.,and Salomaa, A., editors, Graph Algorithms and NP-Completeness, Berlin. Springer.

Raman, V. and Saurabh, S. (2008). Short cycles make W-Hard problems hard: FPT algorithms for W-Hard problems in graphs with no short cycles. Algorithmica, 52(2):203–225.
Publicado
18/07/2021
ABREU, Leonardo C. de; CAMPÊLO, Manoel; MAIA, Ana Karolinna. Conjunto de arcos de realimentação sob restrições de forçamento é FPT. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 6. , 2021, Evento Online. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2021 . p. 30-33. ISSN 2595-6116. DOI: https://doi.org/10.5753/etc.2021.16373.