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

CREATORSatyabrata Jana, Lawqueen Kanesh, Madhumita Kundu, Daniel Lokshtanov, Saket Saurabh
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE100 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-07208

Browse the full library · About the Tower of Babel