{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:36:51Z","timestamp":1787323011741,"version":"build-2736575974"},"reference-count":42,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2015,1]]},"abstract":"<jats:p>Paths $P_1,\\ldots,P_k$ in a graph $G=(V,E)$ are said to be mutually induced if for any $1\\leq i&lt;j \\leq k$, $P_i$ and $P_j$ have neither common vertices nor adjacent vertices (except perhaps their end-vertices). The Induced Disjoint Paths problem is to test whether a graph $G$ with $k$ pairs of specified vertices $(s_i,t_i)$ contains $k$ mutually induced paths $P_i$ such that $P_i$ connects $s_i$ and $t_i$ for $i=1,\\ldots,k$. We show that this problem is fixed-parameter tractable for claw-free graphs when parameterized by $k$. Several related problems, such as the $k$-in-a-Path problem, are proved to be fixed-parameter tractable for claw-free graphs as well. We show that an improvement of these results in certain directions is unlikely, for example, by noting that the Induced Disjoint Paths problem cannot have a polynomial kernel for line graphs (a type of claw-free graphs), unless \\sf NP $\\subseteq$ co${\\sf NP}\/$poly. Moreover, the problem becomes \\sf NP-complete, even when $k=2$, for the more general class of $K_{1,4}$-free graphs. Finally, we show that the $n^{O(k)}$-time algorithm of Fiala et al. for testing whether a claw-free graph contains some $k$-vertex graph $H$ as a topological induced minor is essentially optimal by proving that this problem is $\\mathsf{W}$[1]-hard even if $G$ and $H$ are line graphs.<\/jats:p>","DOI":"10.1137\/140963200","type":"journal-article","created":{"date-parts":[[2015,2,10]],"date-time":"2015-02-10T11:20:54Z","timestamp":1423567254000},"page":"348-375","source":"Crossref","is-referenced-by-count":10,"title":["Induced Disjoint Paths in Claw-Free Graphs"],"prefix":"10.1137","volume":"29","author":[{"given":"Petr A.","family":"Golovach","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dani\u00ebl","family":"Paulusma","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Erik Jan","family":"van Leeuwen","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2015,2,10]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-013-9748-5"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(91)90098-M"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(92)90357-L"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2011.04.039"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2011.02.004"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2008.03.002"},{"key":"atypb7","first-page":"153","author":"Chudnovsky M.","year":"2005","journal-title":"UK"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-010-2334-4"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792269095"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2009.02.009"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1007\/s00373-009-0867-3"},{"key":"atypb12","doi-asserted-by":"crossref","unstructured":"R. G. Downey and M. R. Fellows,\n                      Fundamentals of Parameterized Complexity\n                      , Texts Comput. Sci., Springer, New York, 2013.","DOI":"10.1007\/978-1-4471-5559-1"},{"key":"atypb13","doi-asserted-by":"crossref","unstructured":"R. Diestel,\n                      Graph Theory\n                      , Springer-Verlag, New York, 2005.","DOI":"10.1007\/978-3-642-14279-6_7"},{"key":"atypb14","first-page":"1","author":"Fellows M. R.","year":"1989","journal-title":"RI"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1007\/BF01190507"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-010-9468-z"},{"key":"atypb17","first-page":"223","volume":"15","author":"Fiala J.","year":"2013","journal-title":"Discrete Math. Theoret. Comput. Sci."},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2012.11.002"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2011.10.004"},{"key":"atypb20","first-page":"225","author":"Golovach P. A.","year":"2014","journal-title":"Berlin"},{"key":"atypb21","first-page":"153","author":"Golovach P. A.","year":"2012","journal-title":"Berlin"},{"key":"atypb22","first-page":"515","author":"Golovach P. A.","year":"2012","journal-title":"Berlin"},{"key":"atypb23","first-page":"479","author":"Grohe M.","year":"2011","journal-title":"Proceedings of STOC"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.10.021"},{"key":"atypb25","first-page":"25","author":"Habib M.","year":"1998","journal-title":"Berlin"},{"key":"atypb26","doi-asserted-by":"crossref","unstructured":"F. Harary,\n                      Graph Theory\n                      , Addison-Wesley, Reading MA, 1969.","DOI":"10.21236\/AD0705364"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-014-9877-5"},{"key":"atypb28","first-page":"462","author":"Hermelin D.","year":"2011","journal-title":"Berlin"},{"key":"atypb29","doi-asserted-by":"crossref","unstructured":"D. Hermelin, M. Mnich, E. J. van Leeuwen, and G. J. Woeginger,\n                      Domination when the stars are out\n                      , arXiv:1012.0012v1 [cs. DS], 2010.","DOI":"10.1007\/978-3-642-22006-7_39"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1002\/net.1975.5.1.45"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.20334"},{"key":"atypb32","first-page":"1146","author":"Kobayashi Y.","year":"2009","journal-title":"New York"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2011.10.004"},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2009.02.015"},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2010.06.005"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1145\/1061425.1061430"},{"key":"atypb37","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1994.1011"},{"key":"atypb38","doi-asserted-by":"crossref","unstructured":"R. Niedermeier,\n                      Invitation to Fixed-Parameter Algorithms\n                      , Oxford Lecture Ser. Math. Appl., Oxford University Press, New York, 2006.","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001"},{"key":"atypb39","first-page":"295","author":"Reed B. A.","year":"1993","journal-title":"RI"},{"key":"atypb40","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1995.1006"},{"key":"atypb41","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(73)90029-X"},{"key":"atypb42","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1996.1732"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/140963200","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:37:03Z","timestamp":1787319423000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/140963200"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,1]]},"references-count":42,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2015,1]]}},"alternative-id":["10.1137\/140963200"],"URL":"https:\/\/doi.org\/10.1137\/140963200","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,1]]}}}