Counting and sampling problems on Eulerian graphs
Counting and sampling problems on Eulerian graphs
复制标题
欧拉图的计数和采样问题
DOI：
--
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
P. Creed
中科院分区：
文献类型：
--
作者：
P. Creed
在本文中，我们考虑了在Eulerian图上定义的两组组合结构：Eulerian方向和Euler Tours。我们对计数的计算问题（计算集合中的元素数量）和采样（生成集合的随机元素）感兴趣。具体而言，我们对何时存在有效算法来计数或采样任一集的元素的问题感兴趣。许多类别的平面晶格的欧拉取向具有实际意义，因为它们对应于统计物理学中研究的某些模型的配置。在1992年，Mihail和Winkler表明，计算一般欧拉图的欧拉取向是＃p-Complete，并证明了对欧拉尔方向进行采样的问题可以简化为可探索的问题，即对二键图的完美匹配进行采样。我们提供了一个证明，当输入仅限于平面图时，此问题仍然是#PComplete，并分析了一种自然算法，用于生成上述平面晶格之一的随机欧拉方向。此外，我们通过展示无限类别的平面图迅速混合的平面图范围，取得了一些进展，该算法始终需要花费指数的时间来收敛。事实证明，计算无方向图的欧拉旅游的问题与欧拉方向相比，对分析的不太适合分析。尽管已经知道，可以在多项式时间内计算出任何有向图的欧拉旅行的数量，直到最近对计算无方向图的Euler Tours的复杂性知之甚少。 Brightwell和Winkler表明，这个问题在2005年是＃P-Complete，除了一些非常简单的示例，例如，串联 - Parellel图，没有已知的可行情况，也没有任何充分的理由相信问题是棘手。此外，尽管尝试了几次未成功的尝试，但在近似性问题上没有取得任何进展。实际上，由于很早就解决了精确计数的复杂性，因此这一问题被认为是近似计数中最困难的开放问题之一。通过考虑随机输入模型，我们能够证明一种非常简单的算法可以在预期的多项式时间内进行样品或大约计算几乎每个D-IN/D-OUL的有向图的Euler Tours。然后，我们提出一些部分结果，以表明该算法可用于采样或大约计算预期多项式时间中几乎每2D规则图的Euler巡回演出。我们还提供了一些经验证据，以支持获得此结果所需的未经证实的猜想。作为这项工作的一个方面，我们获得了随机2D指定图的欧拉方向数量的分布的渐近表征。
In this thesis we consider two sets of combinatorial structures defined on an Eulerian graph: the Eulerian orientations and Euler tours. We are interested in the computational problems of counting (computing the number of elements in the set) and sampling (generating a random element of the set). Specifically, we are interested in the question of when there exists an efficient algorithm for counting or sampling the elements of either set. The Eulerian orientations of a number of classes of planar lattices are of practical significance as they correspond to configurations of certain models studied in statistical physics. In 1992 Mihail and Winkler showed that counting Eulerian orientations of a general Eulerian graph is #P-complete and demonstrated that the problem of sampling an Eulerian orientation can be reduced to the tractable problem of sampling a perfect matching of a bipartite graph. We present a proof that this problem remains #Pcomplete when the input is restricted to being a planar graph, and analyse a natural algorithm for generating random Eulerian orientations of one of the afore-mentioned planar lattices. Moreover, we make some progress towards classifying the range of planar graphs on which this algorithm is rapidly mixing by exhibiting an infinite class of planar graphs for which the algorithm will always take an exponential amount of time to converge. The problem of counting the Euler tours of undirected graphs has proven to be less amenable to analysis than that of Eulerian orientations. Although it has been known for many years that the number of Euler tours of any directed graph can be computed in polynomial time, until recently very little was known about the complexity of counting Euler tours of an undirected graph. Brightwell and Winkler showed that this problem is #P-complete in 2005 and, apart from a few very simple examples, e.g., series-parellel graphs, there are no known tractable cases, nor are there any good reasons to believe the problem to be intractable. Moreover, despite several unsuccessful attempts, there has been no progress made on the question of approximability. Indeed, this problem was considered to be one of the more difficult open problems in approximate counting since long before the complexity of exact counting was resolved. By considering a randomised input model, we are able to show that a very simple algorithm can sample or approximately count the Euler tours of almost every d-in/d-out directed graph in expected polynomial time. Then, we present some partial results towards showing that this algorithm can be used to sample or approximately count the Euler tours of almost every 2d-regular graph in expected polynomial time. We also provide some empirical evidence to support the unproven conjecture required to obtain this result. As a sideresult of this work, we obtain an asymptotic characterisation of the distribution of the number of Eulerian orientations of a random 2d-regular graph.