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

A kk-dimensional box is the Cartesian product R1×R2×⋯×RkR1×R2×⋯×Rk where each RiRi is a closed interval on the real line. The boxicity   of a graph GG, denoted as box(G), is the minimum integer kk such that GG can be represented as the intersection graph of a collection of kk-dimensional boxes. A unit cube in kk-dimensional space or a kk-cube is defined as the Cartesian product R1×R2×⋯×RkR1×R2×⋯×Rk where each RiRi is a closed interval on the real line of the form [ai,ai+1][ai,ai+1]. The cubicity   of GG, denoted as cub(G), is the minimum integer kk such that GG can be represented as the intersection graph of a collection of kk-cubes. The threshold dimension   of a graph G(V,E)G(V,E) is the smallest integer kk such that EE can be covered by kk threshold spanning subgraphs of GG. In this paper we will show that there exists no polynomial-time algorithm for approximating the threshold dimension of a graph on nn vertices with a factor of O(n0.5−ϵ)O(n0.5−ϵ) for any ϵ>0ϵ>0 unless NP=ZPPNP=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 nn vertices with factor O(n0.5−ϵ)O(n0.5−ϵ) for any ϵ>0ϵ>0 unless NP=ZPPNP=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 NPNP-complete to determine whether a given split graph has boxicity at most 3.