NP-hard graph problems and boundary classes of graphs
Vadim Lozin ( University of Warwick )
- 16:30 2nd March 2010 ( week 7, Hilary Term 2010 )Lecture Theatre B
Any graph problem, which is NP-hard in general graphs, becomes polynomial-time solvable when restricted to graphs in special classes. When does a difficult problem become easy? To answer this question, we study the notion of boundary classes of graphs. Originally, this notion was introduced with respect to the maximum independent set problem, and then was applied to some other algorithmic graph problems. In this talk, we survey recent results on this topic and report a new one. In particular, we reveal the first boundary class for the Hamiltonian Cycle problem.