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/
Karpov, Nikolai ;
Pilipczuk, Marcin ;
Zych-Pawlewicz, Anna
An Exponential Lower Bound for Cut Sparsifiers in Planar Graphs
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 |