2024/02/16 by P Aboulker, Pierre Aboulker, Aboulker, Pierre +4
Computer Science · #Artificial Intelligence in Games #AI-based Problem Solving and Planning
paper · pdf · doi:10.46298/dmtcs.14281
Given a class of (undirected) graphs C, we say that a Feedback Arc Set (FAS for short) F is a C-FAS if the graph induced by the edges of F (forgetting their orientations) belongs to C. We show that deciding if a tournament has a C-FAS is NP-complete when C is the class of all forests. We are motivated by connections between C-FAS and structural parameters of tournaments, such as the dichromatic number, the clique number of tournaments, and the strong Erdős-Hajnal property.