{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,19]],"date-time":"2026-03-19T05:26:54Z","timestamp":1773898014476,"version":"3.50.1"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"8","license":[{"start":{"date-parts":[[2019,8,2]],"date-time":"2019-08-02T00:00:00Z","timestamp":1564704000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2019,8,2]],"date-time":"2019-08-02T00:00:00Z","timestamp":1564704000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100010663","name":"H2020 European Research Council","doi-asserted-by":"publisher","award":["714704"],"award-info":[{"award-number":["714704"]}],"id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100010663","name":"H2020 European Research Council","doi-asserted-by":"publisher","award":["714704"],"award-info":[{"award-number":["714704"]}],"id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100010663","name":"H2020 European Research Council","doi-asserted-by":"publisher","award":["725978"],"award-info":[{"award-number":["725978"]}],"id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100011199","name":"FP7 Ideas: European Research Council","doi-asserted-by":"publisher","award":["280152"],"award-info":[{"award-number":["280152"]}],"id":[{"id":"10.13039\/100011199","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/P007228\/1"],"award-info":[{"award-number":["EP\/P007228\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2020,8]]},"DOI":"10.1007\/s00453-019-00609-1","type":"journal-article","created":{"date-parts":[[2019,8,2]],"date-time":"2019-08-02T10:48:58Z","timestamp":1564742938000},"page":"2135-2155","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Multi-budgeted Directed Cuts"],"prefix":"10.1007","volume":"82","author":[{"given":"Stefan","family":"Kratsch","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shaohua","family":"Li","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"D\u00e1niel","family":"Marx","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5680-7397","authenticated-orcid":false,"given":"Marcin","family":"Pilipczuk","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Magnus","family":"Wahlstr\u00f6m","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,8,2]]},"reference":[{"key":"609_CR1","unstructured":"Agarwal, A., Alon, N., Charikar, M.: Improved approximation for directed cut problems. In: Johnson, D.S., Feige, U. (eds.) Proceedings of the 39th Annual ACM Symposium on Theory of Computing, San Diego, California, USA, June 11\u201313, 2007, pp. 671\u2013680. ACM (2007)"},{"issue":"1","key":"609_CR2","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1137\/S0895480104445095","volume":"20","author":"C Chekuri","year":"2006","unstructured":"Chekuri, C., Guha, S., Naor, J.: The steiner k-cut problem. SIAM J. Discrete Math. 20(1), 261\u2013271 (2006)","journal-title":"SIAM J. Discrete Math."},{"issue":"4","key":"609_CR3","doi-asserted-by":"publisher","first-page":"833","DOI":"10.1016\/j.jcss.2003.09.003","volume":"67","author":"J Chen","year":"2003","unstructured":"Chen, J., Kanj, I.A.: Constrained minimum vertex cover in bipartite graphs: complexity and parameterized algorithms. J. Comput. Syst. Sci. 67(4), 833\u2013847 (2003)","journal-title":"J. Comput. Syst. Sci."},{"issue":"5","key":"609_CR4","doi-asserted-by":"publisher","first-page":"21:1","DOI":"10.1145\/1411509.1411511","volume":"55","author":"J Chen","year":"2008","unstructured":"Chen, J., Liu, Y., Lu, S., O\u2019Sullivan, B., Razgon, I.: A fixed-parameter algorithm for the directed feedback vertex set problem. J. ACM 55(5), 21:1\u201321:19 (2008)","journal-title":"J. ACM"},{"issue":"4","key":"609_CR5","doi-asserted-by":"publisher","first-page":"1171","DOI":"10.1137\/15M1032077","volume":"45","author":"R Chitnis","year":"2016","unstructured":"Chitnis, R., Cygan, M., Hajiaghayi, M., Pilipczuk, M., Pilipczuk, M.: Designing FPT algorithms for cut problems using randomized contractions. SIAM J. Comput. 45(4), 1171\u20131229 (2016)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"609_CR6","doi-asserted-by":"publisher","first-page":"110","DOI":"10.1007\/s00453-016-0139-6","volume":"78","author":"R Chitnis","year":"2017","unstructured":"Chitnis, R., Egri, L., Marx, D.: List h-coloring a graph by removing few vertices. Algorithmica 78(1), 110\u2013146 (2017)","journal-title":"Algorithmica"},{"key":"609_CR7","doi-asserted-by":"crossref","unstructured":"Chitnis, R.H., Cygan, M., Hajiaghayi, M.T., Marx, D.: Directed subset feedback vertex set is fixed-parameter tractable. In: Czumaj, A., Mehlhorn, K., Pitts, A.M., Wattenhofer, R. (eds.) ICALP (1). Lecture Notes in Computer Science, vol. 7391, pp. 230\u2013241. Springer (2012)","DOI":"10.1007\/978-3-642-31594-7_20"},{"issue":"4","key":"609_CR8","doi-asserted-by":"publisher","first-page":"1674","DOI":"10.1137\/12086217X","volume":"42","author":"RH Chitnis","year":"2013","unstructured":"Chitnis, R.H., Hajiaghayi, M., Marx, D.: Fixed-parameter tractability of directed multiway cut parameterized by the size of the cutset. SIAM J. Comput. 42(4), 1674\u20131696 (2013)","journal-title":"SIAM J. Comput."},{"key":"609_CR9","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Cham (2015)"},{"issue":"1","key":"609_CR10","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1145\/2462896.2462899","volume":"5","author":"M Cygan","year":"2013","unstructured":"Cygan, M., Pilipczuk, M., Pilipczuk, M., Wojtaszczyk, J.O.: On multiway cut parameterized above lower bounds. TOCT 5(1), 3 (2013)","journal-title":"TOCT"},{"issue":"2","key":"609_CR11","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1007\/PL00009191","volume":"20","author":"G Even","year":"1998","unstructured":"Even, G., Naor, J., Schieber, B., Sudan, M.: Approximating minimum feedback sets and multicuts in directed graphs. Algorithmica 20(2), 151\u2013174 (1998)","journal-title":"Algorithmica"},{"key":"609_CR12","unstructured":"Faliszewski, P., Fomin, F.V., Lokshtanov, D., Marx, D., Onn, S., Pilipczuk, M., Pilipczuk, M., Saurabh, S., Zehavi, M.: What\u2019s next? Future directions in parameterized complexity. Recent Advances in Parameterized Complexity, Tel-Aviv, Israel (2017). Accessed 18 Sept 2018"},{"issue":"2","key":"609_CR13","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1137\/S0097539793243016","volume":"25","author":"N Garg","year":"1996","unstructured":"Garg, N., Vazirani, V.V., Yannakakis, M.: Approximate max-flow min-(multi)cut theorems and their applications. SIAM J. Comput. 25(2), 235\u2013251 (1996)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"609_CR14","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/S0196-6774(03)00111-1","volume":"50","author":"N Garg","year":"2004","unstructured":"Garg, N., Vazirani, V.V., Yannakakis, M.: Multiway cuts in node weighted graphs. J. Algorithms 50(1), 49\u201361 (2004)","journal-title":"J. Algorithms"},{"issue":"1","key":"609_CR15","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1016\/j.disopt.2010.05.003","volume":"8","author":"S Guillemot","year":"2011","unstructured":"Guillemot, S.: FPT algorithms for path-transversal and cycle-transversal problems. Discrete Optim. 8(1), 61\u201371 (2011)","journal-title":"Discrete Optim."},{"key":"609_CR16","unstructured":"Iwata, Y.: Linear-time kernelization for feedback vertex set. In: Chatzigiannakis, I., Indyk, P., Kuhn, F., Muscholl, A. (eds.) 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10\u201314, 2017, Warsaw, Poland. LIPIcs, vol. 80, pp. 68:1\u201368:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2017)"},{"issue":"4","key":"609_CR17","doi-asserted-by":"publisher","first-page":"1377","DOI":"10.1137\/140962838","volume":"45","author":"Y Iwata","year":"2016","unstructured":"Iwata, Y., Wahlstr\u00f6m, M., Yoshida, Y.: Half-integrality, LP-branching, and FPT algorithms. SIAM J. Comput. 45(4), 1377\u20131411 (2016)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"609_CR18","doi-asserted-by":"publisher","first-page":"436","DOI":"10.1287\/moor.1030.0086","volume":"29","author":"DR Karger","year":"2004","unstructured":"Karger, D.R., Klein, P.N., Stein, C., Thorup, M., Young, N.E.: Rounding algorithms for a geometric embedding of minimum multiway cut. Math. Oper. Res. 29(3), 436\u2013461 (2004)","journal-title":"Math. Oper. Res."},{"key":"609_CR19","unstructured":"Kratsch, S., Li, S., Marx, D., Pilipczuk, M., Wahlstr\u00f6m, M.: Multi-budgeted directed cuts. In: Paul, C., Pilipczuk, M. (eds.) 13th International Symposium on Parameterized and Exact Computation, IPEC 2018, August 20\u201324, 2018, Helsinki, Finland. LIPIcs, vol. 115, pp. 18:1\u201318:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2018)"},{"key":"609_CR20","unstructured":"Kratsch, S., Wahlstr\u00f6m, M.: Representative sets and irrelevant vertices: new tools for kernelization. In: 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20\u201323, 2012, pp. 450\u2013459. IEEE Computer Society (2012)"},{"issue":"4","key":"609_CR21","first-page":"20","volume":"10","author":"S Kratsch","year":"2014","unstructured":"Kratsch, S., Wahlstr\u00f6m, M.: Compression via matroids: a randomized polynomial kernel for odd cycle transversal. ACM Trans. Algorithms 10(4), 20 (2014)","journal-title":"ACM Trans. Algorithms"},{"key":"609_CR22","doi-asserted-by":"crossref","unstructured":"Lokshtanov, D., Ramanujan, M.S., Saurabh, S.: A linear time parameterized algorithm for directed feedback vertex set. CoRR, abs\/1609.04347 (2016)","DOI":"10.1007\/978-3-662-47672-7_76"},{"key":"609_CR23","unstructured":"Lokshtanov, D., Ramanujan, M.S., Saurabh, S., Zehavi, M.: Parameterized complexity and approximability of directed odd cycle transversal. CoRR, abs\/1704.04249 (2017)"},{"issue":"3","key":"609_CR24","doi-asserted-by":"publisher","first-page":"394","DOI":"10.1016\/j.tcs.2005.10.007","volume":"351","author":"D Marx","year":"2006","unstructured":"Marx, D.: Parameterized graph separation problems. Theor. Comput. Sci. 351(3), 394\u2013406 (2006)","journal-title":"Theor. Comput. Sci."},{"key":"609_CR25","unstructured":"Marx, D.: What\u2019s next? Future directions in parameterized complexity. In: Bodlaender, H.L., Downey, R., Fomin, F.V., Marx, D. (eds.) The Multivariate Algorithmic Revolution and Beyond\u2014Essays Dedicated to Michael R. Fellows on the Occasion of His 60th Birthday. Lecture Notes in Computer Science, vol. 7370, pp. 469\u2013496. Springer (2012)"},{"issue":"4","key":"609_CR26","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1145\/2500119","volume":"9","author":"D Marx","year":"2013","unstructured":"Marx, D., O\u2019Sullivan, B., Razgon, I.: Finding small separators in linear time via treewidth reduction. ACM Trans. Algorithms 9(4), 30 (2013)","journal-title":"ACM Trans. Algorithms"},{"issue":"2","key":"609_CR27","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1137\/110855247","volume":"43","author":"D Marx","year":"2014","unstructured":"Marx, D., Razgon, I.: Fixed-parameter tractability of multicut parameterized by the size of the cutset. SIAM J. Comput. 43(2), 355\u2013388 (2014)","journal-title":"SIAM J. Comput."},{"key":"609_CR28","unstructured":"Pilipczuk, M., Wahlstr\u00f6m, M.: Directed multicut is W[1]-hard, even for four terminal pairs. In: Krauthgamer, R. (ed.) Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10\u201312, 2016, pp. 1167\u20131178. SIAM (2016)"},{"issue":"8","key":"609_CR29","doi-asserted-by":"publisher","first-page":"435","DOI":"10.1016\/j.jcss.2009.04.002","volume":"75","author":"I Razgon","year":"2009","unstructured":"Razgon, I., O\u2019Sullivan, B.: Almost 2-sat is fixed-parameter tractable. J. Comput. Syst. Sci. 75(8), 435\u2013450 (2009)","journal-title":"J. Comput. Syst. Sci."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00609-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-019-00609-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00609-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,25]],"date-time":"2022-09-25T01:53:07Z","timestamp":1664070787000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-019-00609-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,8,2]]},"references-count":29,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2020,8]]}},"alternative-id":["609"],"URL":"https:\/\/doi.org\/10.1007\/s00453-019-00609-1","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,8,2]]},"assertion":[{"value":"16 October 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 July 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 August 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}