boundary classes of graphs

Breaking the Boundaries: from Structure to Algorithms

Vadim Lozin, Professor, University of Warwick, UK

Apr 17, 14:00 - 15:00

KAUST

maximum independent set line graphs boundary classes of graphs

Abstract Finding a maximum independent set in a graph is an NP-hard problem. However, restricted to the class of line graphs this problem becomes polynomial-time solvable due to the celebrated matching algorithm of Jack Edmonds. What makes the problem easy in the class of line graphs and what other restrictions can lead to an efficient solution? To answer these questions, we employ the notion of boundary classes of graphs. In this talk, we shed some light on the structure of the boundary separating difficult instances of the problem from polynomially solvable ones and analyze algorithmic tools