{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,18]],"date-time":"2026-09-18T09:10:08Z","timestamp":1789722608695,"version":"4.0.1"},"reference-count":57,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","funder":[{"DOI":"10.13039\/501100004281","name":"Polish National Science Centre","doi-asserted-by":"crossref","award":["N206567140"],"award-info":[{"award-number":["N206567140"]}],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001870","name":"Foundation for Polish Science","doi-asserted-by":"crossref","award":["START"],"award-info":[{"award-number":["START"]}],"id":[{"id":"10.13039\/501100001870","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100000185","name":"Defense Advanced Research Projects Agency","doi-asserted-by":"publisher","award":["FA8650-11-1-7162"],"award-info":[{"award-number":["FA8650-11-1-7162"]}],"id":[{"id":"10.13039\/100000185","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["YIP N000141110662"],"award-info":[{"award-number":["YIP N000141110662"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CAREER 1053605"],"award-info":[{"award-number":["CAREER 1053605"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2016,1]]},"abstract":"<jats:p>We introduce a new technique for designing fixed-parameter algorithms for cut problems, called randomized contractions. We apply our framework to obtain the first fixed-parameter algorithms (FPT algorithms) with exponential speed up for the Steiner Cut and Node Multiway Cut-Uncut problems. We prove that the parameterized version of the Unique Label Cover problem, which is the base of the Unique Games Conjecture, can be solved in $2^{O(k^2\\log |\\Sigma|)}n^4\\log n$ deterministic time (even in the stronger, vertex-deletion variant), where $k$ is the number of unsatisfied edges and $|\\Sigma|$ is the size of the alphabet. As a consequence, we show that one can in polynomial time solve instances of Unique Games where the number of edges allowed not to be satisfied is upper bounded by $O(\\sqrt{\\log n})$ to optimality, which improves over the trivial $O(1)$ upper bound. We prove that the Steiner Cut problem can be solved in $2^{O(k^2\\log k)}n^4\\log n$ deterministic time and $\\tilde{O}(2^{O(k^2\\log k)}n^2)$ randomized time, where $k$ is the size of the cutset. This result improves the double exponential running time of the recent work of Kawarabayashi and Thorup presented at FOCS'11. We show how to combine considering \u201ccut\u201d and \u201cuncut\u201d constraints at the same time. More precisely, we define a robust problem, Node Multiway Cut-Uncut, that can serve as an abstraction of introducing uncut constraints and show that it admits an algorithm running in $2^{O(k^2\\log k)}n^4\\log n$ deterministic time, where $k$ is the size of the cutset. To the best of our knowledge, the only known way of tackling uncut constraints was via the approach of Marx, O'Sullivan, and Razgon [ACM Trans. Algorithms, 9 (2013), 30], which yields algorithms with double exponential running time. An interesting aspect of our algorithms is that they can handle positive real weights.<\/jats:p>","DOI":"10.1137\/15m1032077","type":"journal-article","created":{"date-parts":[[2016,7,6]],"date-time":"2016-07-06T11:19:20Z","timestamp":1467803960000},"page":"1171-1229","source":"Crossref","is-referenced-by-count":44,"title":["Designing FPT Algorithms for Cut Problems Using Randomized Contractions"],"prefix":"10.1137","volume":"45","author":[{"given":"Rajesh","family":"Chitnis","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Marek","family":"Cygan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"MohammadTaghi","family":"Hajiaghayi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Marcin","family":"Pilipczuk","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Micha\u0142","family":"Pilipczuk","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2016,7,6]]},"reference":[{"key":"atypb1","doi-asserted-by":"crossref","unstructured":"A. Agarwal, N. Alon, and M. Charikar,\n                      Improved approximation for directed cut problems\n                      , in Proceedings of STOC'07, 2007, pp. 671-680.","DOI":"10.1145\/1250790.1250888"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1145\/210332.210337"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1145\/2775105"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480196305124"},{"key":"atypb5","doi-asserted-by":"crossref","unstructured":"H. L. Bodlaender, F. V. Fomin, D. Lokshtanov, E. Penninkx, S. Saurabh, and D. M. Thilikos,\n                      (Meta) kernelization\n                      , in Proceedings of FOCS'09, 2009, pp. 629-638.","DOI":"10.1109\/FOCS.2009.46"},{"key":"atypb6","doi-asserted-by":"crossref","unstructured":"N. Bousquet, J. Daligault, and S. Thomass\u00e9,\n                      Multicut is FPT\n                      , in Proceedings of STOC'11, 2011, pp. 459-468.","DOI":"10.1145\/1993636.1993698"},{"key":"atypb7","unstructured":"K. Bringmann, D. Hermelin, M. Mnich, and E. J. van Leeuwen,\n                      Parameterized complexity dichotomy for Steiner multicut\n                      , in Proceedings of the 32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015, 2015, Garching, Germany, E. W. Mayr and N. Ollinger, eds., LIPIcs 30, Schloss Dagstuhl, Leibniz-Zentrum fuer Informatik, 2015, pp. 157-170, doi:10.4230\/LIPIcs.STACS.2015.157."},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1145\/1541885.1541893"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480104445095"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-007-9130-6"},{"key":"atypb11","first-page":"55","author":"Chen J.","year":"2008","journal-title":"J. ACM"},{"key":"atypb12","first-page":"460","author":"Chitnis R. H.","year":"2012","journal-title":"NJ"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1145\/2700209"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1137\/12086217X"},{"key":"atypb15","doi-asserted-by":"crossref","unstructured":"M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh,\n                      Parameterized Algorithms\n                      , Springer, New York, 2015, doi:10.1007\/978-3-319-21275-3.","DOI":"10.1007\/978-3-319-21275-3"},{"key":"atypb16","doi-asserted-by":"crossref","unstructured":"M. Cygan, D. Lokshtanov, M. Pilipczuk, M. Pilipczuk, and S. Saurabh,\n                      Minimum bisection is fixed parameter tractable\n                      , in Proceedings of the Symposium on Theory of Computing, STOC 2014, New York, 2014, D. B. Shmoys, ed., ACM, 2014, pp. 323-332, doi:10.1145\/2591796.2591852.","DOI":"10.1145\/2591796.2591852"},{"key":"atypb17","doi-asserted-by":"crossref","unstructured":"M. Cygan, M. Pilipczuk, and M. Pilipczuk,\n                      On group feedback vertex set parameterized by the size of the cutset\n                      , in Proceedings of WG'12, 2012, pp. 194-205.","DOI":"10.1007\/978-3-642-34611-8_21"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1145\/2462896.2462899"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1137\/110843071"},{"key":"atypb20","doi-asserted-by":"crossref","unstructured":"R. G. Downey and M. R. Fellows,\n                      Parameterized Complexity\n                      , Springer, New York, 1999.","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"atypb21","doi-asserted-by":"crossref","unstructured":"R. G. Downey and M. R. Fellows,\n                      Fundamentals of Parameterized Complexity\n                      , Texts in Comput. Sci., Springer, New York, 2013, doi:10.1007\/978-1-4471-5559-1.","DOI":"10.1007\/978-1-4471-5559-1"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009191"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539798340047"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.09.065"},{"key":"atypb25","unstructured":"J. Flum and M. Grohe,\n                      Parameterized Complexity Theory\n                      , Texts in Theoret. Comput. Sci. EATCS Ser., Springer, New York 2006, http:\/\/www.worldcat.org\/isbn\/3540299521."},{"key":"atypb26","doi-asserted-by":"crossref","unstructured":"F. V. Fomin, D. Lokshtanov, S. Saurabh, and D. M. Thilikos,\n                      Linear kernels for (connected) dominating set on H-minor-free graphs\n                      , in Proceedings of SODA'12, 2012, pp. 82-93.","DOI":"10.1137\/1.9781611973099.7"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793243016"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1007\/BF02523685"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1016\/S0196-6774(03)00111-1"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(86)90079-X"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1137\/120892234"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1016\/j.disopt.2010.05.003"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1016\/j.disopt.2010.08.003"},{"key":"atypb34","doi-asserted-by":"crossref","unstructured":"Y. Iwata, M. Wahlstr\u00f6m, and Y. Yoshida,\n                      Half-Integrality, LP-Branching and FPT Algorithms\n                      , arXiv:1310.2841, 2013.","DOI":"10.1137\/1.9781611973402.128"},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1145\/331605.331608"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1030.0086"},{"key":"atypb37","doi-asserted-by":"crossref","unstructured":"K. Kawarabayashi and M. Thorup,\n                      The minimum k-way cut of bounded size is fixed-parameter tractable\n                      , in Proceedings of FOCS'11, 2011, pp. 160-169.","DOI":"10.1109\/FOCS.2011.53"},{"key":"atypb38","doi-asserted-by":"crossref","unstructured":"S. Khot,\n                      On the power of unique\n                      2\n                      -prover\n                      1\n                      -round games\n                      , in Proceedings of STOC'02, 2002, pp. 767-775.","DOI":"10.1145\/509907.510017"},{"key":"atypb39","first-page":"99","author":"Khot S.","year":"2010","journal-title":"Proceedings of the IEEE Conference on Computational Complexity"},{"key":"atypb40","doi-asserted-by":"publisher","DOI":"10.1137\/120904202"},{"key":"atypb41","unstructured":"S. Kratsch and M. Sorge,\n                      On kernelization and approximation for the vector connectivity problem\n                      , in Proceedings of the 10th International Symposium on Parameterized and Exact Computation, IPEC 2015, Patras, Greece, T. Husfeldt and I. A. Kanj, eds., of LIPIcs 43, Schloss Dagstuhl Leibniz-Zentrum fuer Informatik, 2015, pp. 377-388, doi:10.4230\/LIPIcs.IPEC.2015.377."},{"key":"atypb42","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2012.10.016"},{"key":"atypb43","doi-asserted-by":"publisher","DOI":"10.1145\/2566616"},{"key":"atypb44","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.10.007"},{"key":"atypb45","doi-asserted-by":"publisher","DOI":"10.1145\/2500119"},{"key":"atypb46","doi-asserted-by":"publisher","DOI":"10.1137\/110855247"},{"key":"atypb47","doi-asserted-by":"publisher","DOI":"10.1007\/BF01758778"},{"key":"atypb48","unstructured":"J. Naor and Y. Rabani,\n                      Tree packing and approximating k-cuts\n                      , in Proceedings of SODA'01, 2001, pp. 26-27."},{"key":"atypb49","doi-asserted-by":"crossref","unstructured":"M. Naor, L. J. Schulman, and A. Srinivasan,\n                      Splitters and near-optimal derandomization\n                      , in Proceedings of FOCS'95, 1995, pp. 182-191.","DOI":"10.1109\/SFCS.1995.492475"},{"key":"atypb50","unstructured":"N. S. Narayanaswamy, V. Raman, M. S. Ramanujan, and S. Saurabh,\n                      LP can be a cure for parameterized problems\n                      , in Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science, STACS 2012, Paris, France, C. D\u00fcrr and T. Wilke, eds., LIPIcs 14, Schloss Dagstuhl, Leibniz-Zentrum fuer Informatik, 2012, pp. 338-349, doi:10.4230\/LIPIcs.STACS.2012.338."},{"key":"atypb51","first-page":"1167","author":"Pilipczuk M.","year":"2016","journal-title":"SIAM"},{"key":"atypb52","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2007.01.040"},{"key":"atypb53","unstructured":"I. Razgon,\n                      Large Isolating Cuts Shrink the Multiway Cut\n                      , CoRR abs\/1104.5361, 2011."},{"key":"atypb54","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2009.04.002"},{"key":"atypb55","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2003.10.009"},{"key":"atypb56","doi-asserted-by":"publisher","DOI":"10.1007\/BF01200760"},{"key":"atypb57","doi-asserted-by":"crossref","unstructured":"M. Wahlstr\u00f6m,\n                      Half-integrality, LP-branching and FPT algorithms\n                      , in Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, OR, C. Chekuri, ed., SIAM, 2014, pp. 1762-1781, doi:10.1137\/1.9781611973402.128.","DOI":"10.1137\/1.9781611973402.128"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/15M1032077","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:57:16Z","timestamp":1787338636000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/15M1032077"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,1]]},"references-count":57,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2016,1]]}},"alternative-id":["10.1137\/15M1032077"],"URL":"https:\/\/doi.org\/10.1137\/15m1032077","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,1]]}}}