Sublinear approximation algorithms for boxicity and related problems

DOI10.1016/J.DAM.2017.10.031MaRDI QIDQ1693125zbMATH OpenOpenAlexFDO

Authors Abhijin Adiga, Jasine Babu, L. Sunil Chandran

Publication date 11 January 2018

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1505.04918

zbMATH Keywords

approximation algorithmparameterizationboxicitypartial order dimensionthreshold dimension

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Graph operations (line graphs, products, etc.) (05C76)

Abstract: Boxicity of a graph G(V, E) is the minimum integer k such that G can be represented as the intersection graph of axis parallel boxes in $mathbb{R}^k$. Cubicity is a variant of boxicity, where the axis parallel boxes in the intersection representation are restricted to be of unit length sides. Deciding whether boxicity (resp. cubicity) of a graph is at most k is NP-hard, even for k=2 or 3. Computing these parameters is inapproximable within $O(n^{1-epsilon})$-factor, for any $epsilon>0$ in polynomial time unless NP=ZPP, even for many simple graph classes. In this paper, we give a polynomial time $kappa(n)$ factor approximation algorithm for computing boxicity and a $kappa(n)lceilloglognceil$ factor approximation algorithm for computing the cubicity, where $kappa(n)=2leftlceilfracnsqrtloglognsqrtlognightceil$. These o(n) factor approximation algorithms also produce the corresponding box (resp. cube) representations. As a special case, this resolves the question paused by Spinrad about polynomial time construction of o(n) dimensional box representations for boxicity 2 graphs. Other consequences of our approximation algorithm include $O(kappa(n))$ factor approximation algorithms for computing the following parameters: the partial order dimension of finite posets, the interval dimension of finite posets, minimum chain cover of bipartite graphs, threshold dimension of split graphs and Ferrer's dimension of digraphs. Each of these parameters is inapproximable within an $O(n^{1-epsilon})$-factor, for any $epsilon>0$ in polynomial time unless NP=ZPP and the algorithms we derive seem to be the first o(n) factor approximation algorithms known for all these problems.

Recommendations

• Polynomial time and parameterized approximation algorithms for boxicity
• The hardness of approximating the boxicity, cubicity and threshold dimension of a graph
• Geometric Representation of Graphs in Low Dimension
• Parameterized algorithms for boxicity

Cites work

• scientific article; zbMATH DE number 3672353 (Why is no real title available?)
• scientific article; zbMATH DE number 3598234 (Why is no real title available?)
• scientific article; zbMATH DE number 3307331 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• scientific article; zbMATH DE number 3064989 (Why is no real title available?)
• A special planar satisfiability problem and a consequence of its NP- completeness
• Boxicity and treewidth
• Complexity results on graphs with few cliques
• Computing crossing numbers in quadratic time
• Cubicity of interval graphs and the claw number
• Cubicity, boxicity, and vertex cover
• Efficient graph representations
• Ferrers dimension of grid intersection graphs
• Interval Completion Is Fixed Parameter Tractable
• Interval representations of planar graphs
• Obtaining a planar graph by vertex deletion
• On feedback vertex set: new measure and new structures
• On the Ferrers dimension of a digraph
• On the Interplay Between Interval Dimension and Dimension
• Parameterized algorithms for boxicity
• Parameterized complexity of vertex colouring
• Polynomial time and parameterized approximation algorithms for boxicity
• Proper interval vertex deletion
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• The Complexity of the Partial Order Dimension Problem
• The complexity ecology of parameters: An illustration using bounded max leaf number
• The complexity of the partial order dimension problem: closing the gap
• The relationship between the threshold dimension of split graphs and various dimensional parameters
• Threshold graphs and related topics
• Unit disk graph recognition is NP-hard
• Well-quasi-orders in subclasses of bounded treewidth graphs

Cited in

(10)

• Geometric representation of graphs in low dimension using axis parallel boxes
• Lower bounds for boxicity
• Approximation hardness of optimization problems in intersection graphs of \(d\)-dimensional boxes
• The Complexity of Combinatorial Optimization Problems on d‐Dimensional Boxes
• Asymptotic relative submajorization of multiple-state boxes
• Parameterized algorithms for boxicity
• Geometric Representation of Graphs in Low Dimension
• Polynomial time and parameterized approximation algorithms for boxicity
• A constant factor approximation algorithm for boxicity of circular arc graphs
• Improved approximation algorithms for box contact representations

This page was built for publication: Sublinear approximation algorithms for boxicity and related problems

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