The hardness of approximating the boxicity, cubicity and threshold dimension of a graph

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]