{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T16:02:18Z","timestamp":1725897738066},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642315930"},{"type":"electronic","value":"9783642315947"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-31594-7_20","type":"book-chapter","created":{"date-parts":[[2012,6,22]],"date-time":"2012-06-22T21:20:21Z","timestamp":1340400021000},"page":"230-241","source":"Crossref","is-referenced-by-count":7,"title":["Directed Subset Feedback Vertex Set Is Fixed-Parameter Tractable"],"prefix":"10.1007","author":[{"given":"Rajesh","family":"Chitnis","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marek","family":"Cygan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mohammadtaghi","family":"Hajiaghayi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"D\u00e1niel","family":"Marx","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"3","key":"20_CR1","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1137\/S0895480196305124","volume":"12","author":"V. Bafna","year":"1999","unstructured":"Bafna, V., Berman, P., Fujito, T.: A 2-approximation algorithm for the undirected feedback vertex set problem. SIAM J. Discrete Math.\u00a012(3), 289\u2013297 (1999)","journal-title":"SIAM J. Discrete Math."},{"key":"20_CR2","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1613\/jair.638","volume":"12","author":"A. Becker","year":"2000","unstructured":"Becker, A., Bar-Yehuda, R., Geiger, D.: Randomized algorithms for the loop cutset problem. J. Artif. Intell. Res. (JAIR)\u00a012, 219\u2013234 (2000)","journal-title":"J. Artif. Intell. Res. (JAIR)"},{"doi-asserted-by":"crossref","unstructured":"Bodlaender, H.L.: On disjoint cycles. In: WG, pp. 230\u2013238 (1991)","key":"20_CR3","DOI":"10.1007\/3-540-55121-2_24"},{"key":"20_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1007\/978-3-642-22300-6_11","volume-title":"Algorithms and Data Structures","author":"P. Bonsma","year":"2011","unstructured":"Bonsma, P., Lokshtanov, D.: Feedback Vertex Set in Mixed Graphs. In: Dehne, F., Iacono, J., Sack, J.-R. (eds.) WADS 2011. LNCS, vol.\u00a06844, pp. 122\u2013133. Springer, Heidelberg (2011)"},{"key":"20_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1007\/978-3-642-13731-0_10","volume-title":"Algorithm Theory - SWAT 2010","author":"Y. Cao","year":"2010","unstructured":"Cao, Y., Chen, J., Liu, Y.: On Feedback Vertex Set New Measure and New Structures. In: Kaplan, H. (ed.) SWAT 2010. LNCS, vol.\u00a06139, pp. 93\u2013104. Springer, Heidelberg (2010)"},{"issue":"7","key":"20_CR6","doi-asserted-by":"publisher","first-page":"1188","DOI":"10.1016\/j.jcss.2008.05.002","volume":"74","author":"J. Chen","year":"2008","unstructured":"Chen, J., Fomin, F.V., Liu, Y., Lu, S., Villanger, Y.: Improved algorithms for feedback vertex set problems. J. Comput. Syst. Sci.\u00a074(7), 1188\u20131198 (2008)","journal-title":"J. Comput. Syst. Sci."},{"doi-asserted-by":"crossref","unstructured":"Chen, J., Liu, Y., Lu, S., O\u2019Sullivan, B., Razgon, I.: A fixed-parameter algorithm for the directed feedback vertex set problem. In: STOC 2008, pp. 177\u2013186 (2008)","key":"20_CR7","DOI":"10.1145\/1374376.1374404"},{"doi-asserted-by":"crossref","unstructured":"Chitnis, R.H., Hajiaghayi, M., Marx, D.: Fixed-parameter tractability of directed multiway cut parameterized by the size of the cutset. In: SODA 2012, pp. 1713\u20131725 (2012)","key":"20_CR8","DOI":"10.1137\/1.9781611973099.136"},{"doi-asserted-by":"crossref","unstructured":"Cygan, M., Kratsch, S., Pilipczuk, M., Pilipczuk, M., Wahlstr\u00f6m, M.: Clique cover and graph separation: New incompressibility results. CoRR abs\/1111.0570 (2011)","key":"20_CR9","DOI":"10.1007\/978-3-642-31594-7_22"},{"doi-asserted-by":"crossref","unstructured":"Cygan, M., Nederlof, J., Pilipczuk, M., Pilipczuk, M., van Rooij, J.M.M., Wojtaszczyk, J.O.: Solving connectivity problems parameterized by treewidth in single exponential time. In: FOCS 2011, pp. 150\u2013159 (2011)","key":"20_CR10","DOI":"10.1109\/FOCS.2011.23"},{"key":"20_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"449","DOI":"10.1007\/978-3-642-22006-7_38","volume-title":"Automata, Languages and Programming","author":"M. Cygan","year":"2011","unstructured":"Cygan, M., Pilipczuk, M., Pilipczuk, M., Wojtaszczyk, J.O.: Subset Feedback Vertex Set is Fixed-Parameter Tractable. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) ICALP 2011. LNCS, vol.\u00a06755, pp. 449\u2013461. Springer, Heidelberg (2011)"},{"doi-asserted-by":"crossref","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity, 530 p. Springer (1999)","key":"20_CR12","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"20_CR13","series-title":"LNCS","first-page":"14","volume-title":"IPCO 1995","author":"G. Even","year":"1995","unstructured":"Even, G., Naor, J., Schieber, B., Sudan, M.: Approximating Minimum Feedback Sets and Multi-Cuts in Directed Graphs (Extended Summary). In: IPCO 1995. LNCS, vol.\u00a0920, pp. 14\u201328. Springer, Heidelberg (1995)"},{"issue":"4","key":"20_CR14","doi-asserted-by":"publisher","first-page":"1231","DOI":"10.1137\/S0097539798340047","volume":"30","author":"G. Even","year":"2000","unstructured":"Even, G., Naor, J., Zosin, L.: An 8-approximation algorithm for the subset feedback vertex set problem. SIAM J. Comput.\u00a030(4), 1231\u20131252 (2000)","journal-title":"SIAM J. Comput."},{"unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory, 493 p. Springer (2006)","key":"20_CR15"},{"doi-asserted-by":"crossref","unstructured":"Kakimura, N., Kawarabayashi, K., Kobayashi, Y.: Erd\u00f6s-p\u00f3sa property and its algorithmic applications: parity constraints, subset feedback set, and subset packing. In: SODA 2012, pp. 1726\u20131736 (2012)","key":"20_CR16","DOI":"10.1137\/1.9781611973099.137"},{"key":"20_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1007\/978-3-540-28639-4_21","volume-title":"Parameterized and Exact Computation","author":"I.A. Kanj","year":"2004","unstructured":"Kanj, I.A., Pelsmajer, M.J., Schaefer, M.: Parameterized Algorithms for Feedback Vertex Set. In: Downey, R.G., Fellows, M.R., Dehne, F. (eds.) IWPEC 2004. LNCS, vol.\u00a03162, pp. 235\u2013247. Springer, Heidelberg (2004)"},{"doi-asserted-by":"crossref","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Complexity of Computer Computations, pp. 85\u2013103 (1972)","key":"20_CR18","DOI":"10.1007\/978-1-4684-2001-2_9"},{"doi-asserted-by":"crossref","unstructured":"Kratsch, S., Wahlstr\u00f6m, M.: Representative sets and irrelevant vertices: New tools for kernelization. CoRR abs\/1111.2195 (2011)","key":"20_CR19","DOI":"10.1109\/FOCS.2012.46"},{"doi-asserted-by":"crossref","unstructured":"Kratsch, S., Wahlstr\u00f6m, M.: Compression via matroids: a randomized polynomial kernel for odd cycle transversal. In: SODA 2012, pp. 94\u2013103 (2012)","key":"20_CR20","DOI":"10.1137\/1.9781611973099.8"},{"doi-asserted-by":"crossref","unstructured":"Marx, D., Razgon, I.: Fixed-parameter tractability of multicut parameterized by the size of the cutset. In: STOC 2011, pp. 469\u2013478 (2011)","key":"20_CR21","DOI":"10.1145\/1993636.1993699"},{"doi-asserted-by":"crossref","unstructured":"Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford University Press (2006)","key":"20_CR22","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001"},{"doi-asserted-by":"crossref","unstructured":"Reed, B.A., Smith, K., Vetta, A.: Finding odd cycle transversals. Oper. Res. Lett. (2004)","key":"20_CR23","DOI":"10.1016\/j.orl.2003.10.009"},{"issue":"2","key":"20_CR24","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1007\/BF01200760","volume":"15","author":"P.D. Seymour","year":"1995","unstructured":"Seymour, P.D.: Packing directed circuits fractionally. Combinatorica\u00a015(2), 281\u2013288 (1995)","journal-title":"Combinatorica"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-31594-7_20.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T12:14:52Z","timestamp":1620130492000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-31594-7_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642315930","9783642315947"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-31594-7_20","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}