论文标题
具有有界路径的图形的简单计数和采样算法
Simple Counting and Sampling Algorithms for Graphs with Bounded Pathwidth
论文作者
论文摘要
在本文中，我们考虑了图中计数和采样结构的问题。我们定义了一类“ Edge通用标记问题” ---包括适当的$ K $ - 色，独立集和下调 - 并描述用于计数和均匀采样图的有效标记的简单算法，假设给出了路径分解。因此，我们表明，当通过输入图的路径宽进行参数化时，几个研究的计数和采样问题是固定的参数可行（fpt）。我们讨论了与分配格的计数和采样问题的连接，尤其是我们提供了一种新的FPT算法，以精确计数和均匀地采样稳定的匹配。
In this paper, we consider the problem of counting and sampling structures in graphs. We define a class of "edge universal labeling problems"---which include proper $k$-colorings, independent sets, and downsets---and describe simple algorithms for counting and uniformly sampling valid labelings of graphs, assuming a path decomposition is given. Thus, we show that several well-studied counting and sampling problems are fixed parameter tractable (FPT) when parameterized by the pathwidth of the input graph. We discuss connections to counting and sampling problems for distributive lattices and, in particular, we give a new FPT algorithm for exactly counting and uniformly sampling stable matchings.
