Fiala, J. and Kaminski, M. and Lidický, B. and Paulusma, Daniel (2012) 'The k-in-a-path problem for claw-free graphs.', *Algorithmica.*, 62 (1-2). pp. 499-519.

## Abstract

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,…,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,…,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.

Item Type: | Article |
---|---|

Keywords: | Induced path, Claw-free graph, Polynomial time algorithm. |

Full text: | PDF - Accepted Version (311Kb) |

Status: | Peer-reviewed |

Publisher Web site: | http://dx.doi.org/10.1007/s00453-010-9468-z |

Publisher statement: | The final publication is available at Springer via http://dx.doi.org/10.1007/s00453-010-9468-z |

Record Created: | 07 Dec 2011 14:35 |

Last Modified: | 12 Aug 2015 16:28 |

Social bookmarking: | Export: EndNote, Zotero | BibTex |

Usage statistics | Look up in GoogleScholar | Find in a UK Library |