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

作者：Adiga Abhijin; Bhowmick Diptendu; Chandran L Sunil^*

来源：Discrete Applied Mathematics, 2010, 158(16): 1719-1726.

DOI：10.1016/j.dam.2010.06.017

• Boxicity
• Cubicity
• Threshold dimension
• Partial order dimension
• Split graph
• NP-completeness
• Approximation hardness

A k-dimensional box is the Cartesian product R(1) X R(2) X ... X R(k) where each R(i) is a closed interval on the real line. The boxicity of a graph G, denoted as 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) X R(2) X ... X R(k) where each R(i) is a closed interval oil the real line of the form [a(i), a(i) + 1]. The cubicity of G, denoted as 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-epsilon)) for any epsilon > 0 unless NP = 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-epsilon)) for any epsilon > 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 whether a given split graph has boxicity at most 3.

• 出版日期2010-8-28