The problem of counting the number of solutions of a DNF formula, also called #DNF, is a fundamental problem in artificial intelligence with applications in diverse domains ranging from network reliability to probabil...
详细信息
The problem of counting the number of solutions of a DNF formula, also called #DNF, is a fundamental problem in artificial intelligence with applications in diverse domains ranging from network reliability to probabilistic databases. Owing to the intractability of the exact variant, efforts have focused on the design of approximate techniques for #DNF. Consequently, several fully polynomial randomized approximation schemes (FPRASs) based on Monte Carlo techniques have been proposed. Recently, it was discovered that hashing-based techniques too lend themselves to FPRASs for #DNF. Despite significant improvements, the complexity of the hashing-based FPRAS is still worse than that of the best Monte Carlo FPRAS by polylog factors. Two questions were left unanswered in previous works: Can the complexity of the hashing-based techniques be improved? How do the various approaches stack up against each other empirically? In this paper, we first propose a new search procedure for the hashing-based FPRAS that removes the polylog factors from its time complexity. We then present the first empirical study of runtime behavior of different FPRASs for #DNF. The result of our study produces a nuanced picture. First of all, we observe that there is no single best algorithm that outperforms all others for all classes of formulas and input parameters. Second, we observe that the algorithm with one of the worst time complexities solves the largest number of benchmarks.
We investigate the complexity of counting Eulerian tours (#ET) and its variations from two perspectives-the complexity of exact counting and the complexity w.r.t. approximation-preserving reductions (AP-reductions, Dy...
详细信息
We investigate the complexity of counting Eulerian tours (#ET) and its variations from two perspectives-the complexity of exact counting and the complexity w.r.t. approximation-preserving reductions (AP-reductions, Dyer et al., Algorithmica 38(3):471-500, 2004). We prove that #ET is #P-complete even for planar 4-regular graphs. A closely related problem is that of counting A-trails (#A-trails) in graphs with rotational embedding schemes (so called maps). Kotzig (Theory of Graphs, Proc. Colloq., Tihany, 1966, pp. 219-230, Academic Press, San Diego, 1968) showed that #A-trails can be computed in polynomial time for 4-regular plane graphs (embedding in the plane is equivalent to giving a rotational embedding scheme). We show that for 4-regular maps the problem is #P-hard. Moreover, we show that from the approximation viewpoint #A-trails in 4-regular maps captures the essence of #ET, that is, we give an AP-reduction from #ET in general graphs to #A-trails in 4-regular maps. The reduction uses a fast mixing result for a card shuffling problem (Wilson, Ann. Appl. Probab. 14(1):274-325, 2004).
Jerrum, Sinclair, and Vigoda [J. ACM, 51 (2004), pp. 671-697] showed that the permanent of any square matrix can be estimated in polynomial time. This computation can be viewed as approximating the partition function ...
详细信息
Jerrum, Sinclair, and Vigoda [J. ACM, 51 (2004), pp. 671-697] showed that the permanent of any square matrix can be estimated in polynomial time. This computation can be viewed as approximating the partition function of edge-weighted matchings in a bipartite graph. Equivalently, this may be viewed as approximating the partition function of vertex-weighted independent sets in the line graph of a bipartite graph. Line graphs of bipartite graphs are perfect graphs and are known to be precisely the class of (claw, diamond, odd hole)-free graphs. So how far does the result of Jerrum, Sinclair, and Vigoda extend? We first show that it extends to (claw, odd hole)-free graphs, and then show that it extends to the even larger class of (fork, odd hole)-free graphs. Our techniques are based on graph decompositions, which have been the focus of much recent work in structural graph theory, and on structural results of Chvatal and Sbihi [J. Combin. Theory Ser. B, 44 (1988)], Maffray and Reed [J. Combin. Theory Ser. B, 75 (1999)], and Lozin and Milanic [J. Discrete Algorithms, 6 (2008), pp. 595-604].
暂无评论