图中欧拉路径的快速评估及其应用

《ACM Transactions on Knowledge Discovery from Data》：Fast Assessment of Eulerian Trails in Graphs with Applications

评估有向图欧拉路径数量下界问题，提出基于树数据结构的优化算法，将时间复杂度从O(n^ω)降至O(m·min{z, #ET(G)})，实验显示效率提升两个数量级。

　　

摘要

在图中枚举或计算组合对象是数据挖掘中的一个基本任务。我们考虑评估有向图中欧拉路径数量的问题，该问题表述如下：给定一个有向图 $G=(V,\mathrm{E)}$，其中包含 $|V|=n$ 个节点和 $|E|=m$ 条边，以及一个整数 $z$，我们需要判断欧拉路径的数量 $\#ET\left(G\right)$ 是否至少为 $z$。这个问题在数据隐私、计算生物学、数据压缩和交通网络等多个领域都有应用。目前，从业者通常使用著名的BEST定理来解决这个问题，但实际上BEST定理只是计算欧拉路径的数量，而不是仅仅判断欧拉路径的数量是否大于或等于某个阈值 $\#ET\left(G\right)$。不幸的是，这种解决方案需要执行 O(nω 次算术运算，其中 $\mathrm{\omega <<mn>2.373</mn>}$ 表示“矩阵乘法指数”。由于在大多数现实世界的图中，边的数量 $m$ 与节点的数量 $n$ 相当，且 $z$ 在实际应用中是有限的，因此算法上的挑战在于：对于某些特定的 $m$ 和 $z$ 值，我们能否更快地解决这个问题？我们希望设计一种组合算法来评估欧拉路径的数量是否大于或等于某个阈值 $\#ET\left(G\right)$，这种算法不依赖于BEST定理，并且其计算成本能够根据 $m$ 和 $z$ 进行预测。我们通过以下方法应对这一挑战：首先介绍一种通用的算法框架来评估（和枚举）欧拉路径；然后引入一种新的树状数据结构以减少该框架中的迭代次数；最后，通过进一步的组合学洞察来改进算法，使其在最坏情况下的时间复杂度达到