2026-07-23T22:06:50Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20588 2024-08-23T05:50:28Z ddc:004 open_access

Symmetric-Difference (Degeneracy) and Signed Tree Models Bonnet, Édouard Duron, Julien Sylvester, John Zamaraev, Viktor symmetric difference degeneracy adjacency labeling schemes NP-hardness We introduce a dense counterpart of graph degeneracy, which extends the recently-proposed invariant symmetric difference. We say that a graph has sd-degeneracy (for symmetric-difference degeneracy) at most d if it admits an elimination order of its vertices where a vertex u can be removed whenever it has a d-twin, i.e., another vertex v such that at most d vertices outside {u,v} are neighbors of exactly one of u, v. The family of graph classes of bounded sd-degeneracy is a superset of that of graph classes of bounded degeneracy or of bounded flip-width, and more generally, of bounded symmetric difference. Unlike most graph parameters, sd-degeneracy is not hereditary: it may be strictly smaller on a graph than on some of its induced subgraphs. In particular, every n-vertex graph is an induced subgraph of some O(n²)-vertex graph of sd-degeneracy 1. In spite of this and the breadth of classes of bounded sd-degeneracy, we devise Õ(√n)-bit adjacency labeling schemes for them, which are optimal up to the hidden polylogarithmic factor. This is attained on some even more general classes, consisting of graphs G whose vertices bijectively map to the leaves of a tree T, where transversal edges and anti-edges added to T define the edge set of G. We call such graph representations signed tree models as they extend the so-called tree models (or twin-decompositions) developed in the context of twin-width, by adding transversal anti-edges. While computing the degeneracy of a graph takes linear time, we show that determining its symmetric difference is para-co-NP-complete. This may seem surprising as symmetric difference can serve as a short-sighted first approximation of twin-width, whose computation is para-NP-complete. Indeed, we show that deciding if the symmetric difference of an input graph is at most 8 is co-NP-complete. We also show that deciding if the sd-degeneracy is at most 6 is NP-complete, contrasting with the symmetric difference. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Édouard Bonnet and Julien Duron and John Sylvester and Viktor Zamaraev 2024 Is Part Of LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2024.32 urn:nbn:de:0030-drops-205886 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.32 eng https://creativecommons.org/licenses/by/4.0/legalcode