{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:42:00Z","timestamp":1740109320420,"version":"3.37.3"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"9","license":[{"start":{"date-parts":[[2023,3,11]],"date-time":"2023-03-11T00:00:00Z","timestamp":1678492800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,3,11]],"date-time":"2023-03-11T00:00:00Z","timestamp":1678492800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2023,9]]},"abstract":"Abstract<\/jats:title>Paths $$P^1,\\ldots ,P^k$$<\/jats:tex-math>\n \n \n P<\/mml:mi>\n 1<\/mml:mn>\n <\/mml:msup>\n ,<\/mml:mo>\n \u2026<\/mml:mo>\n ,<\/mml:mo>\n \n P<\/mml:mi>\n k<\/mml:mi>\n <\/mml:msup>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> in a graph $$G=(V,E)$$<\/jats:tex-math>\n \n G<\/mml:mi>\n =<\/mml:mo>\n (<\/mml:mo>\n V<\/mml:mi>\n ,<\/mml:mo>\n E<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> are mutually induced if any two distinct $$P^i$$<\/jats:tex-math>\n \n P<\/mml:mi>\n i<\/mml:mi>\n <\/mml:msup>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and $$P^j$$<\/jats:tex-math>\n \n P<\/mml:mi>\n j<\/mml:mi>\n <\/mml:msup>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> have neither common vertices nor adjacent vertices. The Induced Disjoint Paths<\/jats:sc> problem is to decide if a graph\u00a0G<\/jats:italic> with k<\/jats:italic> pairs of specified vertices $$(s_i,t_i)$$<\/jats:tex-math>\n \n (<\/mml:mo>\n \n s<\/mml:mi>\n i<\/mml:mi>\n <\/mml:msub>\n ,<\/mml:mo>\n \n t<\/mml:mi>\n i<\/mml:mi>\n <\/mml:msub>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> contains k<\/jats:italic> mutually induced paths\u00a0$$P^i$$<\/jats:tex-math>\n \n P<\/mml:mi>\n i<\/mml:mi>\n <\/mml:msup>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> such that each $$P^i$$<\/jats:tex-math>\n \n P<\/mml:mi>\n i<\/mml:mi>\n <\/mml:msup>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> starts from $$s_i$$<\/jats:tex-math>\n \n s<\/mml:mi>\n i<\/mml:mi>\n <\/mml:msub>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and ends at $$t_i$$<\/jats:tex-math>\n \n t<\/mml:mi>\n i<\/mml:mi>\n <\/mml:msub>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. This is a classical graph problem that is -complete even for $$k=2$$<\/jats:tex-math>\n \n k<\/mml:mi>\n =<\/mml:mo>\n 2<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. We introduce a natural generalization, Induced Disjoint Connected Subgraphs<\/jats:sc>: instead of connecting pairs of terminals, we must connect sets of terminals. We give almost-complete dichotomies of the computational complexity of both problems for H<\/jats:italic>-free graphs, that is, graphs that do not contain some fixed graph H<\/jats:italic> as an induced subgraph. Finally, we give a complete classification of the complexity of the second problem if the number\u00a0k<\/jats:italic> of terminal sets is fixed, that is, not part of the input.\n<\/jats:p>","DOI":"10.1007\/s00453-023-01109-z","type":"journal-article","created":{"date-parts":[[2023,3,26]],"date-time":"2023-03-26T21:50:55Z","timestamp":1679867455000},"page":"2580-2604","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Induced Disjoint Paths and Connected Subgraphs for H-Free Graphs"],"prefix":"10.1007","volume":"85","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4642-8614","authenticated-orcid":false,"given":"Barnaby","family":"Martin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5945-9287","authenticated-orcid":false,"given":"Dani\u00ebl","family":"Paulusma","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0797-0512","authenticated-orcid":false,"given":"Siani","family":"Smith","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5240-7257","authenticated-orcid":false,"given":"Erik Jan","family":"van Leeuwen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,3,11]]},"reference":[{"key":"1109_CR1","first-page":"501","volume":"69","author":"R Belmonte","year":"2014","unstructured":"Belmonte, R., Golovach, P.A., Heggernes, P., van\u2019t Hof, P., Kaminski, M., Paulusma, D.: Detecting fixed patterns in chordal graphs in polynomial time. Algorithmica 69, 501\u2013521 (2014)","journal-title":"Algorithmica"},{"key":"1109_CR2","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/0012-365X(91)90098-M","volume":"90","author":"D Bienstock","year":"1991","unstructured":"Bienstock, D.: On the complexity of testing for odd holes and induced odd paths. Discrete Math. 90, 85\u201392 (1991)","journal-title":"Discrete Math."},{"key":"1109_CR3","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1016\/j.tcs.2007.09.031","volume":"389","author":"A Brandst\u00e4dt","year":"2007","unstructured":"Brandst\u00e4dt, A., Ho\u00e0ng, C.T.: On clique separators, nearly chordal graphs, and the maximum weight stable set problem. Theoret. Comput. Sci. 389, 295\u2013306 (2007)","journal-title":"Theoret. Comput. Sci."},{"key":"1109_CR4","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1007\/s00453-015-9989-6","volume":"75","author":"E Camby","year":"2016","unstructured":"Camby, E., Schaudt, O.: A new characterization of $${P}_k$$-free graphs. Algorithmica 75, 205\u2013217 (2016)","journal-title":"Algorithmica"},{"key":"1109_CR5","first-page":"1","volume":"89","author":"MR Fellows","year":"1989","unstructured":"Fellows, M.R.: The Robertson-Seymour theorems: a survey of applications. Proc. AMS-IMS-SIAM Jt. Summer Res. Conf. Contemp. Math. 89, 1\u201318 (1989)","journal-title":"Proc. AMS-IMS-SIAM Jt. Summer Res. Conf. Contemp. Math."},{"key":"1109_CR6","doi-asserted-by":"publisher","first-page":"499","DOI":"10.1007\/s00453-010-9468-z","volume":"62","author":"J Fiala","year":"2012","unstructured":"Fiala, J., Kami\u0144ski, M., Lidick\u00fd, B., Paulusma, D.: The $$k$$-in-a-Path problem for claw-free graphs. Algorithmica 62, 499\u2013519 (2012)","journal-title":"Algorithmica"},{"key":"1109_CR7","first-page":"613","volume":"2020","author":"P Gartland","year":"2020","unstructured":"Gartland, P., Lokshtanov, D.: Independent set on $${P}_k$$-free graphs in quasi-polynomial time. Proc. FOCS 2020, 613\u2013624 (2020)","journal-title":"Proc. FOCS"},{"key":"1109_CR8","first-page":"330","volume":"2021","author":"P Gartland","year":"2021","unstructured":"Gartland, P., Lokshtanov, D., Pilipczuk, M., Pilipczuk, M., Rz\u0105\u017cewski, P.: Finding large induced sparse subgraphs in $${C}_{>t}$$-free graphs in quasipolynomial time. Proc. STOC 2021, 330\u2013341 (2021)","journal-title":"Proc. STOC"},{"key":"1109_CR9","doi-asserted-by":"publisher","first-page":"348","DOI":"10.1137\/140963200","volume":"29","author":"PA Golovach","year":"2015","unstructured":"Golovach, P.A., Paulusma, D., van Leeuwen, E.J.: Induced disjoint paths in claw-free graphs. SIAM J. Discrete Math. 29, 348\u2013375 (2015)","journal-title":"SIAM J. Discrete Math."},{"key":"1109_CR10","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1016\/j.tcs.2016.06.003","volume":"640","author":"PA Golovach","year":"2016","unstructured":"Golovach, P.A., Paulusma, D., van Leeuwen, E.J.: Induced disjoint paths in circular-arc graphs in linear time. Theor. Comput. Sci. 640, 70\u201383 (2016)","journal-title":"Theor. Comput. Sci."},{"key":"1109_CR11","doi-asserted-by":"publisher","first-page":"170","DOI":"10.1016\/j.jcss.2021.10.003","volume":"124","author":"PA Golovach","year":"2022","unstructured":"Golovach, P.A., Paulusma, D., van Leeuwen, E.J.: Induced disjoint paths in AT-free graphs. J. Comput. Syst. Sci. 124, 170\u2013191 (2022)","journal-title":"J. Comput. Syst. Sci."},{"key":"1109_CR12","doi-asserted-by":"publisher","first-page":"4:1","DOI":"10.1145\/3414473","volume":"18","author":"A Grzesik","year":"2022","unstructured":"Grzesik, A., Klimosov\u00e1, T., Pilipczuk, M., Pilipczuk, M.: Polynomial-time algorithm for maximum weight independent set on $${P}_6$$-free graphs. ACM Trans. Algorithms 18, 4:1-4:57 (2022)","journal-title":"ACM Trans. Algorithms"},{"key":"1109_CR13","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1016\/j.dam.2019.06.026","volume":"278","author":"L Jaffke","year":"2020","unstructured":"Jaffke, L., Kwon, O., Telle, J.A.: Mim-width I. Induced path problems. Discrete Appl. Math. 278, 153\u2013168 (2020)","journal-title":"Discrete Appl. Math."},{"key":"1109_CR14","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1007\/s00453-019-00601-9","volume":"82","author":"M Johnson","year":"2020","unstructured":"Johnson, M., Paesani, G., Paulusma, D.: Connected vertex cover for $$(s{P}_1+{P}_5)$$-free graphs. Algorithmica 82, 20\u201340 (2020)","journal-title":"Algorithmica"},{"key":"1109_CR15","doi-asserted-by":"publisher","first-page":"670","DOI":"10.1016\/j.jcss.2011.10.004","volume":"78","author":"K Kawarabayashi","year":"2012","unstructured":"Kawarabayashi, K., Kobayashi, Y.: A linear time algorithm for the induced disjoint paths problem in planar graphs. J. Comput. Syst. Sci. 78, 670\u2013680 (2012)","journal-title":"J. Comput. Syst. Sci."},{"key":"1109_CR16","first-page":"22:1","volume":"181","author":"W Kern","year":"2020","unstructured":"Kern, W., Paulusma, D.: Contracting to a longest path in $${H}$$-free graphs. Proc. ISAAC 2020 LIPIcs 181, 22:1-22:18 (2020)","journal-title":"Proc. ISAAC 2020 LIPIcs"},{"key":"1109_CR17","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1016\/j.tcs.2021.10.019","volume":"898","author":"W Kern","year":"2022","unstructured":"Kern, W., Martin, B., Paulusma, D., Smith, S., van Leeuwen, E.J.: Disjoint paths and connected subgraphs for $$H$$-free graphs. Theor. Comput. Sci. 898, 59\u201368 (2022)","journal-title":"Theor. Comput. Sci."},{"key":"1109_CR18","first-page":"1146","volume":"2009","author":"Y Kobayashi","year":"2009","unstructured":"Kobayashi, Y., Kawarabayashi, K.: Algorithms for finding an induced cycle in planar graphs and bounded genus graphs. Proc. SODA 2009, 1146\u20131155 (2009)","journal-title":"Proc. SODA"},{"key":"1109_CR19","doi-asserted-by":"publisher","first-page":"3540","DOI":"10.1016\/j.dam.2009.02.015","volume":"157","author":"B L\u00e9v\u00eaque","year":"2009","unstructured":"L\u00e9v\u00eaque, B., Lin, D.Y., Maffray, F., Trotignon, N.: Detecting induced subgraphs. Discrete Appl. Math. 157, 3540\u20133551 (2009)","journal-title":"Discrete Appl. Math."},{"key":"1109_CR20","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1016\/S0166-218X(97)00020-6","volume":"78","author":"WN Li","year":"1997","unstructured":"Li, W.N.: Two-segmented channel routing is strong NP-complete. Discrete Appl. Math. 78, 291\u2013298 (1997)","journal-title":"Discrete Appl. Math."},{"key":"1109_CR21","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1145\/1061425.1061430","volume":"5","author":"J Lynch","year":"1975","unstructured":"Lynch, J.: The equivalence of theorem proving and the interconnection problem. SIGDA Newsletter 5, 31\u201336 (1975)","journal-title":"SIGDA Newsletter"},{"key":"1109_CR22","first-page":"398","volume":"13453","author":"B Martin","year":"2022","unstructured":"Martin, B., Paulusma, D., Smith, S., van Leeuwen, E.J.: Induced disjoint paths and connected subgraphs for $${H}$$-free graphs. Proc. WG 2022 LNCS 13453, 398\u2013411 (2022)","journal-title":"Proc. WG 2022 LNCS"},{"key":"1109_CR23","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1016\/j.tcs.2022.10.024","volume":"939","author":"B Martin","year":"2023","unstructured":"Martin, B., Paulusma, D., Smith, S., van Leeuwen, E.J.: Few induced disjoint paths for $${H}$$-free graphs. Theor. Comput. Sci. 939, 182\u2013193 (2023)","journal-title":"Theor. Comput. Sci."},{"key":"1109_CR24","doi-asserted-by":"publisher","first-page":"284","DOI":"10.1016\/0095-8956(80)90074-X","volume":"28","author":"GJ Minty","year":"1980","unstructured":"Minty, G.J.: On maximal independent sets of vertices in claw-free graphs. J. Comb. Theory Ser. B 28, 284\u2013304 (1980)","journal-title":"J. Comb. Theory Ser. B"},{"key":"1109_CR25","doi-asserted-by":"publisher","first-page":"2453","DOI":"10.1137\/22M1468864","volume":"36","author":"G Paesani","year":"2022","unstructured":"Paesani, G., Paulusma, D., Rz\u0105\u017cewski, P.: Feedback vertex set and even cycle transversal for $${H}$$-free graphs: finding large block graphs. SIAM J. Discrete Math. 36, 2453\u20132472 (2022)","journal-title":"SIAM J. Discrete Math."},{"key":"1109_CR26","first-page":"204","volume":"2021","author":"M Pilipczuk","year":"2021","unstructured":"Pilipczuk, M., Pilipczuk, M., Rz\u0105\u017cewski, P.: Quasi-polynomial-time algorithm for independent set in $${P}_t$$-free graphs via shrinking the space of induced paths. Proc. SOSA 2021, 204\u2013209 (2021)","journal-title":"Proc. SOSA"},{"key":"1109_CR27","doi-asserted-by":"publisher","first-page":"495","DOI":"10.1016\/j.jctb.2020.06.002","volume":"146","author":"M Radovanovi\u0107","year":"2021","unstructured":"Radovanovi\u0107, M., Trotignon, N., Vus\u0306kovi\u0107, K.: The (theta,wheel)-free graphs Part IV: induced paths and cycles. J. Combin. Theory Ser. B 146, 495\u2013531 (2021)","journal-title":"J. Combin. Theory Ser. B"},{"key":"1109_CR28","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1006\/jctb.1995.1006","volume":"63","author":"N Robertson","year":"1995","unstructured":"Robertson, N., Seymour, P.D.: Graph minors .XIII. The disjoint paths problem. J. Combin. Theory Ser. B 63, 65\u2013110 (1995)","journal-title":"J. Combin. Theory Ser. B"},{"key":"1109_CR29","doi-asserted-by":"crossref","unstructured":"Schaefer, T.J.: The complexity of satisfiability problems. In: STOC, pp. 216\u2013226 (1978)","DOI":"10.1145\/800133.804350"},{"key":"1109_CR30","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/0012-365X(90)90287-R","volume":"29","author":"N Shibi","year":"1980","unstructured":"Shibi, N.: Algorithme de recherche d\u2019un stable de cardinalit\u00e9 maximum dans un graphe sans \u00e9toile. Discrete Math. 29, 53\u201376 (1980)","journal-title":"Discrete Math."},{"key":"1109_CR31","doi-asserted-by":"publisher","first-page":"4834","DOI":"10.1016\/j.tcs.2009.06.028","volume":"410","author":"P van\u2019t Hof","year":"2009","unstructured":"van\u2019t Hof, P., Paulusma, D.: Partitioning graphs into connected parts. Theor. Comput. Sci. 410, 4834\u20134843 (2009)","journal-title":"Theor. Comput. Sci."},{"key":"1109_CR32","doi-asserted-by":"publisher","first-page":"731","DOI":"10.1016\/j.dam.2008.08.025","volume":"158","author":"P van\u2019t Hof","year":"2010","unstructured":"van\u2019t Hof, P., Paulusma, D.: A new characterization of $${P}_6$$-free graphs. Discrete Appl. Math. 158, 731\u2013740 (2010)","journal-title":"Discrete Appl. Math."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-023-01109-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-023-01109-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-023-01109-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,22]],"date-time":"2023-09-22T15:03:26Z","timestamp":1695395006000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-023-01109-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,3,11]]},"references-count":32,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2023,9]]}},"alternative-id":["1109"],"URL":"https:\/\/doi.org\/10.1007\/s00453-023-01109-z","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2023,3,11]]},"assertion":[{"value":"16 July 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 February 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 March 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no competing interests as defined by Springer, or other interests that might be perceived to influence the results and\/or discussion reported in this paper.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}