Colloquium Details
The k-in-a-path problem for claw-free graphs
| Author: | Jiri Fiala Charles University, Czech Republic |
|---|---|
| Date: | October 04, 2012 |
| Time: | 15:30 |
| Location: | 220 Deschutes |
| Host: | Andrzej Proskurowski |
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.
When $k$ is part of the input, then this problems is NP-complete, even for the class of line graphs, which form a subclass of the class of claw-free graphs.
Joint work with Marcin Kaminski, Bernard Lidicky and Daniel Paulusma
Biography
Jiri Fiala is an associate professor at the Department of Applied Mathematics at Charles University in Prague. He is a visiting faculty this academic year in the CIS department, supported by a Fulbright fellowship.