Mathematics – Combinatorics
Scientific paper
2009-03-05
Mathematics
Combinatorics
13 pages
Scientific paper
A $k$-dimensional box is the Cartesian product $R_1 \times R_2 \times ... \times R_k$ where each $R_i$ is a closed interval on the real line. The {\it boxicity} of a graph $G$, denoted as $\boxi(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 ... \times R_k$ where each $R_i$ is a closed interval on the real line of the form $[a_i,a_i + 1]$. The {\it 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 {\it 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^{0.5-\epsilon})$ for any $\epsilon >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^{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 if a given split graph has boxicity at most 3.
Adiga Abhijin
Bhowmick Diptendu
Chandran Sunil L.
No associations
LandOfFree
The Hardness of Approximating the Threshold Dimension, Boxicity and Cubicity of a Graph does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with The Hardness of Approximating the Threshold Dimension, Boxicity and Cubicity of a Graph, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Hardness of Approximating the Threshold Dimension, Boxicity and Cubicity of a Graph will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-115506