DROPS

Document

DOI: 10.4230/LIPIcs.IPEC.2024.22

Dynamic Parameterized Feedback Problems in Tournaments

Authors: Anna Zych-Pawlewicz and Marek Żochowski

Published in: LIPIcs, Volume 321, 19th International Symposium on Parameterized and Exact Computation (IPEC 2024)

Abstract

In this paper we present the first dynamic algorithms for the problem of K-Feedback Arc Set in Tournaments (K-Fast) and the problem of K-Feedback Vertex Set in Tournaments (K-Fvst). Our algorithms maintain a dynamic tournament on n vertices altered by redirecting the arcs, and answer if the tournament admits a feedback arc set (or respectively feedback vertex set) of size at most K, for some chosen parameter K. For dynamic K-Fast we offer two algorithms. In the promise model, where we are guaranteed, that the size of the solution does not exceed g(K) for some computable function g, we give an O(√g(K)) update and O(3^K K √K) query algorithm. In the general setting without any promise, we offer an O(log² n) update and O(3^K K log² n) query time algorithm for dynamic K-Fast. For dynamic K-Fvst we offer an algorithm working in the promise model, which admits O(g⁵(K)) update and O(3^K K³ g(K)) query time.

Cite as

Anna Zych-Pawlewicz and Marek Żochowski. Dynamic Parameterized Feedback Problems in Tournaments. In 19th International Symposium on Parameterized and Exact Computation (IPEC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 321, pp. 22:1-22:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{zychpawlewicz_et_al:LIPIcs.IPEC.2024.22,
  author =	{Zych-Pawlewicz, Anna and \.{Z}ochowski, Marek},
  title =	{{Dynamic Parameterized Feedback Problems in Tournaments}},
  booktitle =	{19th International Symposium on Parameterized and Exact Computation (IPEC 2024)},
  pages =	{22:1--22:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-353-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{321},
  editor =	{Bonnet, \'{E}douard and Rz\k{a}\.{z}ewski, Pawe{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2024.22},
  URN =		{urn:nbn:de:0030-drops-222482},
  doi =		{10.4230/LIPIcs.IPEC.2024.22},
  annote =	{Keywords: dynamic algorithms, parameterized algorithms, feedback arc set, feedback vertex set, tournaments}
}

Search Results

Documents authored by Żochowski, Marek

Dynamic Parameterized Feedback Problems in Tournaments

Abstract

Cite as

Thanks for your feedback!

Could not send message