Groupe d’études et de recherche en analyse des décisions

Boundary Classes of Graphs for NP-hard Problems: When a Difficult Problem Becomes Easy

Vadim Lozin

We study graph problems that are NP-hard in general, which means they are NP-hard in the class of all graphs. On the other hand, by restricting the class of input graphs, one can transform any NP-hard problem into a tractable one, i.e. solvable in polynomial time. When a difficult problem becomes easy? Is there any boundary that separates classes of graphs where the problem remains NP-hard from those where it has a polynomial-time solution? A partial answer to these general questions is given by the notion of boundary classes. In this talk we define this notion in its most general form and apply it to various graph problems such as MAXIMUM INDEPENDENT SET or MINIMUM DOMINATING SET.

Different parts of this work have been done in collaboration with V. Alekseev, D. Korobitsyn (University of Nizhny Novgorod, Russia) and R. Boliac (Rutgers University).