Boxicity and Poset Dimension

Autor: L. Sunil Chandran, Diptendu Bhowmick, Abhijin Adiga
Přispěvatelé: Thai, MT, Sahni, S
Rok vydání: 2011
Předmět:
Zdroj: Lecture Notes in Computer Science ISBN: 9783642140303
COCOON
ISSN: 1095-7146
0895-4801
DOI: 10.1137/100786290
Popis: Let $G$ be a simple, undirected, finite graph with vertex set $V(G)$ and edge set $E(G)$. A $k$-dimensional box is a Cartesian product of closed intervals $[a_1,b_1]\times [a_2,b_2]\times\cdots\times [a_k,b_k]$. The boxicity of $G$, box$(G)$, is the minimum integer $k$ such that $G$ can be represented as the intersection graph of $k$-dimensional boxes; i.e., each vertex is mapped to a $k$-dimensional box and two vertices are adjacent in $G$ if and only if their corresponding boxes intersect. Let $\mathcal{P}=(S,P)$ be a poset, where $S$ is the ground set and $P$ is a reflexive, antisymmetric and transitive binary relation on $S$. The dimension of $\mathcal{P}$, $\dim(\mathcal{P})$, is the minimum integer $t$ such that $P$ can be expressed as the intersection of $t$ total orders. Let $G_{\mathcal{P}}$ be the underlying comparability graph of $\mathcal{P}$; i.e., $S$ is the vertex set and two vertices are adjacent if and only if they are comparable in $\mathcal{P}$. It is a well-known fact that posets with the same underlying comparability graph have the same dimension. The first result of this paper links the dimension of a poset to the boxicity of its underlying comparability graph. In particular, we show that for any poset $\mathcal{P}$, box$(G_{\mathcal{P}})/(\chi(G_{\mathcal{P}})-1) \le \dim(\mathcal{P})\le 2\mbox{box}(G_{\mathcal{P}})$, where $\chi(G_{\mathcal{P}})$ is the chromatic number of $G_{\mathcal{P}}$ and $\chi(G_{\mathcal{P}})\ne1$. It immediately follows that if $\mathcal{P}$ is a height-$2$ poset, then box$(G_{\mathcal{P}})\le \dim(\mathcal{P})\le 2\mbox{box}(G_{\mathcal{P}})$ since the underlying comparability graph of a height-$2$ poset is a bipartite graph. The second result of the paper relates the boxicity of a graph $G$ with a natural partial order associated with the extended double cover of $G$, denoted as $G_c$: Note that $G_c$ is a bipartite graph with partite sets $A$ and $B$ which are copies of $V(G)$ such that, corresponding to every $u\in V(G)$, there are two vertices $u_A\in A$ and $u_B\in B$ and $\{u_A,v_B\}$ is an edge in $G_c$ if and only if either $u=v$ or $u$ is adjacent to $v$ in $G$. Let $\mathcal{P}_c$ be the natural height-$2$ poset associated with $G_c$ by making $A$ the set of minimal elements and $B$ the set of maximal elements. We show that $\frac{\mbox{box}(G)}{2} \le \dim(\mathcal{P}_c) \le 2\mbox{box}(G)+4$. These results have some immediate and significant consequences. The upper bound $\dim(\mathcal{P})\le 2\mbox{box}(G_\mathcal{P})$ allows us to derive hitherto unknown upper bounds for poset dimension such as $\dim(\mathcal{P})\le 2\mbox{ tree width }(G_{\mathcal{P}})+4$, since boxicity of any graph is known to be at most its tree width $+\; 2$. In the other direction, using the already known bounds for partial order dimension we get the following: (1) The boxicity of any graph with maximum degree $\Delta$ is $O(\Delta\log^2\Delta)$, which is an improvement over the best-known upper bound of $\Delta^2+2$. (2) There exist graphs with boxicity $\Omega(\Delta\log\Delta)$. This disproves a conjecture that the boxicity of a graph is $O(\Delta)$. (3) There exists no polynomial-time algorithm to approximate the boxicity of a bipartite graph on $n$ vertices with a factor of $O(n^{0.5-\epsilon})$ for any $\epsilon>0$ unless $NP=ZPP$.
Databáze: OpenAIRE
Externí odkaz: