2026-07-23T18:00:21Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22243 2024-12-05T15:32:41Z ddc:004 open_access

Subset Feedback Vertex Set in Tournaments as Fast as Without the Subset Jana, Satyabrata Kanesh, Lawqueen Kundu, Madhumita Saurabh, Saket Parameterized algorithms Feedback vertex set Tournaments Fixed parameter tractable Graph partitions In the Feedback Vertex Set in Tournaments (FVST) problem, we are given a tournament T and a positive integer k. The objective is to determine whether there exists a vertex set X ⊆ V(T) of size at most k such that T-X is a directed acyclic graph. This problem is known to be equivalent to the problem of hitting all directed triangles, thereby using the best-known algorithm for the 3-Hitting Set problem results in an algorithm for FVST with a running time of 2.076^k ⋅ n^{𝒪(1)} [Wahlström, Ph.D. Thesis]. Kumar and Lokshtanov [STACS 2016] designed a more efficient algorithm with a running time of 1.6181^k ⋅ n^{𝒪(1)}. A generalization of FVST, called Subset-FVST, includes an additional subset S ⊆ V(T) in the input. The goal for Subset-FVST is to find a vertex set X ⊆ V(T) of size at most k such that T-X contains no directed cycles that pass through any vertex in S. This generalized problem can also be represented as a 3-Hitting Set problem, leading to a running time of 2.076^k ⋅ n^{𝒪(1)}. Bai and Xiao [Theoretical Computer Science 2023] improved this and obtained an algorithm with running time 2^{k + o(k)} ⋅ n^{𝒪(1)}. In our work, we extend the algorithm of Kumar and Lokshtanov [STACS 2016] to solve Subset-FVST, obtaining an algorithm with a running time {𝒪}(1.6181^k + n^{{𝒪}(1)}), matching the running time for FVST. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Satyabrata Jana and Lawqueen Kanesh and Madhumita Kundu and Saket Saurabh 2024 Is Part Of LIPIcs, Volume 321, 19th International Symposium on Parameterized and Exact Computation (IPEC 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2024.17 urn:nbn:de:0030-drops-222438 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2024.17 eng https://creativecommons.org/licenses/by/4.0/legalcode