加载中…
Given a class of (undirected) graphs , we say that a Feedback Arc Set (FAS for short) is a -FAS if the graph induced by the edges of (forgetting their orientations) belongs to . We show that deciding if a tournament has a -FAS is NP-complete when is the class of all forests. We are motivated by connections between -FAS and structural parameters of tournaments, such as the dichromatic number, the clique number of tournaments, and the strong Erdős-Hajnal property.

生成讲解博客的中文版本

生成AI智能校验的中文版本