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

Neighborhood Complexity and Kernelization for Nowhere Dense Classes of Graphs

Uproszczony widok
cris.lastimport.scopus2024-02-12T19:33:04Z
dc.abstract.enWe prove that whenever G is a graph from a nowhere dense graph class C, and A is a subset of vertices of G, then the number of subsets of A that are realized as intersections of A with r-neighborhoods of vertices of G is at most f(r,eps)|A|^(1+eps), where r is any positive integer, eps is any positive real, and f is a function that depends only on the class C. This yields a characterization of nowhere dense classes of graphs in terms of neighborhood complexity, which answers a question posed by [Reidl et al., CoRR, 2016]. As an algorithmic application of the above result, we show that for every fixed integer r, the parameterized Distance-r Dominating Set problem admits an almost linear kernel on any nowhere dense graph class. This proves a conjecture posed by [Drange et al., STACS 2016], and shows that the limit of parameterized tractability of Distance-r Dominating Set on subgraph-closed graph classes lies exactly on the boundary between nowhere denseness and somewhere denseness.
dc.affiliationUniwersytet Warszawski
dc.conference.countryPolska
dc.conference.datefinish2017-07-14
dc.conference.datestart2017-07-10
dc.conference.placeWarszawa
dc.conference.seriesInternational Colloquium on Automata Languages and Programming
dc.conference.seriesInternational Colloquium on Automata Languages and Programming
dc.conference.seriesshortcutICALP
dc.conference.shortcutICALP 2017
dc.conference.weblinkhttp://icalp17.mimuw.edu.pl/
dc.contributor.authorPilipczuk, Michał
dc.contributor.authorSiebertz, Sebastian
dc.contributor.authorEickmeyer, Kord
dc.contributor.authorGiannopoulou, Archontia C.
dc.contributor.authorKwon, O-joung
dc.contributor.authorRabinovich, Roman
dc.contributor.authorKreutzer, Stephan
dc.date.accessioned2024-01-25T13:31:53Z
dc.date.available2024-01-25T13:31:53Z
dc.date.issued2017
dc.description.financeNie dotyczy
dc.identifier.doi10.4230/LIPICS.ICALP.2017.63
dc.identifier.urihttps://repozytorium.uw.edu.pl//handle/item/113475
dc.identifier.weblinkhttps://drops.dagstuhl.de/opus/volltexte/2017/7428/
dc.languageeng
dc.pbn.affiliationcomputer and information sciences
dc.relation.pages63:1--63:14
dc.rightsClosedAccess
dc.sciencecloudnosend
dc.subject.enGraph Structure Theory
dc.subject.enNowhere Dense Graphs
dc.subject.enParameterized Complexity
dc.subject.enKernelization
dc.subject.enDominating Set
dc.titleNeighborhood Complexity and Kernelization for Nowhere Dense Classes of Graphs
dc.typeJournalArticle
dspace.entity.typePublication