Header menu link for other important links
X
Polynomial time and parameterized approximation algorithms for boxicity
A. Adiga, , L.S. Chandran
Published in
2012
Volume: 7535 LNCS
   
Pages: 135 - 146
Abstract
The boxicity (cubicity) of a graph G, denoted by box(G) (respectively cub(G)), is the minimum integer k such that G can be represented as the intersection graph of axis parallel boxes (cubes) in ℝk. The problem of computing boxicity (cubicity) is known to be inapproximable in polynomial time even for graph classes like bipartite, co-bipartite and split graphs, within an O(n0.5-ε) factor for any ε > 0, unless NP = ZPP. We prove that if a graph G on n vertices has a clique on n - k vertices, then box(G) can be computed in time n22 O(k2 log k). Using this fact, various FPT approximation algorithms for boxicity are derived. The parameter used is the vertex (or edge) edit distance of the input graph from certain graph families of bounded boxicity - like interval graphs and planar graphs. Using the same fact, we also derive an O(n√log log n/√ log n) factor approximation algorithm for computing boxicity, which, to our knowledge, is the first o(n) factor approximation algorithm for the problem. We also present an FPT approximation algorithm for computing the cubicity of graphs, with vertex cover number as the parameter. © 2012 Springer-Verlag.
About the journal
JournalLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN03029743