Integrating and Sampling Cuts in Bounded Treewidth Graphs

被引：2

作者：

Bezakova, Ivona ^{[1
]}

Chambers, Erin W. ^{[2
]}

Fox, Kyle ^{[3
]}

机构：

[1] Rochester Inst Technol, Dept Comp Sci, Rochester, NY 14623 USA

[2] St Louis Univ, Dept Comp Sci & Math, St Louis, MO 63103 USA

[3] Duke Univ, Dept Comp Sci, Durham, NC 27708 USA

来源：

ADVANCES IN THE MATHEMATICAL SCIENCES | 2016年 / 6卷

基金：

美国国家科学基金会;

关键词：

Treewidth; Minimum cuts; Algorithms; MONADIC 2ND-ORDER LOGIC; MARKOV-CHAINS; TREE-WIDTH; COMPLEXITY; TIME;

D O I：

10.1007/978-3-319-34139-2_20

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

In this paper, we consider the problem of evaluating (s, t)-cuts in a bounded treewidth graph. In particular, we show how to compute the partition function for weighted cuts of the graph, i.e., the total weight of all (s, t)-cuts where the weight of a single cut is the product of its edge weights. This method can also easily be adapted to work with additive weights for the cost of a cut. We also present a method for sampling a cut proportional to its weight in linear time. Computing the partition function is # P-hard for general graphs, and our sampling algorithm is simple enough to prove useful is several application areas. Finally, we discuss an alternative method for sampling cuts that uses Markov chains and show that, in the worst case, its mixing time is exponential in the size of the graph even when the graph has bounded treewidth.

引用

页码：401 / 415

页数：15

共 19 条

[1] COMPLEXITY OF FINDING EMBEDDINGS IN A K-TREE
ARNBORG, S
CORNEIL, DG
PROSKUROWSKI, A
[J]. SIAM JOURNAL ON ALGEBRAIC AND DISCRETE METHODS, 1987, 8 (02): : 277 - 284
[2] CALCULATING BOUNDS ON REACHABILITY AND CONNECTEDNESS IN STOCHASTIC NETWORKS
BALL, MO
PROVAN, JS
[J]. NETWORKS, 1983, 13 (02) : 253 - 278
[3] Counting and sampling minimum (s, t)-cuts in weighted planar graphs in polynomial time
Bezakova, Ivona
Friedlander, Adam J.
[J]. THEORETICAL COMPUTER SCIENCE, 2012, 417 : 2 - 11
[4] BODLAENDER HL, 1988, LECT NOTES COMPUT SC, V317, P105
[5] A linear-time ie algorithm for finding three-decompositions of small treewidth
Bodlaender, HL
[J]. SIAM JOURNAL ON COMPUTING, 1996, 25 (06) : 1305 - 1317
[6] Boykov Y, 2006, HANDBOOK OF MATHEMATICAL MODELS IN COMPUTER VISION, P79, DOI 10.1007/0-387-28831-7_5
[7] Chambers EW, 2013, PROCEEDINGS OF THE TWENTY-NINETH ANNUAL SYMPOSIUM ON COMPUTATIONAL GEOMETRY (SOCG'13), P249
[8] Colbourn CJ., 1991, Annals Operations Research, V33, P1, DOI DOI 10.1007/BF02061656
[9] On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
Courcelle, B
Makowsky, JA
Rotics, U
[J]. DISCRETE APPLIED MATHEMATICS, 2001, 108 (1-2) : 23 - 52
[10] THE MONADIC 2ND-ORDER LOGIC OF GRAPHS .1. RECOGNIZABLE SETS OF FINITE GRAPHS
COURCELLE, B
[J]. INFORMATION AND COMPUTATION, 1990, 85 (01) : 12 - 75

← 1 2 →