1. The hardness of approximating the boxicity, cubicity and threshold dimension of a graph
- Author
-
Adiga, Abhijin, Bhowmick, Diptendu, and Sunil Chandran, L.
- Subjects
- *
APPROXIMATION theory , *DIMENSIONAL analysis , *GRAPH theory , *INTERVAL analysis , *POLYNOMIALS , *INTERSECTION graph theory , *SPANNING trees - Abstract
Abstract: A -dimensional box is the Cartesian product where each is a closed interval on the real line. The boxicity of a graph , denoted as , is the minimum integer such that can be represented as the intersection graph of a collection of -dimensional boxes. A unit cube in -dimensional space or a -cube is defined as the Cartesian product where each is a closed interval on the real line of the form . The cubicity of , denoted as , is the minimum integer such that can be represented as the intersection graph of a collection of -cubes. The threshold dimension of a graph is the smallest integer such that can be covered by threshold spanning subgraphs of . In this paper we will show that there exists no polynomial-time algorithm for approximating the threshold dimension of a graph on vertices with a factor of for any unless . From this result we will show that there exists no polynomial-time algorithm for approximating the boxicity and the cubicity of a graph on vertices with factor for any unless . In fact all these hardness results hold even for a highly structured class of graphs, namely the split graphs. We will also show that it is -complete to determine whether a given split graph has boxicity at most 3. [ABSTRACT FROM AUTHOR]
- Published
- 2010
- Full Text
- View/download PDF