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

preprint2010arXivOpen access

Abstract

A kk-dimensional box is the Cartesian product R1×R2×...×RkR_1 \times R_2 \times ... \times R_k where each RiR_i is a closed interval on the real line. The {\it boxicity} of a graph GG, denoted as $\boxi(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×...×RkR_1 \times R_2 \times ... \times R_k where each RiR_i is a closed interval on the real line of the form [ai,ai+1][a_i,a_i + 1]. The {\it 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 {\it 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 to approximate the threshold dimension of a graph on nn vertices with a factor of O(n0.5−ε)O(n^{0.5-ε}) for any ε>0ε>0, unless NP=ZPPNP=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 nn vertices with factor O(n0.5−ε)O(n^{0.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 NP-complete to determine if a given split graph has boxicity at most 3.

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 reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.