论文标题
同构简洁表示的二分法
A dichotomy for succinct representations of homomorphisms
论文作者
论文摘要
在两个有限的关系结构之间计算同构的任务$ \ MATHCAL {a} $和$ \ MATHCAL {B} $是一个有很多应用程序的问题。由于集合$ \ peratatorAname {hom}（\ Mathcal {a}，\ Mathcal {B}）$所有同构的$可能非常大，因此具有一种简洁的方式，尤其是一种使我们能够执行有效的枚举和计数的方法，这可能是非常有用的。 这样做的一种简单而强大的方法是使用Union and Cartesian产品分解$ \ operatotorName {hom}（\ Mathcal {a}，\ Mathcal {B}）$。在数据库理论的背景下，Olteanu和Zavodny引入了此类数据结构，称为D-pressentations。他们的结果还暗示，如果左侧结构的树宽$ \ MATHCAL {a} $是有界的，则可以在多项式时间中找到多项式大小的D-代表。我们表明，对于有界的arity结构，这是最佳的：如果树宽是无限的，则在某些情况下，任何D-代表的大小都是超级分类的。在途中，我们开发了用于证明D-代表大小的下限的工具，尤其是我们定义了适合这种情况的减少概念，并证明了图中所有$ k $ cliques的D-代表大小的几乎紧密的下限。
The task of computing homomorphisms between two finite relational structures $\mathcal{A}$ and $\mathcal{B}$ is a well-studied question with numerous applications. Since the set $\operatorname{Hom}(\mathcal{A},\mathcal{B})$ of all homomorphisms may be very large having a method of representing it in a succinct way, especially one which enables us to perform efficient enumeration and counting, could be extremely useful. One simple yet powerful way of doing so is to decompose $\operatorname{Hom}(\mathcal{A},\mathcal{B})$ using union and Cartesian product. Such data structures, called d-representations, have been introduced by Olteanu and Zavodny in the context of database theory. Their results also imply that if the treewidth of the left-hand side structure $\mathcal{A}$ is bounded, then a d-representation of polynomial size can be found in polynomial time. We show that for structures of bounded arity this is optimal: if the treewidth is unbounded then there are instances where the size of any d-representation is superpolynomial. Along the way we develop tools for proving lower bounds on the size of d-representations, in particular we define a notion of reduction suitable for this context and prove an almost tight lower bound on the size of d-representations of all $k$-cliques in a graph.
