Abstract
A -dimensional box is the Cartesian product where each is a closed interval on the real line. The {\it boxicity} of a graph , denoted as $\boxi(G)$, is the minimum integer such that can be represented as the intersection graph of a collection of -dimensional boxes. A unit cube in -dimensional space or a -cube is defined as the Cartesian product where each is a closed interval on the real line of the form . The {\it cubicity} of , denoted as $\cub(G)$, is the minimum integer such that can be represented as the intersection graph of a collection of -cubes. The {\it threshold dimension} of a graph is the smallest integer such that can be covered by threshold spanning subgraphs of . In this paper we will show that there exists no polynomial-time algorithm to approximate the threshold dimension of a graph on vertices with a factor of for any , unless . From this result we will show that there exists no polynomial-time algorithm to approximate the boxicity and the cubicity of a graph on vertices with factor for any , unless . 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.
Connections
Explore this paper’s authors, topics and related work.
Building this map preview
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Reviews 0
Write a review
No reviews yet.
Discussion 0
Add a comment
No comments yet.