论文标题
度假：解决比赛问题的新参数
Degreewidth: a New Parameter for Solving Problems on Tournaments
论文作者
论文摘要
在论文中，我们为锦标赛定义了一个名为Legrwidth的新参数，该参数可以看作是衡量比赛距离无环的程度的衡量标准。 $δ（t）$表示的比赛的$ t $的度量是最低值$ k $，我们可以找到$ \ langle v_1，\ dots，\ dots，v_n \ rangle $ $ t $的$ t $ $ t $ $ t $ t $ $ t $的$ t $ c $ k $ k $ back $ s $ \ textiT $ \ textit vextiT（c） $ j <i $）。因此，仅当比赛宽度为零时，比赛是无环的。 此外，Bessy等人定义的稀疏比赛类别。 [ESA 2017]正是Legrwidth One的比赛类别。 我们首先研究查找学位的计算复杂性。也就是说，我们证明这是NP固定的，并使用$ 3 $ APPROXIMATION算法对此结果进行补充。我们还提供了一种立方算法来决定比赛是否稀疏。 最后，我们研究经典的图形问题\ textsc {主导集}和\ textsc {反馈顶点set}通过度假参数化。我们表明前者是固定参数可处理的，而后者在稀疏比赛中是NP-HARD。此外，我们在稀疏比赛中研究\ textsc {反馈弧集}。
In the paper, we define a new parameter for tournaments called degreewidth which can be seen as a measure of how far is the tournament from being acyclic. The degreewidth of a tournament $T$ denoted by $Δ(T)$ is the minimum value $k$ for which we can find an ordering $\langle v_1, \dots, v_n \rangle$ of the vertices of $T$ such that every vertex is incident to at most $k$ backward arcs (\textit{i.e.} an arc $(v_i,v_j)$ such that $j<i$). Thus, a tournament is acyclic if and only if its degreewidth is zero. Additionally, the class of sparse tournaments defined by Bessy et al. [ESA 2017] is exactly the class of tournaments with degreewidth one. We first study computational complexity of finding degreewidth. Namely, we show it is NP-hard and complement this result with a $3$-approximation algorithm. We also provide a cubic algorithm to decide if a tournament is sparse. Finally, we study classical graph problems \textsc{Dominating Set} and \textsc{Feedback Vertex Set} parameterized by degreewidth. We show the former is fixed parameter tractable whereas the latter is NP-hard on sparse tournaments. Additionally, we study \textsc{Feedback Arc Set} on sparse tournaments.
