The hardness of approximating the boxicity, cubicity and threshold dimension of a graph ?
A k k -dimensional box is the Cartesian product R1R2?Rk R 1  R 2  ?  R k where each Ri R i is a closed interval on the real line. The boxicity  of a graph G G , denoted as box ( G ) , is the minimum integer k k such that G G can be represented as the intersection graph of a collection of k k -dimensional boxes. A unit cube in k k -dimensional space or a k k -cube is defined as the Cartesian product R1R2?Rk R 1  R 2  ?  R k where each Ri R i is a closed interval on the real line of the form [ai,ai+1] [ a i , a i + 1 ] . The cubicity  of G G , denoted as cub ( G ) , is the minimum integer k k such that G G can be represented as the intersection graph of a collection of k k -cubes. The threshold dimension  of a graph G(V,E) G ( V , E ) is the smallest integer k k such that E E can be covered by k k threshold spanning subgraphs of G G . In this paper we will show that there exists no polynomial-time algorithm for approximating the threshold dimension of a graph on n n vertices with a factor of O(n0.5??) O ( n 0.5 ? ? ) for any ?>0 ? > 0 unless NP=ZPP N P = Z P P . From this result we will show that there exists no polynomial-time algorithm for approximating the boxicity and the cubicity of a graph on n n vertices with factor O(n0.5??) O ( n 0.5 ? ? ) for any ?>0 ? > 0 unless NP=ZPP N P = Z P P . 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 NP N P -complete to determine whether a given split graph has boxicity at most 3.
boxicity cubicity threshold dimension split graph partial order dimension np n p -completeness np n p np n p n p approximation hardness