{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,24]],"date-time":"2026-09-24T12:15:08Z","timestamp":1790252108047,"version":"4.1.0"},"reference-count":28,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2013,1]]},"abstract":"<jats:p>The Bipartite Contraction problem takes as input an $n$-vertex graph $G$ and an integer $k$, and the task is to determine whether we can obtain a bipartite graph from $G$ by a sequence of at most $k$ edge contractions. We show that Bipartite Contraction is fixed-parameter tractable when parameterized by $k$. Despite a strong resemblance between Bipartite Contraction and the classical Odd Cycle Transversal (OCT) problem, the methods developed to tackle OCT do not seem to be directly applicable to Bipartite Contraction. To obtain our result, we combine several techniques and concepts that are central in parameterized complexity: iterative compression, irrelevant vertices, and important separators. To the best of our knowledge, this is the first time the irrelevant vertex technique and the concept of important separators are applied in unison. Furthermore, our algorithm may serve as a comprehensible example of the usage of the irrelevant vertex technique.<\/jats:p>","DOI":"10.1137\/130907392","type":"journal-article","created":{"date-parts":[[2013,12,19]],"date-time":"2013-12-19T12:33:27Z","timestamp":1387456407000},"page":"2143-2156","source":"Crossref","is-referenced-by-count":27,"title":["Obtaining a Bipartite Graph by Contracting Few Edges"],"prefix":"10.1137","volume":"27","author":[{"given":"Pinar","family":"Heggernes","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pim Van 'T","family":"Hof","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Daniel","family":"Lokshtanov","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Christophe","family":"Paul","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2013,12,19]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(83)90012-0"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190110111"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(90)90043-H"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-007-9130-6"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1145\/1411509.1411511"},{"key":"atypb6","first-page":"329","author":"Demaine E. D.","year":"2010","journal-title":"Philadelphia"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1998.1862"},{"key":"atypb8","doi-asserted-by":"crossref","unstructured":"R. G. Downey and M. R. Fellows,<i>Parameterized Complexity<\/i> Monogr. Comput. Sci., Springer-Verlag, New York, 1999.","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2006.02.001"},{"key":"atypb10","unstructured":"P. Heggernes, P. van 't Hof, D. Lokshtanov, and C. Paul,<i>Obtaining a bipartite graph by contracting few edges<\/i> in Proceedings of the 31st International Conference on Foundations of Software, Technology and Theoretical Computer Science (FSTTCS), LIPIcs. Leibniz Int. Proc. Inform. 13, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, Germany, 2011, pp. 217-228."},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00177"},{"key":"atypb12","first-page":"374","author":"Kawarabayashi K.","year":"2008","journal-title":"Berlin"},{"key":"atypb13","first-page":"365","author":"Kawarabayashi K.","year":"2010","journal-title":"Philadelphia"},{"key":"atypb14","doi-asserted-by":"crossref","unstructured":"K. Kawarabayashi and B. A. Reed,<i>Odd cycle packing<\/i> in Proceedings of the 42nd Annual ACM Symposium on Theory of Computing (STOC), 2010, ACM, New York, pp. 695-704.","DOI":"10.1145\/1806689.1806785"},{"key":"atypb15","doi-asserted-by":"crossref","unstructured":"K. Kawarabayashi and P. Wollan,<i>A simpler algorithm and shorter proof for the graph minor decomposition<\/i> in Proceedings of the 43rd Annual ACM Symposium on Theory of Computing (STOC), 2011, ACM, New York, pp. 451-458.","DOI":"10.1145\/1993636.1993697"},{"key":"atypb16","first-page":"94","author":"Kratsch S.","year":"2012","journal-title":"Philadelphia"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1002\/net.20214"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2012.10.016"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.10.007"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1145\/2500119"},{"key":"atypb21","doi-asserted-by":"crossref","unstructured":"D. Marx and I. Razgon,<i>Fixed-parameter tractability of multicut parameterized by the size of the cutset<\/i> in Proceedings of the 43rd Annual ACM Symposium on Theory of Computing (STOC), 2011, ACM, New York, pp. 469-478.","DOI":"10.1145\/1993636.1993699"},{"key":"atypb22","doi-asserted-by":"crossref","unstructured":"R. Niedermeier,<i>Invitation to Fixed-Parameter Algorithms<\/i> Oxford University Press, Oxford, UK, 2006.","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2009.04.002"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2003.10.009"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1995.1006"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2007.12.007"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(81)90039-1"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(83)90101-4"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/130907392","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:23:18Z","timestamp":1787318598000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/130907392"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,1]]},"references-count":28,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2013,1]]}},"alternative-id":["10.1137\/130907392"],"URL":"https:\/\/doi.org\/10.1137\/130907392","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,1]]}}}