Spanning tree constrained determinantal point processes are hard to (approximately) evaluate. (English) Zbl 1525.60062
Summary: We consider determinantal point processes (DPPs) constrained by spanning trees. Given a graph \(G = ( V , E )\) and a positive semi-definite matrix \(\mathbf{A}\) indexed by \(E\), a spanning-tree DPP defines a distribution such that we draw \(S \subseteq E\) with probability \(\propto \det ( \mathbf{A}_S )\) only if \(S\) induces a spanning tree. We prove #P-hardness of computing the normalizing constant for spanning-tree DPPs and provide an approximation-preserving reduction from the mixed discriminant, for which FPRAS is not known. We show similar results for DPPs constrained by forests.
MSC:
| 60G55 | Point processes (e.g., Poisson, Cox, Hawkes processes) |
| 05C05 | Trees |
| 60-08 | Computational methods for problems pertaining to probability theory |
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
References:
| [1] | Raja Hafiz Affandi, Emily B. Fox, Ryan P. Adams, Ben Taskar, Learning the parameters of determinantal point process kernels, in: ICML, 2014, pp. 1224-1232. |
| [2] | Andrzejak, Artur, An algorithm for the Tutte polynomials of graphs of bounded treewidth, Discrete Math., 190, 1-3, 39-54 (1998) · Zbl 0955.05101 |
| [3] | Annan, James D., A randomised approximation algorithm for counting the number of forests in dense graphs, Combin. Probab. Comput., 3, 273-283 (1994) · Zbl 0809.05086 |
| [4] | Bodlaender, Hans L., A partial \(k\)-arboretum of graphs with bounded treewidth, Theoret. Comput. Sci., 209, 1-2, 1-45 (1998) · Zbl 0912.68148 |
| [5] | Borodin, Alexei; Rains, Eric M., Eynard-Mehta theorem, Schur process, and their Pfaffian analogs, J. Stat. Phys., 121, 3-4, 291-317 (2005) · Zbl 1127.82017 |
| [6] | L. Elisa Celis, Amit Deshpande, Tarun Kathuria, Damian Straszak, Nisheeth K. Vishnoi, On the complexity of constrained determinantal point processes, in: APPROX/RANDOM, 2017, pp. 36:1-36:22. · Zbl 1467.68062 |
| [7] | L. Elisa Celis, Vijay Keswani, Damian Straszak, Amit Deshpande, Tarun Kathuria, Nisheeth K. Vishnoi, Fair and diverse DPP-based data summarization, in: ICML, 2018, pp. 715-724. |
| [8] | Courcelle, Bruno; Makowsky, Johann A.; Rotics, Udi, On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic, Discrete Appl. Math., 108, 1-2, 23-52 (2001) · Zbl 0972.05023 |
| [9] | Cygan, Marek; Fomin, Fedor V.; Kowalik, Łukasz; Lokshtanov, Daniel; Marx, Dániel; Pilipczuk, Marcin; Pilipczuk, Michał; Saurabh, Saket, Parameterized Algorithms (2015), Springer · Zbl 1334.90001 |
| [10] | Dagum, Paul; Luby, Michael, Approximating the permanent of graphs with large factors, Theoret. Comput. Sci., 102, 2, 283-305 (1992) · Zbl 0766.68056 |
| [11] | Dyer, Martin; Goldberg, Leslie Ann; Greenhill, Catherine; Jerrum, Mark, The relative complexity of approximate counting problems, Algorithmica, 38, 3, 471-500 (2004) · Zbl 1138.68424 |
| [12] | Edmonds, Jack, Systems of distinct representatives and linear algebra, J. Res. Natl. Bur. Stand., 71B, 241-245 (1967) · Zbl 0178.03002 |
| [13] | Edmonds, Jack, Submodular functions, matroids, and certain polyhedra, (Combinatorial Structures and Their Applications (1970)), 69-87 · Zbl 0268.05019 |
| [14] | Wai Shing Fung, Ramesh Hariharan, Nicholas J.A. Harvey, Debmalya Panigrahi, A general framework for graph sparsification, in: STOC, 2011, pp. 71-80. · Zbl 1288.68118 |
| [15] | Boqing Gong, Wei-Lun Chao, Kristen Grauman, Fei Sha, Diverse sequential subset selection for supervised video summarization, in: NIPS, 2014, pp. 2069-2077. |
| [16] | Leonid Gurvits, On the complexity of mixed discriminants and related problems, in: MFCS, 2005, pp. 447-458. · Zbl 1156.68402 |
| [17] | Takanori Hayashi, Takuya Akiba, Yuichi Yoshida, Efficient algorithms for spanning tree centrality, in: IJCAI, 2016, pp. 3733-3739. |
| [18] | Jerrum, Mark; Sinclair, Alistair; Vigoda, Eric, A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries, J. ACM, 51, 4, 671-697 (2004) · Zbl 1204.65044 |
| [19] | Jerrum, Mark R.; Valiant, Leslie G.; Vazirani, Vijay V., Random generation of combinatorial structures from a uniform distribution, Theoret. Comput. Sci., 43, 169-188 (1986) · Zbl 0597.68056 |
| [20] | Kirchhoff, Gustav, Ueber die auflösung der gleichungen, auf welche man bei der untersuchung der linearen vertheilung galvanischer ströme geführt wird, Ann. Phys., 148, 12, 497-508 (1847) |
| [21] | Alex Kulesza, Ben Taskar, \(k\)-DPPs: Fixed-size determinantal point processes, in: ICML, 2011, pp. 1193-1200. |
| [22] | Kulesza, Alex; Taskar, Ben, Determinantal point processes for machine learning, Found. Trends Mach. Learn., 5, 2-3, 123-286 (2012) · Zbl 1278.68240 |
| [23] | Macchi, Odile, The coincidence approach to stochastic point processes, Adv. Appl. Probab., 7, 1, 83-122 (1975) · Zbl 0366.60081 |
| [24] | Noble, Steven D., Evaluating the Tutte polynomial for graphs of bounded tree-width, Combin. Probab. Comput., 7, 3, 307-321 (1998) · Zbl 0917.05072 |
| [25] | Robertson, Neil; Seymour, Paul D., Graph minors. II. algorithmic aspects of tree-width, J. Algorithms, 7, 3, 309-322 (1986) · Zbl 0611.05017 |
| [26] | Schrijver, Alexander, Theory of Linear and Integer Programming, Wiley-Interscience Series in Discrete Mathematics and Optimization (1999), Wiley · Zbl 0665.90063 |
| [27] | Schur, Issai, Bemerkungen zur theorie der beschränkten bilinearformen mit unendlich vielen veränderlichen, J. Reine Angew. Math., 1911, 140, 1-28 (1911) · JFM 42.0367.01 |
| [28] | Valiant, Leslie G., The complexity of computing the permanent, Theoret. Comput. Sci., 8, 2, 189-201 (1979) · Zbl 0415.68008 |
| [29] | Vertigan, Dirk L.; Welsh, Dominic J. A., The computational complexity of the Tutte plane: The bipartite case, Combin. Probab. Comput., 1, 2, 181-187 (1992) · Zbl 0793.05091 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
