{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,13]],"date-time":"2026-03-13T20:20:21Z","timestamp":1773433221375,"version":"3.50.1"},"reference-count":42,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2022,1,30]],"date-time":"2022-01-30T00:00:00Z","timestamp":1643500800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,1,30]],"date-time":"2022-01-30T00:00:00Z","timestamp":1643500800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"University of Bergen"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2022,5]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The two weighted graph problems <jats:sc>Node Multiway Cut<\/jats:sc> (NMC) and <jats:sc>Subset Feedback Vertex Set<\/jats:sc> (SFVS) both ask for a vertex set of minimum total weight, that for NMC disconnects a given set of terminals, and for SFVS intersects all cycles containing a vertex of a given set. We design a meta-algorithm that allows to solve both problems in time <jats:inline-formula><jats:alternatives><jats:tex-math>$$2^{O(rw^3)}\\cdot n^{4}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:msup>\n                      <mml:mn>2<\/mml:mn>\n                      <mml:mrow>\n                        <mml:mi>O<\/mml:mi>\n                        <mml:mo>(<\/mml:mo>\n                        <mml:mi>r<\/mml:mi>\n                        <mml:msup>\n                          <mml:mi>w<\/mml:mi>\n                          <mml:mn>3<\/mml:mn>\n                        <\/mml:msup>\n                        <mml:mo>)<\/mml:mo>\n                      <\/mml:mrow>\n                    <\/mml:msup>\n                    <mml:mo>\u00b7<\/mml:mo>\n                    <mml:msup>\n                      <mml:mi>n<\/mml:mi>\n                      <mml:mn>4<\/mml:mn>\n                    <\/mml:msup>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, <jats:inline-formula><jats:alternatives><jats:tex-math>$$2^{O(q^2\\log (q))}\\cdot n^{4}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:msup>\n                      <mml:mn>2<\/mml:mn>\n                      <mml:mrow>\n                        <mml:mi>O<\/mml:mi>\n                        <mml:mo>(<\/mml:mo>\n                        <mml:msup>\n                          <mml:mi>q<\/mml:mi>\n                          <mml:mn>2<\/mml:mn>\n                        <\/mml:msup>\n                        <mml:mo>log<\/mml:mo>\n                        <mml:mrow>\n                          <mml:mo>(<\/mml:mo>\n                          <mml:mi>q<\/mml:mi>\n                          <mml:mo>)<\/mml:mo>\n                        <\/mml:mrow>\n                        <mml:mo>)<\/mml:mo>\n                      <\/mml:mrow>\n                    <\/mml:msup>\n                    <mml:mo>\u00b7<\/mml:mo>\n                    <mml:msup>\n                      <mml:mi>n<\/mml:mi>\n                      <mml:mn>4<\/mml:mn>\n                    <\/mml:msup>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, and <jats:inline-formula><jats:alternatives><jats:tex-math>$$n^{O(k^2)}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msup>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mrow>\n                      <mml:mi>O<\/mml:mi>\n                      <mml:mo>(<\/mml:mo>\n                      <mml:msup>\n                        <mml:mi>k<\/mml:mi>\n                        <mml:mn>2<\/mml:mn>\n                      <\/mml:msup>\n                      <mml:mo>)<\/mml:mo>\n                    <\/mml:mrow>\n                  <\/mml:msup>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> where <jats:italic>rw<\/jats:italic> is the rank-width, <jats:italic>q<\/jats:italic> the <jats:inline-formula><jats:alternatives><jats:tex-math>$${\\mathbb {Q}}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>Q<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-rank-width, and <jats:italic>k<\/jats:italic> the mim-width of a given decomposition. This answers in the affirmative an open question raised by Jaffke et\u00a0al. (Algorithmica 82(1):118\u2013145, 2020) concerning an  algorithm for SFVS parameterized by mim-width. By a unified algorithm, this solves both problems in polynomial-time on the following graph classes: <jats:sc>Interval<\/jats:sc>, <jats:sc>Permutation<\/jats:sc>, and <jats:sc>Bi-Interval<\/jats:sc> graphs, <jats:sc>Circular Arc<\/jats:sc> and <jats:sc>Circular Permutation<\/jats:sc> graphs, <jats:sc>Convex<\/jats:sc> graphs, <jats:italic>k<\/jats:italic>-<jats:sc>Polygon<\/jats:sc>, <jats:sc>Dilworth<\/jats:sc>-<jats:italic>k<\/jats:italic> and <jats:sc>Co-<\/jats:sc><jats:italic>k<\/jats:italic>-<jats:sc>Degenerate<\/jats:sc> graphs for fixed <jats:italic>k<\/jats:italic>; and also on <jats:sc>Leaf Power<\/jats:sc> graphs if a leaf root is given as input, on  <jats:italic>H<\/jats:italic><jats:sc>-Graphs<\/jats:sc> for fixed <jats:italic>H<\/jats:italic> if an <jats:italic>H<\/jats:italic>-representation is given as input, and on arbitrary powers of graphs in all the above classes. Prior to our results, only SFVS was known to be tractable restricted only on <jats:sc>Interval<\/jats:sc> and <jats:sc>Permutation<\/jats:sc> graphs, whereas all other results are new. \n<\/jats:p>","DOI":"10.1007\/s00453-022-00936-w","type":"journal-article","created":{"date-parts":[[2022,1,30]],"date-time":"2022-01-30T12:02:32Z","timestamp":1643544152000},"page":"1385-1417","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["Node Multiway Cut and Subset Feedback Vertex Set on Graphs of Bounded Mim-Width"],"prefix":"10.1007","volume":"84","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6270-3663","authenticated-orcid":false,"given":"Benjamin","family":"Bergougnoux","sequence":"first","affiliation":[]},{"given":"Charis","family":"Papadopoulos","sequence":"additional","affiliation":[]},{"given":"Jan Arne","family":"Telle","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,1,30]]},"reference":[{"key":"936_CR1","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1016\/j.tcs.2013.01.011","volume":"511","author":"R Belmonte","year":"2013","unstructured":"Belmonte, R., Vatshelle, M.: Graph classes with structured neighborhoods and algorithmic applications. Theor. Comput. Sci. 511, 54\u201365 (2013)","journal-title":"Theor. Comput. Sci."},{"key":"936_CR2","unstructured":"Bergougnoux, B., Bonnet, \u00c9., Brettell, N., Kwon, O.: Close relatives of feedback vertex set without single-exponential algorithms parameterized by treewidth. In: 15th International Symposium on Parameterized and Exact Computation, IPEC 2020, December 14\u201318, 2020, Hong Kong, China (Virtual Conference), pp. 3:1\u20133:17 (2020)"},{"key":"936_CR3","unstructured":"Bergougnoux, B., Kant\u00e9, M.M.: More applications of the d-neighbor equivalence: connectivity and acyclicity constraints. In: 27th Annual European Symposium on Algorithms, ESA 2019, September 9\u201311, 2019, Munich\/Garching, Germany, pp. 17:1\u201317:14 (2019)"},{"key":"936_CR4","doi-asserted-by":"crossref","unstructured":"Bodlaender, H.L.: Treewidth: characterizations, applications, and computations. In: Graph-Theoretic Concepts in Computer Science, 32nd International Workshop, WG 2006, Bergen, Norway, June 22\u201324, 2006, Revised Papers, pp. 1\u201314 (2006)","DOI":"10.1007\/11917496_1"},{"key":"936_CR5","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1016\/j.ic.2014.12.008","volume":"243","author":"HL Bodlaender","year":"2015","unstructured":"Bodlaender, H.L., Cygan, M., Kratsch, S., Nederlof, J.: Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth. Inform. Comput. 243, 86\u2013111 (2015)","journal-title":"Inform. Comput."},{"issue":"10","key":"936_CR6","doi-asserted-by":"publisher","first-page":"3890","DOI":"10.1007\/s00453-019-00579-4","volume":"81","author":"\u00c9 Bonnet","year":"2019","unstructured":"Bonnet, \u00c9., Brettell, N., Kwon, O., Marx, D.: Generalized feedback vertex set problems on bounded-treewidth graphs: chordality is the key to single-exponential parameterized algorithms. Algorithmica 81(10), 3890\u20133935 (2019)","journal-title":"Algorithmica"},{"key":"936_CR7","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1016\/j.tcs.2013.01.009","volume":"511","author":"B-M Bui-Xuan","year":"2013","unstructured":"Bui-Xuan, B.-M., Telle, J.A., Vatshelle, M.: Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems. Theor. Comput. Sci. 511, 66\u201376 (2013)","journal-title":"Theor. Comput. Sci."},{"key":"936_CR8","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-30162-4_253","volume-title":"Multiway Cut","author":"G Calinescu","year":"2008","unstructured":"Calinescu, G.: Multiway Cut. Springer, Berlin (2008)"},{"key":"936_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00453-007-9130-6","volume":"55","author":"J Chen","year":"2009","unstructured":"Chen, J., Liu, Y., Lu, S.: An improved parameterized algorithm for the minimum node multiway cut problem. Algorithmica 55, 1\u201313 (2009)","journal-title":"Algorithmica"},{"key":"936_CR10","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1016\/j.jcss.2017.04.003","volume":"88","author":"RH Chitnis","year":"2017","unstructured":"Chitnis, R.H., Fomin, F.V., Lokshtanov, D., Misra, P., Ramanujan, M.S., Saurabh, S.: Faster exact algorithms for some terminal set problems. J. Comput. Syst. Sci. 88, 195\u2013207 (2017)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"936_CR11","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/0166-218X(88)90086-8","volume":"22","author":"DG Corneil","year":"1988","unstructured":"Corneil, D.G., Fonlupt, J.: The complexity of generalized clique covering. Discrete Appl. Math. 22(2), 109\u2013118 (1988)","journal-title":"Discrete Appl. Math."},{"issue":"2","key":"936_CR12","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/s002249910009","volume":"33","author":"B Courcelle","year":"2000","unstructured":"Courcelle, B., Makowsky, J.A., Rotics, U.: Linear time solvable optimization problems on graphs of bounded clique-width. Theory Comput. Syst. 33(2), 125\u2013150 (2000)","journal-title":"Theory Comput. Syst."},{"issue":"1\u20133","key":"936_CR13","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/S0166-218X(99)00184-5","volume":"101","author":"B Courcelle","year":"2000","unstructured":"Courcelle, B., Olariu, S.: Upper bounds to the clique width of graphs. Discrete Appl. Math. 101(1\u20133), 77\u2013114 (2000)","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"936_CR14","doi-asserted-by":"publisher","first-page":"3:1","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:1-3:11 (2013)","journal-title":"TOCT"},{"issue":"1","key":"936_CR15","doi-asserted-by":"publisher","first-page":"290","DOI":"10.1137\/110843071","volume":"27","author":"M Cygan","year":"2013","unstructured":"Cygan, M., Pilipczuk, M., Pilipczuk, M., Wojtaszczyk, J.O.: Subset feedback vertex set is fixed-parameter tractable. SIAM J. Discrete Math. 27(1), 290\u2013309 (2013)","journal-title":"SIAM J. Discrete Math."},{"issue":"4","key":"936_CR16","doi-asserted-by":"publisher","first-page":"864","DOI":"10.1137\/S0097539792225297","volume":"23","author":"E Dahlhaus","year":"1994","unstructured":"Dahlhaus, E., Johnson, D.S., Papadimitriou, C.H., Seymour, P.D., Yannakakis, M.: The complexity of multiterminal cuts. SIAM J. Comput. 23(4), 864\u2013894 (1994)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"936_CR17","doi-asserted-by":"publisher","first-page":"1231","DOI":"10.1137\/S0097539798340047","volume":"30","author":"G Even","year":"2000","unstructured":"Even, G., Naor, J., Zosin, L.: An 8-approximation algorithm for the subset feedback vertex set problem. SIAM J. Comput. 30(4), 1231\u20131252 (2000)","journal-title":"SIAM J. Comput."},{"key":"936_CR18","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Gaspers, S., Lokshtanov, D., Saurabh, S.: Exact algorithms via monotone local search. In: Proceedings of STOC 2016, pp. 764\u2013775 (2016)","DOI":"10.1145\/2897518.2897551"},{"key":"936_CR19","unstructured":"Fomin, F.V., Golovach, P.A., Raymond, J.: On the tractability of optimization problems on h-graphs. In: 26th Annual European Symposium on Algorithms, ESA 2018, August 20\u201322, 2018, Helsinki, Finland, pp. 30:1\u201330:14 (2018)"},{"issue":"1","key":"936_CR20","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1007\/s00453-012-9731-6","volume":"69","author":"FV Fomin","year":"2014","unstructured":"Fomin, F.V., Heggernes, P., Kratsch, D., Papadopoulos, C., Villanger, Y.: Enumerating minimal subset feedback vertex sets. Algorithmica 69(1), 216\u2013231 (2014)","journal-title":"Algorithmica"},{"issue":"1","key":"936_CR21","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":"2","key":"936_CR22","doi-asserted-by":"publisher","first-page":"714","DOI":"10.1007\/s00453-017-0289-1","volume":"80","author":"PA Golovach","year":"2018","unstructured":"Golovach, P.A., Heggernes, P., Kant\u00e9, M.M., Kratsch, D., S\u00e6ther, S.H., Villanger, Y.: Output-polynomial enumeration on graphs of bounded (local) linear mim-width. Algorithmica 80(2), 714\u2013741 (2018)","journal-title":"Algorithmica"},{"key":"936_CR23","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1016\/j.jda.2013.09.005","volume":"26","author":"PA Golovach","year":"2014","unstructured":"Golovach, P.A., Heggernes, P., Kratsch, D., Saei, R.: Subset feedback vertex sets in chordal graphs. J. Discrete Algorithms 26, 7\u201315 (2014)","journal-title":"J. Discrete Algorithms"},{"issue":"3","key":"936_CR24","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1142\/S0129054100000260","volume":"11","author":"MC Golumbic","year":"2000","unstructured":"Golumbic, M.C., Rotics, U.: On the clique-width of some perfect graph classes. Int. J. Found. Comput. Sci. 11(3), 423\u2013443 (2000)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"936_CR25","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1007\/s00224-017-9805-6","volume":"62","author":"EC Hols","year":"2018","unstructured":"Hols, E.C., Kratsch, S.: A randomized polynomial kernel for subset feedback vertex set. Theory Comput. Syst. 62, 54\u201365 (2018)","journal-title":"Theory Comput. Syst."},{"key":"936_CR26","unstructured":"Jacob, H., Bellitto, T., Defrain, O., Pilipczuk, M.: Close Relatives (Of Feedback Vertex Set), Revisited. In: Golovach, P.A., Zehavi, M. (eds.) 16th International Symposium on Parameterized and Exact Computation (IPEC 2021). Leibniz International Proceedings in Informatics (LIPIcs). vol. 214, pp. 21:1\u201321:15. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany (2021)"},{"key":"936_CR27","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1016\/j.tcs.2019.09.012","volume":"796","author":"L Jaffke","year":"2019","unstructured":"Jaffke, L., Kwon, O., Str\u00f8mme, T.J.F., Telle, J.A.: Mim-width III: graph powers and generalized distance domination problems. Theor. Comput. Sci. 796, 216\u2013236 (2019)","journal-title":"Theor. Comput. Sci."},{"key":"936_CR28","unstructured":"Jaffke, L., Kwon, O., Telle, J.A.: A unified polynomial-time algorithm for feedback vertex set on graphs of bounded mim-width. In: 35th Symposium on Theoretical Aspects of Computer Science, STACS 2018, February 28 to March 3, 2018, Caen, France, pp. 42:1\u201342:14 (2018)"},{"issue":"1","key":"936_CR29","doi-asserted-by":"publisher","first-page":"118","DOI":"10.1007\/s00453-019-00607-3","volume":"82","author":"L Jaffke","year":"2020","unstructured":"Jaffke, L., Kwon, O., Telle, J.A.: Mim-width II. The feedback vertex set problem. Algorithmica 82(1), 118\u2013145 (2020)","journal-title":"Algorithmica"},{"issue":"4","key":"936_CR30","doi-asserted-by":"publisher","first-page":"1020","DOI":"10.1016\/j.jctb.2011.12.001","volume":"102","author":"K Kawarabayashi","year":"2012","unstructured":"Kawarabayashi, K., Kobayashi, Y.: Fixed-parameter tractability for the subset feedback set problem and the s-cycle packing problem. J. Combin. Theory Ser. B 102(4), 1020\u20131034 (2012)","journal-title":"J. Combin. Theory Ser. B"},{"key":"936_CR31","volume-title":"Boolean Matrix Theory and Applications","author":"KH Kim","year":"1982","unstructured":"Kim, K.H.: Boolean Matrix Theory and Applications, vol. 70. Dekker, New York (1982)"},{"issue":"10","key":"936_CR32","doi-asserted-by":"publisher","first-page":"1936","DOI":"10.1016\/j.dam.2007.10.006","volume":"156","author":"D Kratsch","year":"2008","unstructured":"Kratsch, D., M\u00fcller, H., Todinca, I.: Feedback vertex set on AT-free graphs. Discrete Appl. Math. 156(10), 1936\u20131947 (2008)","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"936_CR33","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1016\/j.jctb.2005.03.003","volume":"95","author":"S-I Oum","year":"2005","unstructured":"Oum, S.-I.: Rank-width and vertex-minors. J. Combin. Theory Ser. B 95(1), 79\u2013100 (2005)","journal-title":"J. Combin. Theory Ser. B"},{"key":"936_CR34","doi-asserted-by":"crossref","unstructured":"Oum, S.-I.: Approximating rank-width and clique-width quickly. ACM Trans. Algorithms, 5(1):Art. 10, 20 (2009)","DOI":"10.1145\/1435375.1435385"},{"key":"936_CR35","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1016\/j.tcs.2014.03.024","volume":"535","author":"S-I Oum","year":"2014","unstructured":"Oum, S.-I., S\u00e6ther, S.H., Vatshelle, M.: Faster algorithms for vertex partitioning problems parameterized by clique-width. Theor. Comput. Sci. 535, 16\u201324 (2014)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"936_CR36","doi-asserted-by":"publisher","first-page":"514","DOI":"10.1016\/j.jctb.2005.10.006","volume":"96","author":"S-I Oum","year":"2006","unstructured":"Oum, S.-I., Seymour, P.: Approximating clique-width and branch-width. J. Combin. Theory Ser. B 96(4), 514\u2013528 (2006)","journal-title":"J. Combin. Theory Ser. B"},{"key":"936_CR37","doi-asserted-by":"publisher","first-page":"204","DOI":"10.1016\/j.dam.2018.11.017","volume":"258","author":"C Papadopoulos","year":"2019","unstructured":"Papadopoulos, C., Tzimas, S.: Polynomial-time algorithms for the subset feedback vertex set problem on interval graphs and permutation graphs. Discrete Appl. Math. 258, 204\u2013221 (2019)","journal-title":"Discrete Appl. Math."},{"key":"936_CR38","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1016\/j.tcs.2020.01.029","volume":"814","author":"C Papadopoulos","year":"2020","unstructured":"Papadopoulos, C., Tzimas, S.: Subset feedback vertex set on graphs of bounded independent set size. Theor. Comput. Sci. 814, 177\u2013188 (2020)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"936_CR39","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1016\/0095-8956(91)90061-N","volume":"52","author":"N Robertson","year":"1991","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. x. Obstructions to tree-decomposition. J. Comb. Theory Ser. B 52(2), 153\u2013190 (1991)","journal-title":"J. Comb. Theory Ser. B"},{"key":"936_CR40","doi-asserted-by":"publisher","first-page":"120","DOI":"10.1016\/j.tcs.2015.11.039","volume":"615","author":"SH S\u00e6ther","year":"2016","unstructured":"S\u00e6ther, S.H., Vatshelle, M.: Hardness of computing width parameters based on branch decompositions over the vertex set. Theor. Comput. Sci. 615, 120\u2013125 (2016)","journal-title":"Theor. Comput. Sci."},{"key":"936_CR41","unstructured":"Vatshelle, M.: New width parameters of graphs. PhD thesis, University of Bergen, Bergen, Norway (2012)"},{"issue":"11","key":"936_CR42","doi-asserted-by":"publisher","first-page":"173","DOI":"10.3390\/a11110173","volume":"11","author":"K Yamazaki","year":"2018","unstructured":"Yamazaki, K.: Inapproximability of rank, clique, boolean, and maximum induced matching-widths under small set expansion hypothesis. Algorithms 11(11), 173 (2018)","journal-title":"Algorithms"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-00936-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-022-00936-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-00936-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,4,28]],"date-time":"2022-04-28T05:05:00Z","timestamp":1651122300000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-022-00936-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1,30]]},"references-count":42,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2022,5]]}},"alternative-id":["936"],"URL":"https:\/\/doi.org\/10.1007\/s00453-022-00936-w","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,1,30]]},"assertion":[{"value":"24 September 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 January 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 January 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}