The intersection number of a graph G is the minimum size of a set S such that G is an intersection graph of some family of subsets ⊆2S. The overlap number of G is defined similarly, except that G is required to be an overlap graph of . Computing the overlap number of a graph has been stated as an open problem in [B. Rosgen and L. Stewart, 2010, arXiv:1008.2170v2] and [D.W. Cranston, et al., J. Graph Theory., 2011]. In this paper we show two algorithmic aspects concerning both these graph invariants. On the one hand, we show that the corresponding optimization problems associated with these numbers are both APX-hard, where for the intersection number our results hold even for biconnected graphs of maximum degree 7, strengthening the previously known hardness result. On the other hand, we show that the recognition problem for any specific intersection graph class (e.g. interval, unit disc, …) is easy when restricted to graphs with fixed intersection number.

Algorithmic Aspects of the Intersection and Overlap Numbers of a GraphAlgorithms and Computation

RIZZI, ROMEO;
2012-01-01

Abstract

The intersection number of a graph G is the minimum size of a set S such that G is an intersection graph of some family of subsets ⊆2S. The overlap number of G is defined similarly, except that G is required to be an overlap graph of . Computing the overlap number of a graph has been stated as an open problem in [B. Rosgen and L. Stewart, 2010, arXiv:1008.2170v2] and [D.W. Cranston, et al., J. Graph Theory., 2011]. In this paper we show two algorithmic aspects concerning both these graph invariants. On the one hand, we show that the corresponding optimization problems associated with these numbers are both APX-hard, where for the intersection number our results hold even for biconnected graphs of maximum degree 7, strengthening the previously known hardness result. On the other hand, we show that the recognition problem for any specific intersection graph class (e.g. interval, unit disc, …) is easy when restricted to graphs with fixed intersection number.
9783642352607
overlap number; intersection graph
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11562/883987
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? ND
social impact