Parameterized and Approximation Algorithms for Boxicity

Details Parameterized and Approximation Algorithms for Boxicity Parameterized and Approximation Algorithms for Boxicity

2012-01-28

arxiv.org/abs/1201.5958v2

Computer Science

Data Structures and Algorithms

Scientific paper

Boxicity of a graph $G(V,$ $E)$, denoted by $box(G)$, is the minimum integer $k$ such that $G$ can be represented as the intersection graph of axis parallel boxes in $\mathbb{R}^k$. The problem of computing boxicity is inapproximable even for graph classes like bipartite, co-bipartite and split graphs within $O(n^{0.5 - \epsilon})$-factor, for any $\epsilon >0$ in polynomial time unless $NP=ZPP$. We give FPT approximation algorithms for computing the boxicity of graphs, where the parameter used is the vertex or edge edit distance of the given graph from families of graphs of bounded boxicity. This can be seen as a generalization of the parameterizations discussed in \cite{Adiga2}. Extending the same idea in one of our algorithms, we also get an $O(\frac{n\sqrt{\log \log n}}{\sqrt{\log n}})$-factor approximation algorithm for computing boxicity, which, to our knowledge, is the first $o(n)$ factor approximation algorithm for the boxicity problem.

Affiliated with

Also associated with

No associations

Rating

Parameterized and Approximation Algorithms for Boxicity 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 Parameterized and Approximation Algorithms for Boxicity, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Parameterized and Approximation Algorithms for Boxicity will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-257504