{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,11]],"date-time":"2026-04-11T13:36:27Z","timestamp":1775914587687,"version":"3.50.1"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"9","license":[{"start":{"date-parts":[[2017,10,25]],"date-time":"2017-10-25T00:00:00Z","timestamp":1508889600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["306465"],"award-info":[{"award-number":["306465"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2018,9]]},"DOI":"10.1007\/s00453-017-0388-z","type":"journal-article","created":{"date-parts":[[2017,10,25]],"date-time":"2017-10-25T15:17:53Z","timestamp":1508944673000},"page":"2574-2615","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["Linear Kernels and Linear-Time Algorithms for Finding Large Cuts"],"prefix":"10.1007","volume":"80","author":[{"given":"Michael","family":"Etscheid","sequence":"first","affiliation":[]},{"given":"Matthias","family":"Mnich","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,10,25]]},"reference":[{"issue":"3","key":"388_CR1","doi-asserted-by":"crossref","first-page":"638","DOI":"10.1007\/s00453-010-9428-7","volume":"61","author":"N Alon","year":"2011","unstructured":"Alon, N., Gutin, G., Kim, E.J., Szeider, S., Yeo, A.: Solving MAX-\n                        $$r$$\n                        \n                            \n                                r\n                            \n                        \n                    -SAT above a tight lower bound. Algorithmica 61(3), 638\u2013655 (2011)","journal-title":"Algorithmica"},{"issue":"10","key":"388_CR2","doi-asserted-by":"crossref","first-page":"3241","DOI":"10.1088\/0305-4470\/15\/10\/028","volume":"15","author":"F Barahona","year":"1982","unstructured":"Barahona, F.: On the computational complexity of Ising spin glass models. J. Phys. A 15(10), 3241\u20133253 (1982)","journal-title":"J. Phys. A"},{"key":"388_CR3","first-page":"185","volume-title":"Contemporary Combinatorics, Bolyai Society Mathematical Studies","author":"B Bollob\u00e1s","year":"2002","unstructured":"Bollob\u00e1s, B., Scott, A.: Better bounds for max cut. In: Bollob\u00e1s, B. (ed.) Contemporary Combinatorics, Bolyai Society Mathematical Studies, vol. 10, pp. 185\u2013246. Springer, Berlin (2002)"},{"issue":"1","key":"388_CR4","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1109\/TCAD.2006.882642","volume":"26","author":"C Chiang","year":"2007","unstructured":"Chiang, C., Kahng, A.B., Sinha, S., Xu, X., Zelikovsky, A.Z.: Fast and efficient bright-field AAPSM conflict detection and correction. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 26(1), 115\u2013126 (2007)","journal-title":"IEEE Trans. Comput. Aided Des. Integr. Circuits Syst."},{"issue":"4","key":"388_CR5","doi-asserted-by":"crossref","first-page":"687","DOI":"10.1016\/j.jcss.2013.10.002","volume":"80","author":"R Crowston","year":"2014","unstructured":"Crowston, R., Fellows, M., Gutin, G., Jones, M., Kim, E.J., Rosamond, F., Ruzsa, I.Z., Thomass\u00e9, S., Yeo, A.: Satisfying more than half of a system of linear equations over \n                        $${\\rm GF}(2)$$\n                        \n                            \n                                \n                                    GF\n                                    (\n                                    2\n                                    )\n                                \n                            \n                        \n                    : a multivariate approach. J. Comput. Syst. Sci. 80(4), 687\u2013696 (2014)","journal-title":"J. Comput. Syst. Sci."},{"key":"388_CR6","unstructured":"Crowston, R., Gutin, G., Jones, M.: Directed acyclic subgraph problem parameterized above the Poljak\u2013Turz\u00edk bound. In: Proceedings of FSTTCS 2012, Leibniz International Proceedings in Informatics, vol. 18, pp. 400\u2013411, Hyderabad (2012)"},{"key":"388_CR7","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/j.tcs.2013.10.026","volume":"513","author":"R Crowston","year":"2013","unstructured":"Crowston, R., Gutin, G., Jones, M., Muciaccia, G.: Maximum balanced subgraph problem parameterized above lower bound. Theor. Comput. Sci. 513, 53\u201364 (2013)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"388_CR8","doi-asserted-by":"crossref","first-page":"734","DOI":"10.1007\/s00453-014-9870-z","volume":"72","author":"R Crowston","year":"2015","unstructured":"Crowston, R., Jones, M., Mnich, M.: Max-cut parameterized above the Edwards\u2013Erd\u0151s bound. Algorithmica 72(3), 734\u2013757 (2015)","journal-title":"Algorithmica"},{"key":"388_CR9","unstructured":"Crowston, R., Jones, M., Muciaccia, G., Philip, G., Rai, A., Saurabh, S.: Polynomial kernels for \n                        $$\\lambda $$\n                        \n                            \n                                \u03bb\n                            \n                        \n                    -extendible properties parameterized above the Poljak\u2013Turz\u00edk bound. In: Proceedings of FSTTCS 2013, Leibniz International Proceedings in Informatics, vol. 24, pp. 43\u201354, Guwahati (2013)"},{"key":"388_CR10","unstructured":"Dorn, F.: Planar subgraph isomorphism revisited. In: Proceedings of STACS 2010, Leibniz International Proceedings in Informatics, vol. 5, pp. 263\u2013274 (2010)"},{"issue":"2","key":"388_CR11","doi-asserted-by":"crossref","first-page":"1355","DOI":"10.1137\/16M1061862","volume":"31","author":"Z Dvo\u0159\u00e1k","year":"2017","unstructured":"Dvo\u0159\u00e1k, Z., Mnich, M.: Large independent sets in triangle-free planar graphs. SIAM J. Discrete Math. 31(2), 1355\u20131373 (2017)","journal-title":"SIAM J. Discrete Math."},{"key":"388_CR12","doi-asserted-by":"crossref","first-page":"475","DOI":"10.4153\/CJM-1973-048-x","volume":"25","author":"CS Edwards","year":"1973","unstructured":"Edwards, C.S.: Some extremal properties of bipartite subgraphs. Can. J. Math. 25, 475\u2013485 (1973)","journal-title":"Can. J. Math."},{"key":"388_CR13","unstructured":"Edwards, C.S.: An improved lower bound for the number of edges in a largest bipartite subgraph. In: Recent Advances in Graph Theory, pp. 167\u2013181 (1975)"},{"key":"388_CR14","unstructured":"Etscheid, M., Mnich, M.: Linear kernels and linear-time algorithms for finding large cuts. In: Proceedings of ISAAC 2016, Leibniz Int. Proc. Informatics, vol. 64, pp. 31:1\u201331:13 (2016)"},{"issue":"1","key":"388_CR15","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1016\/j.jcss.2011.01.004","volume":"78","author":"G Gutin","year":"2012","unstructured":"Gutin, G., van Iersel, L., Mnich, M., Yeo, A.: Every ternary permutation constraint satisfaction problem parameterized above average has a kernel with a quadratic number of variables. J. Comput. Syst. Sci. 78(1), 151\u2013163 (2012)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"388_CR16","doi-asserted-by":"crossref","first-page":"521","DOI":"10.1007\/s00224-007-1330-6","volume":"41","author":"G Gutin","year":"2007","unstructured":"Gutin, G., Rafiey, A., Szeider, S., Yeo, A.: The linear arrangement problem parameterized above guaranteed value. Theory Comput. Syst. 41(3), 521\u2013538 (2007)","journal-title":"Theory Comput. Syst."},{"issue":"21","key":"388_CR17","doi-asserted-by":"crossref","first-page":"966","DOI":"10.1016\/j.ipl.2010.08.001","volume":"110","author":"G Gutin","year":"2010","unstructured":"Gutin, G., Yeo, A.: Note on maximal bisection above tight lower bound. Inf. Process. Lett. 110(21), 966\u2013969 (2010)","journal-title":"Inf. Process. Lett."},{"key":"388_CR18","first-page":"143","volume":"2","author":"F Harary","year":"1955","unstructured":"Harary, F.: On the notion of balance of a signed graph (1953\u201354). Mich. Math. J. 2, 143\u2013146 (1955)","journal-title":"Mich. Math. J."},{"key":"388_CR19","doi-asserted-by":"crossref","first-page":"316","DOI":"10.1002\/bs.3830040405","volume":"4","author":"F Harary","year":"1959","unstructured":"Harary, F.: On the measurement of structural balance. Behav. Sci. 4, 316\u2013323 (1959)","journal-title":"Behav. Sci."},{"issue":"3","key":"388_CR20","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1093\/imaman\/13.3.201","volume":"13","author":"F Harary","year":"2002","unstructured":"Harary, F., Lim, M.H., Wunsch, D.C.: Signed graphs for portfolio analysis in risk management. IMA J. Manag. Math. 13(3), 201\u2013210 (2002)","journal-title":"IMA J. Manag. Math."},{"issue":"4","key":"388_CR21","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1007\/s10878-009-9212-2","volume":"20","author":"F H\u00fcffner","year":"2010","unstructured":"H\u00fcffner, F., Betzler, N., Niedermeier, R.: Separator-based data reduction for signed graph balancing. J. Comb. Optim. 20(4), 335\u2013360 (2010)","journal-title":"J. Comb. Optim."},{"issue":"4","key":"388_CR22","doi-asserted-by":"crossref","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? J. Comput. Syst. Sci. 63(4), 512\u2013530 (2001)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"388_CR23","doi-asserted-by":"crossref","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":"388_CR24","doi-asserted-by":"crossref","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Complexity of computer computations (Proc. Sympos., IBM Thomas J. Watson Res. Center, Yorktown Heights, NY, 1972), pp. 85\u2013103. Plenum, New York (1972)","DOI":"10.1007\/978-1-4684-2001-2_9"},{"issue":"1\u20132","key":"388_CR25","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1016\/S0304-3975(99)00150-4","volume":"250","author":"T Knuutila","year":"2001","unstructured":"Knuutila, T.: Re-describing an algorithm by Hopcroft. Theor. Comput. Sci. 250(1\u20132), 333\u2013363 (2001)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"388_CR26","doi-asserted-by":"crossref","first-page":"453","DOI":"10.1007\/BF01456961","volume":"77","author":"D K\u00f6nig","year":"1916","unstructured":"K\u00f6nig, D.: \u00dcber Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre. Math. Ann. 77(4), 453\u2013465 (1916)","journal-title":"Math. Ann."},{"key":"388_CR27","doi-asserted-by":"crossref","unstructured":"Lokshtanov, D., Ramanujan, M.S., Saurabh, S.: Linear time parameterized algorithms for subset feedback vertex set. In: Proceedings of ICALP 2015. Lecture Notes Computer Science, vol. 9134, pp. 935\u2013946 (2015)","DOI":"10.1007\/978-3-662-47672-7_76"},{"key":"388_CR28","unstructured":"Mahajan, M., Raman, V.: Parameterizing above guaranteed values: MaxSat and MaxCut. Tech. Rep. TR97-033, Electronic Colloquium on Computational Complexity (1997). \n                        http:\/\/eccc.hpi-web.de\/report\/1997\/033\/"},{"issue":"2","key":"388_CR29","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1016\/j.jcss.2008.08.004","volume":"75","author":"M Mahajan","year":"2009","unstructured":"Mahajan, M., Raman, V., Sikdar, S.: Parameterizing above or below guaranteed values. J. Comput. Syst. Sci. 75(2), 137\u2013153 (2009)","journal-title":"J. Comput. Syst. Sci."},{"issue":"7","key":"388_CR30","doi-asserted-by":"crossref","first-page":"1384","DOI":"10.1016\/j.jcss.2014.04.011","volume":"80","author":"M Mnich","year":"2014","unstructured":"Mnich, M., Philip, G., Saurabh, S., Such\u00fd, O.: Beyond Max-Cut: \n                        $$\\lambda $$\n                        \n                            \n                                \u03bb\n                            \n                        \n                    -extendible properties parameterized above the Poljak\u2013Turz\u00edk bound. J. Comput. Syst. Sci. 80(7), 1384\u20131403 (2014)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"388_CR31","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1017\/S0963548300000596","volume":"2","author":"NV Ng\u1ecdc","year":"1993","unstructured":"Ng\u1ecdc, N.V., Tuza, Z.: Linear-time approximation algorithms for the max cut problem. Comb. Probab. Comput. 2(2), 201\u2013210 (1993)","journal-title":"Comb. Probab. Comput."},{"issue":"1","key":"388_CR32","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1016\/0012-365X(86)90192-5","volume":"58","author":"S Poljak","year":"1986","unstructured":"Poljak, S., Turz\u00edk, D.: A polynomial time heuristic for certain subgraph optimization problems with guaranteed worst case bound. Discrete Math. 58(1), 99\u2013104 (1986)","journal-title":"Discrete Math."},{"key":"388_CR33","doi-asserted-by":"crossref","unstructured":"Poljak, S., Tuza, Z.: Maximum cuts and large bipartite subgraphs. In: Combinatorial Optimization (New Brunswick, NJ, 1992\u20131993), DIMACS Series in Discrete Mathematics Theoretical Computer Science, vol. 20, pp. 181\u2013244 (1995)","DOI":"10.1090\/dimacs\/020\/04"},{"issue":"3","key":"388_CR34","doi-asserted-by":"crossref","first-page":"446","DOI":"10.1016\/j.tcs.2005.10.010","volume":"351","author":"V Raman","year":"2006","unstructured":"Raman, V., Saurabh, S.: Parameterized algorithms for feedback set problems and their duals in tournaments. Theor. Comput. Sci. 351(3), 446\u2013458 (2006)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"388_CR35","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1016\/j.ipl.2007.05.014","volume":"104","author":"V Raman","year":"2007","unstructured":"Raman, V., Saurabh, S.: Improved fixed parameter tractable algorithms for two \u201cedge\u201d problems: MAXCUT and MAXDAG. Inf. Process. Lett. 104(2), 65\u201372 (2007)","journal-title":"Inf. Process. Lett."},{"key":"388_CR36","unstructured":"van Bevern, R.: Fixed-parameter linear-time algorithms for NP-hard graph and hypergraph problems arising in industrial applications. Ph.D. thesis, TU Berlin (2014)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-017-0388-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-0388-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-017-0388-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2018,5,22]],"date-time":"2018-05-22T10:55:16Z","timestamp":1526986516000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-017-0388-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,10,25]]},"references-count":36,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2018,9]]}},"alternative-id":["388"],"URL":"https:\/\/doi.org\/10.1007\/s00453-017-0388-z","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,10,25]]}}}