A Quadratic Vertex Kernel and a Subexponential Algorithm for Subset-FAST
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866929751553212416 |
|---|---|
| author | Jana, Satyabrata Kanesh, Lawqueen Kundu, Madhumita Lokshtanov, Daniel Saurabh, Saket |
| author_facet | Jana, Satyabrata Kanesh, Lawqueen Kundu, Madhumita Lokshtanov, Daniel Saurabh, Saket |
| contents | In the Subset Feedback Arc Set in Tournaments, Subset-FAST problem we are given as input a tournament $T$ with a vertex set $V(T)$ and an arc set $A(T)$, along with a terminal set $S \subseteq V(T)$, and an integer $ k$. The objective is to determine whether there exists a set $ F \subseteq A(T) $ with $|F| \leq k$ such that the resulting graph $T-F $ contains no cycle that includes any vertex of $S$. When $S=V(T)$ this is the classic Feedback Arc Set in Tournaments (FAST) problem. We obtain the first polynomial kernel for this problem parameterized by the solution size. More precisely, we obtain an algorithm that, given an input instance $(T, S, k)$, produces an equivalent instance $(T',S',k')$ with $k'\leq k$ and $V(T')=O(k^2)$.
It was known that FAST admits a simple quadratic vertex kernel and a non-trivial linear vertex kernel. However, no such kernel was previously known for Subset-FAST. Our kernel employs variants of the most well-known reduction rules for FAST and introduces two new reduction rules to identify irrelevant vertices. As a result of our kernelization, we also obtain the first sub-exponential time FPT algorithm for Subset-FAST. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_07208 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Quadratic Vertex Kernel and a Subexponential Algorithm for Subset-FAST Jana, Satyabrata Kanesh, Lawqueen Kundu, Madhumita Lokshtanov, Daniel Saurabh, Saket Discrete Mathematics Data Structures and Algorithms Combinatorics In the Subset Feedback Arc Set in Tournaments, Subset-FAST problem we are given as input a tournament $T$ with a vertex set $V(T)$ and an arc set $A(T)$, along with a terminal set $S \subseteq V(T)$, and an integer $ k$. The objective is to determine whether there exists a set $ F \subseteq A(T) $ with $|F| \leq k$ such that the resulting graph $T-F $ contains no cycle that includes any vertex of $S$. When $S=V(T)$ this is the classic Feedback Arc Set in Tournaments (FAST) problem. We obtain the first polynomial kernel for this problem parameterized by the solution size. More precisely, we obtain an algorithm that, given an input instance $(T, S, k)$, produces an equivalent instance $(T',S',k')$ with $k'\leq k$ and $V(T')=O(k^2)$. It was known that FAST admits a simple quadratic vertex kernel and a non-trivial linear vertex kernel. However, no such kernel was previously known for Subset-FAST. Our kernel employs variants of the most well-known reduction rules for FAST and introduces two new reduction rules to identify irrelevant vertices. As a result of our kernelization, we also obtain the first sub-exponential time FPT algorithm for Subset-FAST. |
| title | A Quadratic Vertex Kernel and a Subexponential Algorithm for Subset-FAST |
| topic | Discrete Mathematics Data Structures and Algorithms Combinatorics |
| url | https://arxiv.org/abs/2503.07208 |