Polynomial time and parameterized approximation algorithms for boxicity

DOI10.1007/978-3-642-33293-7_14MaRDI QIDQ4899248zbMATH OpenOpenAlexFDO

Authors Abhijin Adiga, Jasine Babu, L. Sunil Chandran

Publication date 7 January 2013

Published in Parameterized and Exact Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1201.5958, http://eprints.iisc.ac.in/47704/1/1201.5958v2.pdf

zbMATH Keywords

approximation algorithmboxicityparameterized algorithm

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Abstract: 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^{1-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 $Oleft(fracnsqrtloglognsqrtlognight)$ factor approximation algorithm for computing boxicity and an $Oleft(fracn{(loglogn)}^{frac32}sqrtlognight)$ factor approximation algorithm for computing the cubicity. These seem to be the first $o(n)$ factor approximation algorithms known for both boxicity and cubicity. As a consequence of this result, a $o(n)$ factor approximation algorithm for computing the partial order dimension of finite posets and a $o(n)$ factor approximation algorithm for computing the threshold dimension of split graphs would follow.

Recommendations

• Sublinear approximation algorithms for boxicity and related problems
• Parameterized algorithms for boxicity
• A constant factor approximation algorithm for boxicity of circular arc graphs
• The hardness of approximating the boxicity, cubicity and threshold dimension of a graph

Cited in

(10)

• Sublinear approximation algorithms for boxicity and related problems
• Parameterized analysis and crossing minimization problems
• An approximation algorithm for box abstraction of transition systems on real state spaces
• Lower bounds for boxicity
• Approximation hardness of optimization problems in intersection graphs of d-dimensional boxes
• The complexity of the partial order dimension problem: closing the gap
• Parameterized algorithms for boxicity
• A constant factor approximation algorithm for boxicity of circular arc graphs
• Improved approximation algorithms for box contact representations
• The Complexity of Combinatorial Optimization Problems on d‐Dimensional Boxes

This page was built for publication: Polynomial time and parameterized approximation algorithms for boxicity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4899248)