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

• Leonardo C. de Abreu UFC http://orcid.org/0000-0003-0701-0853
• Manoel Campêlo UFC https://orcid.org/0000-0003-2962-2033
• Ana Karolinna Maia UFC https://orcid.org/0000-0002-9027-7948

DOI: https://doi.org/10.5753/etc.2021.16373

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.