On classes of bounded tree rank, their interpretations, and efficient sparsification
arxiv(2024)
摘要
Graph classes of bounded tree rank were introduced recently in the context of
the model checking problem for first-order logic of graphs. These graph classes
are a common generalization of graph classes of bounded degree and bounded
treedepth, and they are a special case of graph classes of bounded expansion.
We introduce a notion of decomposition for these classes and show that these
decompositions can be efficiently computed. Also, a natural extension of our
decomposition leads to a new characterization and decomposition for graph
classes of bounded expansion (and an efficient algorithm computing this
decomposition).
We then focus on interpretations of graph classes of bounded tree rank. We
give a characterization of graph classes interpretable in graph classes of tree
rank 2. Importantly, our characterization leads to an efficient
sparsification procedure: For any graph class C interpretable in a
efficiently bounded graph class of tree rank at most 2, there is a polynomial
time algorithm that to any G ∈ C computes a (sparse) graph H from a fixed
graph class of tree rank at most 2 such that G = I(H) for a fixed
interpretation I. To the best of our knowledge, this is the first efficient
"interpretation reversal" result that generalizes the result of Gajarský et
al. [LICS 2016], who showed an analogous result for graph classes interpretable
in classes of graphs of bounded degree.
更多查看译文
AI 理解论文
溯源树
样例
生成溯源树,研究论文发展脉络
Chat Paper
正在生成论文摘要