Skip to main content

NP-hard graph problems and boundary classes of graphs

Vadim Lozin ( University of Warwick )

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.

Share this: