Title: The k-in-a-path problem for claw-free graphs
Speaker: Jiri Fiala, Charles University, Prague
Date: Tuesday, January 24, 2012
Lunch Served: 12:00pm
Seminar: 1:00 - 2:00pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
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. The proof is based on structural reductions of this problem to quasi-line graphs, interval graphs and circular-arc graphs.
When k is part of the input, we show that this problem 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.