An Almost Quadratic Vertex Kernel for Subset Feedback Arc Set in Tournaments
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912273761566720 |
|---|---|
| author | Bai, Tian |
| author_facet | Bai, Tian |
| contents | In the Feedback Arc Set in Tournaments (Subset-FAST) problem, we are given a tournament $D$ and a positive integer $k$, and the objective is to determine whether there exists an arc set $S \subseteq A(D)$ of size at most $k$ whose removal makes the graph acyclic. This problem is well-known to be equivalent to a natural tournament ranking problem, whose task is to rank players in a tournament such that the number of pairs in which the lower-ranked player defeats the higher-ranked player is no more than $k$. Using the PTAS for Subset-FAST [STOC 2007], Bessy et al. [JCSS 2011] present a $(2 + \varepsilon)k$-vertex kernel for this problem, given any fixed $\varepsilon > 0$. A generalization of Subset-FAST, called Subset-FAST, further includes an additional terminal subset $T \subseteq V(D)$ in the input. The goal of Subset-FAST is to determine whether there is an arc set $S \subseteq A(D)$ of size at most $k$ whose removal ensures that no directed cycle passes through any terminal in $T$. Prior to our work, no polynomial kernel for Subset-FAST was known. In our work, we show that Subset-FAST admits an $\mathcal{O}((αk)^{2})$-vertex kernel, provided that Subset-FAST has an approximation algorithm with an approximation ratio $α$. Consequently, based on the known $\mathcal{O}(\log k \log \log k)$-approximation algorithm, we obtain an almost quadratic kernel for Subset-FAST. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_10447 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | An Almost Quadratic Vertex Kernel for Subset Feedback Arc Set in Tournaments Bai, Tian Data Structures and Algorithms In the Feedback Arc Set in Tournaments (Subset-FAST) problem, we are given a tournament $D$ and a positive integer $k$, and the objective is to determine whether there exists an arc set $S \subseteq A(D)$ of size at most $k$ whose removal makes the graph acyclic. This problem is well-known to be equivalent to a natural tournament ranking problem, whose task is to rank players in a tournament such that the number of pairs in which the lower-ranked player defeats the higher-ranked player is no more than $k$. Using the PTAS for Subset-FAST [STOC 2007], Bessy et al. [JCSS 2011] present a $(2 + \varepsilon)k$-vertex kernel for this problem, given any fixed $\varepsilon > 0$. A generalization of Subset-FAST, called Subset-FAST, further includes an additional terminal subset $T \subseteq V(D)$ in the input. The goal of Subset-FAST is to determine whether there is an arc set $S \subseteq A(D)$ of size at most $k$ whose removal ensures that no directed cycle passes through any terminal in $T$. Prior to our work, no polynomial kernel for Subset-FAST was known. In our work, we show that Subset-FAST admits an $\mathcal{O}((αk)^{2})$-vertex kernel, provided that Subset-FAST has an approximation algorithm with an approximation ratio $α$. Consequently, based on the known $\mathcal{O}(\log k \log \log k)$-approximation algorithm, we obtain an almost quadratic kernel for Subset-FAST. |
| title | An Almost Quadratic Vertex Kernel for Subset Feedback Arc Set in Tournaments |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2503.10447 |