Summary: A \(k\)-dimensional box is the Cartesian product \(R_1\times R_2\times\cdots\times R_k\) where each \(R_i\) is a closed interval on the real line. The boxicity of a graph \(G\), denoted as \(\text{box}(G)\), is the minimum integer \(k\) such that \(G\) can be represented as the intersection graph of a collection of \(k\)-dimensional boxes. A unit cube in \(k\)-dimensional space or a \(k\)-cube is defined as the Cartesian product \(R_1\times R_2\times\cdots\times R_k\) where each \(R_i\) is a closed interval on the real line of the form \([a_i,a_i+ 1]\). The cubicity of \(G\), denoted as \(\text{cub}(G)\), is the minimum integer \(k\) such that \(G\) can be represented as the intersection graph of a collection of \(k\)-cubes. The threshold dimension of a graph \(G(V,E)\) is the smallest integer \(k\) such that \(E\) can be covered by \(k\) threshold spanning subgraphs of \(G\).
In this paper we will show that there exists no polynomial-time algorithm for approximating the threshold dimension of a graph on \(n\) vertices with a factor of \(O(n^{0.5-\varepsilon})\) for any \(\varepsilon> 0\) unless \(\text{NP}= \text{ZPP}\). 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\) vertices with factor \(O(n^{0.5-\varepsilon})\) for any \(\varepsilon> 0\) unless \(\text{NP}= \text{ZPP}\). 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-complete to determine whether a given split graph has boxicity at most 3.