Feedback arc set problem under forcing constraints is 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

Abstract

The feedback arc set problem (FAS) consists in finding a minimum size subset of arcs which contains at least one arc of every directed circuit of a directed graph. We study the FAS problem subject to forcing constraints. These constraints state that at least one element of certain pairs of arcs must be included in any feasible solution. It is known that the feedback arc set problem is FPT. We show that the version with forcing constraints is also FPT when parameterized by the size of the solution.

Keywords: Feedback arc set, Fixed parameter tractability, Disjunctive constraints

References

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.