Prof. Christophe Picouleau - Seminari Giovedì 28 Aprile alle 14:00 aula 103 "U. Dini"

Titolo: Minimum dominating set problem for claw-free graphs with fixed diameter

Abstract: Given a graph G=(V,E) a dominating set is a subset of
vertices S such that every vertex v that is not in S has a neighbor in
S. The domination number of G is the minimum size of a dominating set.
It was show that computing the domination number is a NP-hard problem
even G is claw-free (G contains no star with four vertices as induced
subgraph).
For $k$ a positive integer, assuming the P/NP conjecture, we show that
deciding the domination number is NP-compete whenever G has a diameter
k greater or equal than 3, and it is polynomial when the diameter of G
is k=2.
This results are obtained in collaboration with Valentin Bouquet.