- Supervisor
- Andrea Munaro - University of Primorska, Slovenia
- Date and time
- Thursday, September 21, 2017 at 3:00 PM - Aula M -- rinfresco 14.45, inizio seminario 15.00.
- Programme Director
- External reference
- Publication date
- September 11, 2017
- Department
- Computer Science

Many NP-hard graph problems remain NP-hard even for restricted classes of graphs, while they become polynomial-time solvable when further restrictions are applied. It is therefore natural to ask when a certain "hard" graph problem becomes "easy": Is there any "boundary" separating "easy" and "hard" instances? Alekseev considered this question in the case the instances are hereditary classes of graphs. Given a graph problem Pi, a hereditary class of graphs X is Pi-hard if Pi is NP-hard for X, and Pi-easy if Pi is solvable in polynomial time for graphs in X. He introduced the notion of Pi-boundary class, playing the role of the "boundary" separating Pi-hard and Pi-easy instances, and showed that a finitely defined (hereditary) class is Pi-hard if and only if it contains a Pi-boundary class. Moreover, he determined a boundary class for Independent Set, the first result in the systematic study of boundary classes for NP-hard graph problems. In the talk, I will review some known results and present new boundary classes for some problems involving non-local properties, like Hamiltonian Path and Feedback Vertex Set. Contact Persons: Romeo Rizzi and Giuseppe Mazzuoccolo

© 2002 - 2021
Verona University

Via dell'Artigliere 8, 37129 Verona |
P. I.V.A. 01541040232 |
C. FISCALE 93009870234