Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes

Determining a graph from its reconfiguration graph

Given a graph G and a natural number k , the k -recolouring graph C k ( G ) is the graph whose vertices are the k -colourings of G and whose edges link pairs of colourings which differ at exactly one vertex of G . Recently, Hogan et al. proved that G can be determined from C k (...

Tight (Double) Exponential Bounds for Identification Problems: Locating-Dominating Set and Test Cover

Abstract. We investigate fine-grained algorithmic aspects for classical identification problems in graphs, namely, Locating-Dominating Set, and in set systems, namely, Test Cover. In the first problem, an input is a graph [Formula: see text] on [Formula: see text] vertices and an...