License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.IPEC.2015.236
URN: urn:nbn:de:0030-drops-55865
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/5586/
Go to the corresponding LIPIcs Volume Portal

Bulian, Jannis ; Dawar, Anuj

Fixed-parameter Tractable Distances to Sparse Graph Classes

pdf-format:
23.pdf (0.5 MB)

Abstract

We show that for various classes C of sparse graphs, and several measures of distance to such classes (such as edit distance and elimination distance), the problem of determining the distance of a given graph G to C is fixed-parameter tractable. The results are based on two general techniques. The first of these, building on recent work of Grohe et al. establishes that any class of graphs that is slicewise nowhere dense and slicewise first-order definable is FPT. The second shows that determining the elimination distance of a graph G to a minor-closed class C is FPT.

BibTeX - Entry

@InProceedings{bulian_et_al:LIPIcs:2015:5586,
  author =	{Jannis Bulian and Anuj Dawar},
  title =	{{Fixed-parameter Tractable Distances to Sparse Graph Classes}},
  booktitle =	{10th International Symposium on Parameterized and Exact Computation (IPEC 2015)},
  pages =	{236--247},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-92-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{43},
  editor =	{Thore Husfeldt and Iyad Kanj},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/5586},
  URN =		{urn:nbn:de:0030-drops-55865},
  doi =		{10.4230/LIPIcs.IPEC.2015.236},
  annote =	{Keywords: parameterized complexity, fixed-parameter tractable,   distance, graph theory, sparse graphs, graph minor, nowhere dense}
}

Keywords: parameterized complexity, fixed-parameter tractable, distance, graph theory, sparse graphs, graph minor, nowhere dense
Collection: 10th International Symposium on Parameterized and Exact Computation (IPEC 2015)
Issue Date: 2015
Date of publication: 19.11.2015

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI