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.2017.24
URN: urn:nbn:de:0030-drops-85603
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8560/
Go to the corresponding LIPIcs Volume Portal

Karpov, Nikolai ; Pilipczuk, Marcin ; Zych-Pawlewicz, Anna

An Exponential Lower Bound for Cut Sparsifiers in Planar Graphs

pdf-format:
LIPIcs-IPEC-2017-24.pdf (0.5 MB)

Abstract

Given an edge-weighted graph G with a set Q of k terminals, a mimicking network is a graph with the same set of terminals that exactly preserves the sizes of minimum cuts between any
partition of the terminals. A natural question in the area of graph compression is to provide as small mimicking networks as possible for input graph G being either an arbitrary graph or coming from a specific graph class.

In this note we show an exponential lower bound for cut mimicking networks in planar graphs: there are edge-weighted planar graphs with k terminals that require 2^(k-2) edges in any mimicking network. This nearly matches an upper bound of O(k * 2^(2k)) of Krauthgamer and Rika [SODA 2013, arXiv:1702.05951] and is in sharp contrast with the O(k^2) upper bound under the assumption that all terminals lie on a single face [Goranci, Henzinger, Peng, arXiv:1702.01136]. As a side result we show a hard instance for the double-exponential upper bounds given by Hagerup, Katajainen, Nishimura, and Ragde [JCSS 1998], Khan and Raghavendra [IPL 2014], and Chambers and Eppstein [JGAA 2013].

BibTeX - Entry

@InProceedings{karpov_et_al:LIPIcs:2018:8560,
  author =	{Nikolai Karpov and Marcin Pilipczuk and Anna Zych-Pawlewicz},
  title =	{{An Exponential Lower Bound for Cut Sparsifiers in Planar Graphs}},
  booktitle =	{12th International Symposium on Parameterized and Exact Computation (IPEC 2017)},
  pages =	{24:1--24:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-051-4},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{89},
  editor =	{Daniel Lokshtanov and Naomi Nishimura},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8560},
  URN =		{urn:nbn:de:0030-drops-85603},
  doi =		{10.4230/LIPIcs.IPEC.2017.24},
  annote =	{Keywords: mimicking networks, planar graphs}
}

Keywords: mimicking networks, planar graphs
Collection: 12th International Symposium on Parameterized and Exact Computation (IPEC 2017)
Issue Date: 2018
Date of publication: 02.03.2018

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