From structure to algorithms : breaking the boundaries

Lundi 9 avril 2018, 14h,

Vadim V. Lozin, University of Warwick)

Many algorithmic problems that are generally intractable may become easy when restricted to instances of particular structure. When and why a difficult problem becomes easy ? To answer these questions, we employ the notion of boundary classes of graphs. In this talk, we focus on the maximum independent set problem and shed some light on the structure of the boundary separating difficult instances of this problem from polynomially solvable ones. We also analyze algorithmic tools to break the boundary and discuss similar questions with respect to some other algorithmic problems, including Satisfiability, the central problem of Theoretical Computer Science.