{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,25]],"date-time":"2026-09-25T08:22:59Z","timestamp":1790324579418,"version":"4.1.0"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2017,5,12]],"date-time":"2017-05-12T00:00:00Z","timestamp":1494547200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100004281","name":"Narodowe Centrum Nauki","doi-asserted-by":"publisher","award":["DEC-2013\/11\/D\/ST6\/03073"],"award-info":[{"award-number":["DEC-2013\/11\/D\/ST6\/03073"]}],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004281","name":"Narodowe Centrum Nauki","doi-asserted-by":"publisher","award":["DEC-2013\/11\/D\/ST6\/03073"],"award-info":[{"award-number":["DEC-2013\/11\/D\/ST6\/03073"]}],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001870","name":"Fundacja na rzecz Nauki Polskiej","doi-asserted-by":"publisher","award":["START"],"award-info":[{"award-number":["START"]}],"id":[{"id":"10.13039\/501100001870","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Centre for Discrete Mathematics and its Applications"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2019,3]]},"DOI":"10.1007\/s00453-017-0319-z","type":"journal-article","created":{"date-parts":[[2017,5,12]],"date-time":"2017-05-12T12:36:50Z","timestamp":1494592610000},"page":"917-966","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Edge Bipartization Faster than $$2^k$$ 2 k"],"prefix":"10.1007","volume":"81","author":[{"given":"Marcin","family":"Pilipczuk","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Micha\u0142","family":"Pilipczuk","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Marcin","family":"Wrochna","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2017,5,12]]},"reference":[{"issue":"4","key":"319_CR1","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1016\/j.ipl.2013.12.001","volume":"114","author":"Y Cao","year":"2014","unstructured":"Cao, Y., Chen, J., Fan, J.: An $$\\cal{O}^{\\star } (1.84^k)$$ O \u22c6 ( 1 . 84 k ) parameterized algorithm for the multiterminal cut problem. Inf. Process. Lett. 114(4), 167\u2013173 (2014)","journal-title":"Inf. Process. Lett."},{"key":"319_CR2","doi-asserted-by":"publisher","first-page":"734","DOI":"10.4153\/CJM-1980-057-7","volume":"32","author":"WH Cunnigham","year":"1980","unstructured":"Cunnigham, W.H., Edmonds, J.: A combinatorial decomposition theory. Can. J. Math. 32, 734\u2013765 (1980)","journal-title":"Can. J. Math."},{"issue":"3","key":"319_CR3","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1145\/2925416","volume":"12","author":"M Cygan","year":"2016","unstructured":"Cygan, M., Dell, H., Lokshtanov, D., Marx, D., Nederlof, J., Okamoto, Y., Paturi, R., Saurabh, S., Wahlstr\u00f6m, M.: On problems as hard as CNF-SAT. ACM Trans. Algorithms 12(3), 41 (2016)","journal-title":"ACM Trans. Algorithms"},{"key":"319_CR4","unstructured":"Cygan, M., Fomin, F.V., Jansen, B.M.P., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Open problems from the school on parameterized algorithms and complexity, Bedlewo (2014). http:\/\/fptschool.mimuw.edu.pl\/opl.pdf"},{"key":"319_CR5","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., Loksthanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Berlin (2015)"},{"key":"319_CR6","unstructured":"Cygan, M., Kowalik, L., Pilipczuk, M.: Open problems from the update meeting on graph separation problems. Workshop on Kernels, Warsaw (2013). http:\/\/worker2013.mimuw.edu.pl\/slides\/update-opl.pdf"},{"key":"319_CR7","doi-asserted-by":"crossref","unstructured":"Cygan, M., Kratsch, S., Nederlof, J.: Fast hamiltonicity checking via bases of perfect matchings. In: Proceedings of STOC\u201913, pp. 301\u2013310. ACM (2013)","DOI":"10.1145\/2488608.2488646"},{"key":"319_CR8","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: Proceedings of FOCS\u201911, pp. 150\u2013159. IEEE (2011)","DOI":"10.1109\/FOCS.2011.23"},{"issue":"1","key":"319_CR9","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"},{"key":"319_CR10","volume-title":"Graph Theory","author":"R Diestel","year":"2005","unstructured":"Diestel, R.: Graph Theory. Springer, Berlin (2005)"},{"key":"319_CR11","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5559-1","volume-title":"Fundamentals of Parameterized Complexity. Texts in Computer Science","author":"RG Downey","year":"2013","unstructured":"Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, Berlin (2013)"},{"key":"319_CR12","volume-title":"Exact Exponential Algorithms. Texts in Theoretical Computer Science. An EATCS Series","author":"FV Fomin","year":"2010","unstructured":"Fomin, F.V., Kratsch, D.: Exact Exponential Algorithms. Texts in Theoretical Computer Science. An EATCS Series. Springer, Berlin (2010)"},{"issue":"1","key":"319_CR13","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."},{"issue":"8","key":"319_CR14","doi-asserted-by":"publisher","first-page":"1386","DOI":"10.1016\/j.jcss.2006.02.001","volume":"72","author":"J Guo","year":"2006","unstructured":"Guo, J., Gramm, J., H\u00fcffner, F., Niedermeier, R., Wernicke, S.: Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization. J. Comput. Syst. Sci. 72(8), 1386\u20131396 (2006)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"319_CR15","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1137\/0202012","volume":"2","author":"JE Hopcroft","year":"1973","unstructured":"Hopcroft, J.E., Tarjan, R.E.: Dividing a graph into triconnected components. SIAM J. Comput. 2(3), 135\u2013158 (1973)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"319_CR16","doi-asserted-by":"publisher","first-page":"77","DOI":"10.7155\/jgaa.00177","volume":"13","author":"F H\u00fcffner","year":"2009","unstructured":"H\u00fcffner, F.: Algorithm engineering for optimal graph bipartization. J. Graph Algorithms Appl. 13(2), 77\u201398 (2009)","journal-title":"J. Graph Algorithms Appl."},{"issue":"4","key":"319_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."},{"key":"319_CR18","doi-asserted-by":"crossref","unstructured":"Kawarabayashi, K., Reed, B.A.: An (almost) linear time algorithm for odd cyles transversal. In: Proceedings of SODA\u201910, pp. 365\u2013378. SIAM (2010)","DOI":"10.1137\/1.9781611973075.31"},{"key":"319_CR19","doi-asserted-by":"crossref","unstructured":"Kolay, S., Misra, P., Ramanujan, M.S., Saurabh, S.: Parameterized approximations via $$d$$ d -skew-symmetric multicut. In: Proceedings of MFCS\u201914. Lecture notes in computer science, vol. 8635, pp. 457\u2013468. Springer (2014)","DOI":"10.1007\/978-3-662-44465-8_39"},{"key":"319_CR20","unstructured":"Kolay, S., Panolan, F., Raman, V., Saurabh, S.: Parameterized algorithms on perfect graphs for deletion to (r, l)-graphs. In: Proceedings of MFCS\u201914, LIPIcs, vol. 58, pp. 75:1\u201375:13. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik (2016)"},{"issue":"1","key":"319_CR21","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/130945648","volume":"44","author":"V Kolmogorov","year":"2015","unstructured":"Kolmogorov, V., Thapper, J., \u017divn\u00fd, S.: The power of linear programming for general-valued CSPs. SIAM J. Comput. 44(1), 1\u201336 (2015)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"319_CR22","first-page":"20:1","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:1\u201320:15 (2014)","journal-title":"ACM Trans. Algorithms"},{"key":"319_CR23","doi-asserted-by":"crossref","unstructured":"Lokshtanov, D., Marx, D., Saurabh, S.: Known algorithms on graphs on bounded treewidth are probably optimal. In: Proceedings of SODA\u201911, pp. 777\u2013789. SIAM (2011)","DOI":"10.1137\/1.9781611973082.61"},{"key":"319_CR24","first-page":"41","volume":"105","author":"D Lokshtanov","year":"2011","unstructured":"Lokshtanov, D., Marx, D., Saurabh, S.: Lower bounds based on the exponential time hypothesis. Bull. EATCS 105, 41\u201372 (2011)","journal-title":"Bull. EATCS"},{"issue":"2","key":"319_CR25","doi-asserted-by":"publisher","first-page":"15:1","DOI":"10.1145\/2566616","volume":"11","author":"D Lokshtanov","year":"2014","unstructured":"Lokshtanov, D., Narayanaswamy, N.S., Raman, V., Ramanujan, M.S., Saurabh, S.: Faster parameterized algorithms using linear programming. ACM Trans. Algorithms 11(2), 15:1\u201315:31 (2014)","journal-title":"ACM Trans. Algorithms"},{"key":"319_CR26","doi-asserted-by":"crossref","unstructured":"Lokshtanov, D., Saurabh, S., Sikdar, S.: Simpler parameterized algorithm for OCT. In: Proceedings of IWOCA\u201909, pp. 380\u2013384. Springer (2009)","DOI":"10.1007\/978-3-642-10217-2_37"},{"key":"319_CR27","first-page":"469","volume-title":"What\u2019s next? Future directions in parameterized complexity. The multivariate algorithmic revolution and beyond. Lecture Notes in Computer Science","author":"D Marx","year":"2012","unstructured":"Marx, D.: What\u2019s next? Future directions in parameterized complexity. The multivariate algorithmic revolution and beyond. Lecture Notes in Computer Science, vol. 7370, pp. 469\u2013496. Springer, Berlin (2012)"},{"issue":"4","key":"319_CR28","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1016\/j.orl.2003.10.009","volume":"32","author":"BA Reed","year":"2004","unstructured":"Reed, B.A., Smith, K., Vetta, A.: Finding odd cycle transversals. Oper. Res. Lett. 32(4), 299\u2013301 (2004)","journal-title":"Oper. Res. Lett."},{"key":"319_CR29","doi-asserted-by":"crossref","DOI":"10.3138\/9781487584863","volume-title":"Connectivity in graphs, Mathematical expositions","author":"W Tutte","year":"1966","unstructured":"Tutte, W.: Connectivity in graphs, Mathematical expositions, vol. 15. University of Toronto Press, Toronto (1966)"},{"key":"319_CR30","doi-asserted-by":"crossref","unstructured":"Wahlstr\u00f6m, M.: Half-integrality, LP-branching and FPT algorithms. In: Proceedings of SODA\u201914, pp. 1762\u20131781. SIAM (2014)","DOI":"10.1137\/1.9781611973402.128"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-017-0319-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-017-0319-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-017-0319-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,10,7]],"date-time":"2020-10-07T12:34:42Z","timestamp":1602074082000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-017-0319-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,5,12]]},"references-count":30,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2019,3]]}},"alternative-id":["319"],"URL":"https:\/\/doi.org\/10.1007\/s00453-017-0319-z","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,5,12]]},"assertion":[{"value":"27 October 2016","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 April 2017","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 May 2017","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}