Solving Stability Problems on a Superclass of Interval Graphs

We introduce a graph invariant, called thinness, and show that a maximum weighted stable set on a graph $G(V, E)$ with thinness $k$ may be found in $O(\frac{|V|}{k})^k$-time, if a certain representation is given. We show that a graph has thinness 1 if and only if it is an interval graph, while a graph with thinness $k$ is the intersection graph of $k$-dimensional boxes. We investigate properties of the thinness and discuss relationships between graphs with thinness at most two and other superclasses of interval graphs. We present real a world application where suitable graphs with small thinness naturally occur: the frequency assignment problem ({\sc fap}). We show that an efficient search in exponential neighbourhoods for {\sc fap} may be done by our polynomial time algorithm. This led us to improving the best known solutions for some benchmark instances of {\sc fap} in {\sc gsm} networks. We discuss other applications where a same approach seems quite natural, among which the single machine scheduling problem. We leave some open questions.

Citation

Tech. Rep. Centro Vito Volterra, n. 511, April 2002.