Parameterized algorithms for generalizations of Directed Feedback Vertex Set

Göke, 2019, Parameterized algorithms for generalizations of directed feedback vertex set, vol. 11458, 249 Karp, 1972, Reducibility among combinatorial problems, 85 Seymour, 1995, Packing directed circuits fractionally, Combinatorica, 15, 281, 10.1007/BF01200760 Even, 1998, Approximating minimum feedback sets and multicuts in directed graphs, Algorithmica, 20, 151, 10.1007/PL00009191 Even, 2000, Divide-and-conquer approximation algorithms via spreading metrics, J. ACM, 47, 585, 10.1145/347476.347478 Guruswami, 2011, Beating the random ordering is hard: every ordering CSP is approximation resistant, SIAM J. Comput., 40, 878, 10.1137/090756144 Guruswami, 2016, Simple proof of hardness of feedback vertex set, Theory Comput., 12, 10.4086/toc.2016.v012a006 Svensson, 2013, Hardness of vertex deletion and project scheduling, Theory Comput., 9, 759, 10.4086/toc.2013.v009a024 D. Lokshtanov, M.S. Ramanujan, S. Saurabh, When recursion is better than iteration: A linear-time algorithm for acyclicity with few error vertices, in: Proc. SODA 2018, 2018, pp. 1916–1933. Chitnis, 2015, Directed subset feedback vertex set is fixed-parameter tractable, ACM Trans. Algorithms, 11, 10.1145/2700209 D. Lokshtanov, M. Ramanujan, S. Saurabh, Parameterized Complexity and Approximability of Directed Odd Cycle Transversal, in: Proc. SODA 2020, 2020, pp. 2181–2200. Göke, 2020, Hitting long directed cycles is fixed-parameter tractable, vol. 168, 59:1 Cechlárová, 2010, Computing the deficiency of housing markets with duplicate houses, vol. 6478, 72 Marx, 2012, What’s next? Future directions in parameterized complexity, vol. 7370, 469 Kumar, 2017, A 2ℓk Kernel for ℓ-component order connectivity, vol. 63, 20:1 Xiao, 2017, Linear kernels for separating a graph into components of bounded size, J. Comput. System Sci., 88, 260, 10.1016/j.jcss.2017.04.004 Chen, 2008, A fixed-parameter algorithm for the directed feedback vertex set problem, J. ACM, 55, 10.1145/1411509.1411511 Fortune, 1980, The directed subgraph homeomorphism problem, Theoret. Comput. Sci., 10, 111, 10.1016/0304-3975(80)90009-2 Bang-Jensen, 2016, DAG-width and circumference of digraphs, J. Graph Theory, 82, 194, 10.1002/jgt.21894 Chitnis, 2013, Fixed-parameter tractability of directed multiway cut parameterized by the size of the cutset, SIAM J. Comput., 42, 1674, 10.1137/12086217X Cygan, 2014, Parameterized complexity of Eulerian deletion problems, Algorithmica, 68, 41, 10.1007/s00453-012-9667-x Bang-Jensen, 2020, Component order connectivity in directed graphs, vol. 180, 2:1 Drange, 2016, On the computational complexity of vertex integrity and component order connectivity, Algorithmica, 76, 1181, 10.1007/s00453-016-0127-x Neogi, 2020, On the parameterized complexity of deletion to H-free strong components, vol. 170, 75:1