Další formáty:
BibTeX
LaTeX
RIS
@inproceedings{1799080, author = {Balabán, Jakub and Hliněný, Petr}, address = {Dagstuhl}, booktitle = {International Symposium on Parameterized and Exact Computation (IPEC)}, doi = {http://dx.doi.org/10.4230/LIPIcs.IPEC.2021.6}, edition = {214}, editor = {Golovach, Petr A. and Zehavi, Meirav}, keywords = {twin-width; digraph; poset; FO model checking; contraction sequence}, howpublished = {elektronická verze "online"}, language = {eng}, location = {Dagstuhl}, isbn = {978-3-95977-216-7}, pages = {"6:1"-"6:13"}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, title = {Twin-Width is Linear in the Poset Width}, url = {https://arxiv.org/abs/2106.15337}, year = {2021} }
TY - JOUR ID - 1799080 AU - Balabán, Jakub - Hliněný, Petr PY - 2021 TI - Twin-Width is Linear in the Poset Width PB - Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik CY - Dagstuhl SN - 9783959772167 KW - twin-width KW - digraph KW - poset KW - FO model checking KW - contraction sequence UR - https://arxiv.org/abs/2106.15337 N2 - Twin-width is a new parameter informally measuring how diverse are the neighbourhoods of the graph vertices, and it extends also to other binary relational structures, e.g. to digraphs and posets. It was introduced just very recently, in 2020 by Bonnet, Kim, Thomasse and Watrigant. One of the core results of these authors is that FO model checking on graph classes of bounded twin-width is in FPT. With that result, they also claimed that posets of bounded width have bounded twin-width, thus capturing prior result on FO model checking of posets of bounded width in FPT. However, their translation from poset width to twin-width was indirect and giving only a very loose double-exponential bound. We prove that posets of width d have twin-width at most 9d with a direct and elegant argument, and show that this bound is asymptotically tight. Specially, for posets of width 2 we prove that in the worst case their twin-width is also equal 2. These two theoretical results are complemented with straightforward algorithms to construct the respective contraction sequence for a given poset. ER -
BALABÁN, Jakub a Petr HLINĚNÝ. Twin-Width is Linear in the Poset Width. Online. In Golovach, Petr A. and Zehavi, Meirav. \textit{International Symposium on Parameterized and Exact Computation (IPEC)}. 214. vyd. Dagstuhl: Schloss Dagstuhl -- Leibniz-Zentrum f$\{\backslash$''u$\}$r Informatik, 2021, s.~''6:1''-''6:13'', 13 s. ISBN~978-3-95977-216-7. Dostupné z: https://dx.doi.org/10.4230/LIPIcs.IPEC.2021.6.
|