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

Rankwidth meets stability*

Uproszczony widok
dc.abstract.enWe study two notions of being well-structured for classes of graphs that are inspired by classic model theory. A class of graphs is monadically stable if it is impossible to define arbitrarily long linear orders in vertex-colored graphs from using a fixed first-order formula. Similarly, monadic dependence corresponds to the impossibility of defining all graphs in this way. Examples of monadically stable graph classes are nowhere dense classes, which provide a robust theory of sparsity. Examples of monadically dependent classes are classes of bounded rankwidth (or equivalently, bounded cliquewidth), which can be seen as a dense analog of classes of bounded treewidth. Thus, monadic stability and monadic dependence extend classical structural notions for graphs by viewing them in a wider, model-theoretical context. We explore this emerging theory by proving the following: 1) A class of graphs is a first-order transduction of a class with bounded treewidth if and only if has bounded rankwidth and a stable edge relation (i.e. graphs from exclude some half-graph as a semi-induced subgraph). 2) If a class of graphs is monadically dependent and not monadically stable, then has in fact an unstable edge relation. As a consequence, we show that classes with bounded rankwidth excluding some half-graph as a semi-induced subgraph are linearly χ-bounded. Our proofs are effective and lead to polynomial time algorithms.
dc.affiliationUniwersytet Warszawski
dc.conference.countryStany Zjednoczone
dc.conference.datefinish2021-01-13
dc.conference.datestart2021-01-10
dc.conference.placeAlexandria, Virginia (Virtual Conference)
dc.conference.seriesACM/SIAM Symposium on Discrete Algorithms
dc.conference.seriesACM/SIAM Symposium on Discrete Algorithms
dc.conference.seriesshortcutSODA
dc.conference.shortcutSODA 2021
dc.conference.weblinkhttps://www.siam.org/conferences/cm/conference/soda21
dc.contributor.authorPilipczuk, Michał
dc.contributor.authorSiebertz, Sebastian
dc.contributor.authorRabinovich, Roman
dc.contributor.authorMendez, Patrice Ossona de
dc.contributor.authorNešetřil, Jaroslav
dc.date.accessioned2024-01-25T18:46:29Z
dc.date.available2024-01-25T18:46:29Z
dc.date.issued2021
dc.description.financePublikacja bezkosztowa
dc.identifier.doi10.1137/1.9781611976465.120
dc.identifier.urihttps://repozytorium.uw.edu.pl//handle/item/117859
dc.identifier.weblinkhttps://epubs.siam.org/doi/10.1137/1.9781611976465.120
dc.languageeng
dc.pbn.affiliationcomputer and information sciences
dc.relation.pages1-20
dc.rightsClosedAccess
dc.sciencecloudnosend
dc.titleRankwidth meets stability*
dc.typeJournalArticle
dspace.entity.typePublication