The Hardness of Approximating the Threshold Dimension, Boxicity and Cubicity of a Graph

الأصل · EN

A k-dimensional box is the Cartesian product R₁ × R₂ ×... × Rₖ where each Rᵢ is a closed interval on the real line. The boxicity of a graph G, denoted as (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₁ × R₂ ×... × Rₖ where each Rᵢ is a closed interval on the real line of the form [aᵢ,aᵢ + 1]. The cubicity of G, denoted as (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 to approximate the threshold dimension of a graph on n vertices with a factor of O(n⁰.⁵⁻ε) for any ε>0, unless NP=ZPP. From this result we will show that there exists no polynomial-time algorithm to approximate the boxicity and the cubicity of a graph on n vertices with factor O(n⁰.⁵⁻ε) for any ε>0, unless NP=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 if a given split graph has boxicity at most 3.