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

Abhijin Adiga, Diptendu Bhowmick, L. Sunil ChandranDiscret. Appl. Math 2010 · DOI

Abstract

This paper establishes significant lower bounds on the approximability of three fundamental graph parameters: threshold dimension, boxicity, and cubicity. We demonstrate that for a graph on $n$ vertices, it is impossible to approximate these parameters within a factor of $O(n^{0.5-\epsilon})$ for any $\epsilon > 0$ in polynomial time, unless $NP = ZPP$. Notably, these hardness results persist even when the input is restricted to split graphs. Furthermore, we prove that determining whether a split graph has a boxicity of at most 3 is NP-complete.

Introduction

Representing graphs through geometric structures is a cornerstone of combinatorial geometry and network analysis. Two of the most prominent measures in this field are boxicity and cubicity.

  • Boxicity ($\text{box}(G)$): The minimum dimension $k$ such that $G$ can be represented as the intersection graph of $k$-dimensional axis-parallel boxes (rectangles in 2D, rectangular prisms in 3D, etc.).
  • Cubicity ($\text{cub}(G)$): A more constrained version where the boxes must be unit cubes (Cartesian products of intervals of length 1).

A third, related parameter is the threshold dimension, which measures the minimum number of threshold spanning subgraphs required to cover the edge set of a graph. A threshold graph is one where edges are defined by a weighted sum of vertex values exceeding a certain threshold. While finding the exact values for these parameters has long been known to be NP-hard, the feasibility of efficient approximation remained an open question. This research provides a definitive answer by establishing a high lower bound on approximation ratios.

Methodology: Bridging Graphs and Posets

The authors derive their results by establishing a formal link between graph theory and the theory of partially ordered sets (posets). The central tool in this reduction is the characteristic poset of a split graph.

The Characteristic Poset

A split graph $G(V, E)$ is a graph where the vertex set $V$ can be partitioned into a clique $K$ and an independent set $I$. The authors construct a poset based on the inclusion relationships between the neighborhoods of vertices in $I$. By mapping the structure of the graph to this poset, they show that the dimension of the poset is intrinsically linked to the graph's geometric representation.

Reduction and Hardness Transfer

The proof leverages existing hardness results from poset theory. Specifically, it is known that the dimension of a poset is hard to approximate. The authors prove:

  1. For any split graph, the threshold dimension of its complement is exactly equal to the dimension of its characteristic poset.
  2. The boxicity of the graph is within a factor of two of this poset dimension.

By showing that any efficient approximation of these graph parameters would imply an efficient approximation of poset dimension, the authors transfer the $O(n^{0.5-\epsilon})$ hardness bound to the domain of graphs.

Key Insights

The Complexity of Simple Structures

Perhaps the most surprising finding is that these problems remain computationally intractable even for split graphs. Split graphs are highly structured and often considered "easier" than general graphs for many algorithmic problems. However, this work demonstrates that they are sufficiently expressive to encode the hardest instances of poset dimension problems.

Approximation Limits

The factor of $O(n^{0.5-\epsilon})$ is a substantial barrier. It suggests that for these parameters, standard heuristic or approximation techniques are likely to yield results that are significantly far from the optimal value on worst-case instances. This places boxicity and cubicity among the most difficult graph parameters to approximate.

Results and Implications

The primary contributions of the paper are:

  • Inapproximability Theorem: Unless $NP = ZPP$, no polynomial-time algorithm can approximate the threshold dimension, boxicity, or cubicity of an $n$-vertex graph within a factor of $O(n^{0.5-\epsilon})$.
  • Split Graph Hardness: These hardness results hold even if the input is restricted to the class of split graphs.
  • NP-Completeness of Low Boxicity: The paper proves that deciding if $\text{box}(G) \le 3$ is NP-complete for split graphs. This extends previous work by Yannakakis, who showed a similar result for cubicity.

Future Directions

The current hardness bounds are tied to the state-of-the-art results in poset dimension. Should the complexity community improve the hardness bound for poset dimension (e.g., toward $O(n^{1-\epsilon})$), the bounds for boxicity and cubicity would strengthen accordingly. Additionally, while this paper focuses on split graphs, future research might investigate whether better approximation algorithms exist for other specific graph classes, such as planar graphs or those with bounded degree, where these parameters are known to be naturally constrained.

Summary updated

BibTeX
@article{adiga2010hardness,
  author = {Abhijin Adiga and Diptendu Bhowmick and L. Sunil Chandran},
  title = {{The hardness of approximating the boxicity, cubicity and threshold dimension of a graph}},
  journal = {Discret. Appl. Math.},
  year = {2010},
  doi = {10.1016/j.dam.2010.06.017},
}
Figure