DIMACS Special Seminar


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.