. . "0178-4617" . . . "62" . . "http://dx.doi.org/10.1007/s00453-010-9468-z" . "Fiala, Ji\u0159\u00ED" . "21"^^ . "10.1007/s00453-010-9468-z" . "The k-in-a-Path Problem for Claw-free Graphs"@en . . . "RIV/00216208:11320/12:10125750" . "DE - Spolkov\u00E1 republika N\u011Bmecko" . "Polynomial time algorithm; Claw-free graph; Induced path"@en . . "The k-in-a-Path Problem for Claw-free Graphs" . "The k-in-a-Path Problem for Claw-free Graphs"@en . "2"^^ . "Lidick\u00FD, Bernard" . . "Algorithmica" . "P(1M0545), P(GA201/09/0197)" . . "The k-in-a-Path Problem for Claw-free Graphs" . "4"^^ . . . "1-2" . . . "Kaminski, Marcin" . . "11320" . . "Paulusma, Daniel" . "[65428F58847F]" . "The k-in-a-Path problem is to test whether a graph contains an induced path spanning k given vertices. This problem is NP-complete in general graphs, already when k=3. We show how to solve it in polynomial time on claw-free graphs, when k is an arbitrary fixed integer not part of the input. As a consequence, also the k-Induced Disjoint Paths and the k-in-a-Cycle problem are solvable in polynomial time on claw-free graphs for any fixed k. The first problem has as input a graph G and k pairs of specified vertices (s (i) ,t (i) ) for i=1,aEuro broken vertical bar,k and is to test whether G contain k mutually induced paths P (i) such that P (i) connects s (i) and t (i) for i=1,aEuro broken vertical bar,k. The second problem is to test whether a graph contains an induced cycle spanning k given vertices. When k is part of the input, we show that all three problems are NP-complete, even for the class of line graphs, which form a subclass of the class of claw-free graphs."@en . "RIV/00216208:11320/12:10125750!RIV13-GA0-11320___" . "144625" . "The k-in-a-Path problem is to test whether a graph contains an induced path spanning k given vertices. This problem is NP-complete in general graphs, already when k=3. We show how to solve it in polynomial time on claw-free graphs, when k is an arbitrary fixed integer not part of the input. As a consequence, also the k-Induced Disjoint Paths and the k-in-a-Cycle problem are solvable in polynomial time on claw-free graphs for any fixed k. The first problem has as input a graph G and k pairs of specified vertices (s (i) ,t (i) ) for i=1,aEuro broken vertical bar,k and is to test whether G contain k mutually induced paths P (i) such that P (i) connects s (i) and t (i) for i=1,aEuro broken vertical bar,k. The second problem is to test whether a graph contains an induced cycle spanning k given vertices. When k is part of the input, we show that all three problems are NP-complete, even for the class of line graphs, which form a subclass of the class of claw-free graphs." . . "000298388200022" . .