Directed flow-augmentation. (English) Zbl 07774390
Leonardi, Stefano (ed.) et al., Proceedings of the 54th annual ACM SIGACT symposium on theory of computing, STOC ’22, Rome, Italy June 20–24, 2022. New York, NY: Association for Computing Machinery (ACM). 938-947 (2022).
MSC:
| 68Qxx | Theory of computing |
References:
| [1] | Jianer Chen, Yang Liu, Songjian Lu, Barry O’Sullivan, and Igor Razgon. 2008. A fixed-parameter algorithm for the directed feedback vertex set problem. J. ACM, 55, 5 (2008), 21:1-21:19. https://doi.org/10.1145/1411509.1411511 10.1145/1411509.1411511 · Zbl 1325.68104 |
| [2] | Rajesh Chitnis, Marek Cygan, MohammadTaghi Hajiaghayi, Marcin Pilipczuk, and Michal Pilipczuk. 2016. Designing FPT Algorithms for Cut Problems Using Randomized Contractions. SIAM J. Comput., 45, 4 (2016), 1171-1229. https://doi.org/10.1137/15M1032077 10.1137/15M1032077 · Zbl 1348.68063 |
| [3] | Rajesh Chitnis, László Egri, and Dániel Marx. 2017. List H-Coloring a Graph by Removing Few Vertices. Algorithmica, 78, 1 (2017), 110-146. https://doi.org/10.1007/s00453-016-0139-6 10.1007/s00453-016-0139-6 · Zbl 1361.05085 |
| [4] | Rajesh Hemant Chitnis, Marek Cygan, Mohammad Taghi Hajiaghayi, and Dániel Marx. 2015. Directed Subset Feedback Vertex Set Is Fixed-Parameter Tractable. ACM Trans. Algorithms, 11, 4 (2015), 28:1-28:28. https://doi.org/10.1145/2700209 10.1145/2700209 · Zbl 1398.68222 |
| [5] | Rajesh Hemant Chitnis, László Egri, and Dániel Marx. 2013. List H-Coloring a Graph by Removing Few Vertices. In Algorithms - ESA 2013 - 21st Annual European Symposium, Sophia Antipolis, France, September 2-4, 2013. Proceedings, Hans L. Bodlaender and Giuseppe F. Italiano (Eds.) (Lecture Notes in Computer Science, Vol. 8125). Springer, 313-324. https://doi.org/10.1007/978-3-642-40450-4_27 10.1007/978-3-642-40450-4_27 · Zbl 1395.68145 |
| [6] | Rajesh Hemant Chitnis, MohammadTaghi Hajiaghayi, and Dániel Marx. 2013. Fixed-Parameter Tractability of Directed Multiway Cut Parameterized by the Size of the Cutset. SIAM J. Comput., 42, 4 (2013), 1674-1696. https://doi.org/10.1137/12086217X 10.1137/12086217X · Zbl 1312.68097 |
| [7] | Marek Cygan, Pawel Komosa, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh, and Magnus Wahlström. 2021. Randomized Contractions Meet Lean Decompositions. ACM Trans. Algorithms, 17, 1 (2021), 6:1-6:30. https://doi.org/10.1145/3426738 10.1145/3426738 · Zbl 07471491 |
| [8] | Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. 2019. Minimum Bisection Is Fixed-Parameter Tractable. SIAM J. Comput., 48, 2 (2019), 417-450. · Zbl 1421.68069 |
| [9] | Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk, and Magnus Wahlström. 2021. Directed flow-augmentation. CoRR, abs/2111.03450 (2021), arXiv:2111.03450. arxiv:2111.03450 |
| [10] | Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk, and Magnus Wahlström. 2021. Solving hard cut problems via flow-augmentation. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021, Dániel Marx (Ed.). SIAM, 149-168. https://doi.org/10.1137/1.9781611976465.11 10.1137/1.9781611976465.11 · Zbl 07788349 |
| [11] | Stefan Kratsch, Shaohua Li, Dániel Marx, Marcin Pilipczuk, and Magnus Wahlström. 2020. Multi-budgeted Directed Cuts. Algorithmica, 82, 8 (2020), 2135-2155. https://doi.org/10.1007/s00453-019-00609-1 10.1007/s00453-019-00609-1 · Zbl 1477.68236 |
| [12] | Stefan Kratsch and Magnus Wahlström. 2020. Representative Sets and Irrelevant Vertices: New Tools for Kernelization. J. ACM, 67, 3 (2020), 16:1-16:50. https://doi.org/10.1145/3390887 10.1145/3390887 · Zbl 1491.68092 |
| [13] | Daniel Lokshtanov, M. S. Ramanujan, and Saket Saurabh. 2018. When Recursion is Better than Iteration: A Linear-Time Algorithm for Acyclicity with Few Error Vertices. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, Artur Czumaj (Ed.). SIAM, 1916-1933. https://doi.org/10.1137/1.9781611975031.125 10.1137/1.9781611975031.125 · Zbl 1403.68170 |
| [14] | Daniel Lokshtanov, M. S. Ramanujan, Saket Saurabh, and Meirav Zehavi. 2020. Parameterized Complexity and Approximability of Directed Odd Cycle Transversal. In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, Shuchi Chawla (Ed.). SIAM, 2181-2200. https://doi.org/10.1137/1.9781611975994.134 10.1137/1.9781611975994.134 · Zbl 07304158 |
| [15] | Dániel Marx. 2004. Parameterized Graph Separation Problems. In Parameterized and Exact Computation, First International Workshop, IWPEC 2004, Bergen, Norway, September 14-17, 2004, Proceedings, Rodney G. Downey, Michael R. Fellows, and Frank K. H. A. Dehne (Eds.) (Lecture Notes in Computer Science, Vol. 3162). Springer, 71-82. https://doi.org/10.1007/978-3-540-28639-4_7 10.1007/978-3-540-28639-4_7 · Zbl 1104.68543 |
| [16] | Dániel Marx. 2006. Parameterized graph separation problems. Theor. Comput. Sci., 351, 3 (2006), 394-406. https://doi.org/10.1016/j.tcs.2005.10.007 10.1016/j.tcs.2005.10.007 · Zbl 1086.68104 |
| [17] | Dániel Marx, Barry O’Sullivan, and Igor Razgon. 2013. Finding small separators in linear time via treewidth reduction. ACM Trans. Algorithms, 9, 4 (2013), 30:1-30:35. https://doi.org/10.1145/2500119 10.1145/2500119 · Zbl 1301.05337 |
| [18] | Dániel Marx and Igor Razgon. 2009. Constant ratio fixed-parameter approximation of the edge multicut problem. Inf. Process. Lett., 109, 20 (2009), 1161-1166. https://doi.org/10.1016/j.ipl.2009.07.016 10.1016/j.ipl.2009.07.016 · Zbl 1197.05149 |
| [19] | Dániel Marx and Igor Razgon. 2014. Fixed-Parameter Tractability of Multicut Parameterized by the Size of the Cutset. SIAM J. Comput., 43, 2 (2014), 355-388. https://doi.org/10.1137/110855247 10.1137/110855247 · Zbl 1304.68078 |
| [20] | Marcin Pilipczuk and Magnus Wahlström. 2018. Directed Multicut is W[1]-hard, Even for Four Terminal Pairs. ACM Trans. Comput. Theory, 10, 3 (2018), 13:1-13:18. https://doi.org/10.1145/3201775 10.1145/3201775 · Zbl 1427.68252 |
| [21] | Igor Razgon and Barry O’Sullivan. 2009. Almost 2-SAT is fixed-parameter tractable. J. Comput. Syst. Sci., 75, 8 (2009), 435-450. https://doi.org/10.1016/j.jcss.2009.04.002 10.1016/j.jcss.2009.04.002 · Zbl 1184.68477 |
| [22] | Saket Saurabh. 2017. What’s next? Future directions in parameterized complexity. https://rapctelaviv.weebly.com/uploads/1/0/5/3/105379375/future.pdf Recent Advances in Parameterized Complexity school, Tel Aviv, December 2017 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
