A Quadratic Vertex Kernel and a Subexponential Algorithm for Subset-FAST
Satyabrata Jana, Lawqueen Kanesh, Madhumita Kundu, Daniel Lokshtanov, Saket Saurabh · 2025
Read A Quadratic Vertex Kernel and a Subexponential Algorithm for Subset-FAST by Satyabrata Jana, Lawqueen Kanesh, Madhumita Kundu, Daniel Lokshtanov, Saket Saurabh (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-07208.txt.
Description
Satyabrata Jana and co-authors shrink a hard graph problem to a small core and give a faster method in 2025. The problem asks if a set of arcs can be cut from a tournament graph so no cycle passes a marked set. With all points marked, it is a classic problem. Their method cuts the input to an equal case whose size grows with the square of the answer bound.
No such shrink was known for the subset form before. Known cut rules were adapted, and two new rules find points that can be dropped. The shrink yields the first fast fixed parameter method that runs in sub exponential time. The result closes a gap between the classic and subset forms.
Catalog record
| CREATOR | Satyabrata Jana, Lawqueen Kanesh, Madhumita Kundu, Daniel Lokshtanov, Saket Saurabh |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 100 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-07208