Dynamic Parameterized Problems and Algorithms
© 2020 ACM. Fixed-parameter algorithms and kernelization are two powerful methods to solve NP-hard problems. Yet so far those algorithms have been largely restricted to static inputs. In this article, we provide fixed-parameter algorithms and kernelizations for fundamental NP-hard problems with dyna...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Association for Computing Machinery (ACM)
2021
|
| Online Access: | https://hdl.handle.net/1721.1/135282 |
| _version_ | 1826213624870338560 |
|---|---|
| author | Alman, Josh Mnich, Matthias Williams, Virginia Vassilevska |
| author_facet | Alman, Josh Mnich, Matthias Williams, Virginia Vassilevska |
| author_sort | Alman, Josh |
| collection | MIT |
| description | © 2020 ACM. Fixed-parameter algorithms and kernelization are two powerful methods to solve NP-hard problems. Yet so far those algorithms have been largely restricted to static inputs. In this article, we provide fixed-parameter algorithms and kernelizations for fundamental NP-hard problems with dynamic inputs. We consider a variety of parameterized graph and hitting set problems that are known to have f(k)n1+o(1) time algorithms on inputs of size n, and we consider the question of whether there is a data structure that supports small updates (such as edge/vertex/set/element insertions and deletions) with an update time of g(k)no(1); such an update time would be essentially optimal. Update and query times independent of n are particularly desirable. Among many other results, we show that FEEDBACK VERTEX SET and k-PATH admit dynamic algorithms with f(k)log O(1) update and query times for some function f depending on the solution size k only. We complement our positive results by several conditional and unconditional lower bounds. For example, we show that unlike their undirected counterparts, DIRECTED FEEDBACK VERTEX SET and DIRECTED k-PATH do not admit dynamic algorithms with no(1) update and query times even for constant solution sizes k ≤ 3, assuming popular hardness hypotheses. We also show that unconditionally, in the cell probe model, DIRECTED FEEDBACK VERTEX SET cannot be solved with update time that is purely a function of k. |
| first_indexed | 2024-09-23T15:52:14Z |
| format | Article |
| id | mit-1721.1/135282 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T15:52:14Z |
| publishDate | 2021 |
| publisher | Association for Computing Machinery (ACM) |
| record_format | dspace |
| spelling | mit-1721.1/1352822021-10-28T03:17:31Z Dynamic Parameterized Problems and Algorithms Alman, Josh Mnich, Matthias Williams, Virginia Vassilevska © 2020 ACM. Fixed-parameter algorithms and kernelization are two powerful methods to solve NP-hard problems. Yet so far those algorithms have been largely restricted to static inputs. In this article, we provide fixed-parameter algorithms and kernelizations for fundamental NP-hard problems with dynamic inputs. We consider a variety of parameterized graph and hitting set problems that are known to have f(k)n1+o(1) time algorithms on inputs of size n, and we consider the question of whether there is a data structure that supports small updates (such as edge/vertex/set/element insertions and deletions) with an update time of g(k)no(1); such an update time would be essentially optimal. Update and query times independent of n are particularly desirable. Among many other results, we show that FEEDBACK VERTEX SET and k-PATH admit dynamic algorithms with f(k)log O(1) update and query times for some function f depending on the solution size k only. We complement our positive results by several conditional and unconditional lower bounds. For example, we show that unlike their undirected counterparts, DIRECTED FEEDBACK VERTEX SET and DIRECTED k-PATH do not admit dynamic algorithms with no(1) update and query times even for constant solution sizes k ≤ 3, assuming popular hardness hypotheses. We also show that unconditionally, in the cell probe model, DIRECTED FEEDBACK VERTEX SET cannot be solved with update time that is purely a function of k. 2021-10-27T20:22:46Z 2021-10-27T20:22:46Z 2020 2021-01-25T17:31:59Z Article http://purl.org/eprint/type/JournalArticle https://hdl.handle.net/1721.1/135282 en 10.1145/3395037 ACM Transactions on Algorithms Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Association for Computing Machinery (ACM) arXiv |
| spellingShingle | Alman, Josh Mnich, Matthias Williams, Virginia Vassilevska Dynamic Parameterized Problems and Algorithms |
| title | Dynamic Parameterized Problems and Algorithms |
| title_full | Dynamic Parameterized Problems and Algorithms |
| title_fullStr | Dynamic Parameterized Problems and Algorithms |
| title_full_unstemmed | Dynamic Parameterized Problems and Algorithms |
| title_short | Dynamic Parameterized Problems and Algorithms |
| title_sort | dynamic parameterized problems and algorithms |
| url | https://hdl.handle.net/1721.1/135282 |
| work_keys_str_mv | AT almanjosh dynamicparameterizedproblemsandalgorithms AT mnichmatthias dynamicparameterizedproblemsandalgorithms AT williamsvirginiavassilevska dynamicparameterizedproblemsandalgorithms |