Structural parameterizations for boxicity

DOI10.1007/978-3-319-12340-0_10zbMATH Open1339.68200arXiv1402.4992OpenAlexW1548626548MaRDI QIDQ289935FDOQ289935

Felix Joos, Henning Bruhn, Morgan Chopin, Oliver Schaudt

Publication date: 31 May 2016

Published in: Algorithmica, Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Abstract: The boxicity of a graph $G$ is the least integer $d$ such that $G$ has an intersection model of axis-aligned $d$-dimensional boxes. Boxicity, the problem of deciding whether a given graph $G$ has boxicity at most $d$, is NP-complete for every fixed $dge2$. We show that boxicity is fixed-parameter tractable when parameterized by the cluster vertex deletion number of the input graph. This generalizes the result of Adiga et al., that boxicity is fixed-parameter tractable in the vertex cover number. Moreover, we show that boxicity admits an additive $1$-approximation when parameterized by the pathwidth of the input graph. Finally, we provide evidence in favor of a conjecture of Adiga et al. that boxicity remains NP-complete when parameterized by the treewidth.

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

zbMATH Keywords

treewidthparameterized complexitykernelizationboxicity

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Fundamentals of parameterized complexity
• Fixed-parameter tractability of graph modification problems for hereditary properties
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Efficient graph representations
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Representation of a finite graph by a set of intervals on the real line
• The Complexity of the Partial Order Dimension Problem
• Interval representations of planar graphs
• A special planar satisfiability problem and a consequence of its NP- completeness
• Well quasi orders in subclasses of bounded treewidth graphs and their algorithmic applications
• Boxicity and treewidth
• Twin-Cover: Beyond Vertex Cover in Parameterized Algorithmics
• Cluster Vertex Deletion: A Parameterization between Vertex Cover and Clique-Width
• Parameterized Algorithms for Boxicity
• On a Coloring Problem.
• Polynomial Time and Parameterized Approximation Algorithms for Boxicity
• Coloring Graph Powers: Graph Product Bounds and Hardness of Approximation
• Boxicity and Poset Dimension
• The hardness of approximating the boxicity, cubicity and threshold dimension of a graph

Cited In (3)

• Principles and Practice of Constraint Programming – CP 2003
• Sublinear approximation algorithms for boxicity and related problems
• Approximate association via dissociation

This page was built for publication: Structural parameterizations for boxicity

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