Artykuł w czasopiśmie
Brak miniatury
Licencja
ClosedAccessDostęp zamknięty
 

An Exponential Lower Bound for Cut Sparsifiers in Planar Graphs

Uproszczony widok
dc.abstract.enGiven 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 size of minimum cut 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. We show an exponential lower bound for cut mimicking networks in planar graphs: there are edge-weighted planar graphs with k terminals that require 2k−2 edges in any mimicking network. This nearly matches an upper bound of O(k22k) of Krauthgamer and Rika (in: Khanna (ed) Proceedings of the twenty-fourth annual ACM-SIAM symposium on discrete algorithms, SODA 2013, New Orleans, 2013) and is in sharp contrast with the upper bounds of O(k2) and O(k4) under the assumption that all terminals lie on a single face (Goranci et al., in: Pruhs and Sohler (eds) 25th Annual European symposium on algorithms (ESA 2017), 2017, arXiv:1702.01136; Krauthgamer and Rika in Refined vertex sparsifiers of planar graphs, 2017, arXiv:1702.05951). As a side result we show a tight example for double-exponential upper bounds given by Hagerup et al. (J Comput Syst Sci 57(3):366–375, 1998), Khan and Raghavendra (Inf Process Lett 114(7):365–371, 2014), and Chambers and Eppstein (J Gr Algorithms Appl 17(3):201–220, 2013).
dc.affiliationUniwersytet Warszawski
dc.contributor.authorPilipczuk, Marcin
dc.contributor.authorKarpov, Nikolai
dc.contributor.authorZych-Pawlewicz, Anna
dc.date.accessioned2024-01-24T16:42:11Z
dc.date.available2024-01-24T16:42:11Z
dc.date.issued2019
dc.description.financeNie dotyczy
dc.description.number10
dc.description.volume81
dc.identifier.doi10.1007/S00453-018-0504-8
dc.identifier.issn0178-4617
dc.identifier.urihttps://repozytorium.uw.edu.pl//handle/item/100899
dc.identifier.weblinkhttp://link.springer.com/content/pdf/10.1007/s00453-018-0504-8.pdf
dc.languageeng
dc.pbn.affiliationcomputer and information sciences
dc.relation.ispartofAlgorithmica
dc.relation.pages4029-4042
dc.rightsClosedAccess
dc.sciencecloudnosend
dc.subject.enMimicking network
dc.subject.enPlanar graph
dc.subject.enSparsifier
dc.titleAn Exponential Lower Bound for Cut Sparsifiers in Planar Graphs
dc.typeJournalArticle
dspace.entity.typePublication