Directed Feedback Vertex Set is Fixed-Parameter Tractable

2022/01/26 by Razgon, Igor, O'Sullivan, Barry
#Directed Acyclic Graph (DAG) #Directed FVS #Multicut

paper · doi:10.4230/dagsemproc.07281.4

Abstract

We resolve positively a long standing open question regarding the fixed-parameter tractability of the parameterized Directed Feedback Vertex Set problem. In particular, we propose an algorithm which solves this problem in O(8^kk!*poly(n)).

Related

• Directed Feedback Vertex Set is Fixed-Parameter Tractable
• A Simplified Parameterized Algorithm for Directed Feedback Vertex Set
• Directed Feedback Vertex Set Problem is FPT
• Parameterized Algorithms for Generalizations of Directed Feedback Vertex Set
• Directed Subset Feedback Vertex Set is Fixed-Parameter Tractable