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 to break it. We also discuss similar questions with respect to some other algorithmic problems.
Brief Biography
Vadim Lozin is a Professor of Mathematics at the University of Warwick (UK). In the past, he also has held academic and visiting positions in the USA, Russia, Sweden, Switzerland, Portugal, Germany, Canada, Saudi Arabia, Brazil and France. He is the Managing Editor of "Electronic Notes in Discrete Mathematics" (Elsevier), an Associate Editor of "Discrete Applied Mathematics" (Elsevier) and a member of the editorial board of "Discussiones Mathematicae Graph Theory" (De Gruyter). He is an author of 3 books and over 100 journal publications in the area of graph theory, combinatorics, and discrete mathematics. Seven Ph.D. dissertations have been defended under the supervision of Professor Lozin.