2026-07-20T12:09:20Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8560 2024-03-06T10:41:32Z ddc:004 open_access

An Exponential Lower Bound for Cut Sparsifiers in Planar Graphs Karpov, Nikolai Pilipczuk, Marcin Zych-Pawlewicz, Anna mimicking networks planar graphs 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]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Nikolai Karpov and Marcin Pilipczuk and Anna Zych-Pawlewicz 2018 Is Part Of LIPIcs, Volume 89, 12th International Symposium on Parameterized and Exact Computation (IPEC 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2017.24 urn:nbn:de:0030-drops-85603 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2017.24 eng https://creativecommons.org/licenses/by/3.0/legalcode