Abstract
We consider the problem of sampling connected induced subgraphs of a given input graph G. Our first result is that an efficient algorithm to approximately sample connected induced subgraphs of a given size (the size is specified in the input) does not exist unless RP = NP. We then focus on the problem of approximately sampling connected induced subgraphs with a bias, more precisely we consider a distribution where the probability of a connected subgraph induced by \(S\subseteq V(G)\) is proportional to \(\lambda ^{|S|}\). When the input graph G has maximum degree d we identify a threshold \(\lambda _d=\frac{(d-1)^{(d-1)}}{d^d}\). For \(0< \lambda < \lambda _d\) there exists a trivial efficient sampler for the problem, and for \(\lambda _d<\lambda <1\) an efficient approximate sampler does not exist unless RP = NP. Finally, we show local Markov chains are unlikely to be effective at approximately sampling connected subgraphs.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Aldous, D., Fill, J.A.: Reversible Markov chains and random walks on graphs (2002). https://www.stat.berkeley.edu/users/aldous/RWG/book.pdf. Unfinished monograph, recompiled 2014
Baskerville, K., Grassberger, P., Paczuski, M.: Graph animals, subgraph sampling, and motif search in large networks. Phys. Rev. E 76(3), 036107, 13 (2007)
Frieze, A.: Notes on Counting and rapidly mixing Markov chains. http://www.math.cmu.edu/~af1p/Mixing.html
Grochow, J.A., Kellis, M.: Network motif discovery using subgraph enumeration and symmetry-breaking. In: Speed, T., Huang, H. (eds.) RECOMB 2007. LNCS, vol. 4453, pp. 92–106. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-71681-5_7
Guo, H., Jerrum, M.: A polynomial-time approximation algorithm for all-terminal network reliability. In: Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, Prague, Czech Republic, 9–13 July 2018, pp. 68:1–68:12 (2018)
Ising, E.: Contribution to the theory of ferromagnetism. Z. Phys. 31, 253–258 (1925)
Jerrum, M., Meeks, K.: The parameterised complexity of counting connected subgraphs and graph motifs. J. Comput. Syst. Sci. 81(4), 702–716 (2015)
Jung, K., Shah, D.: Inference in binary pair-wise Markov random fields through self-avoiding walks. arXiv e-prints p. cs/0610111 (2006)
Kangas, K., Kaski, P., Koivisto, M., Korhonen, J.H.: On the number of connected sets in bounded degree graphs. In: Kratsch, D., Todinca, I. (eds.) WG 2014. LNCS, vol. 8747, pp. 336–347. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-12340-0_28
Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W. (eds.) Complexity of Computer Computations, pp. 85–103. Plenum Press, Boston (1972)
Kashtan, N., Milo, R., Itzkovitz, S., Alon, U.: Efficient sampling algorithm for estimating subgraph concentrations and detecting network motifs. Bioinformatics 20(11), 1746–1758 (2004)
Lenz, W.: Beitrag zum Verständnis der magnetischen Erscheinungen in festen Körpern. Z. Phys. 21, 613–615 (1920)
Lu, X., Bressan, S.: Sampling connected induced subgraphs uniformly at random. In: Ailamaki, A., Bowers, S. (eds.) SSDBM 2012. LNCS, vol. 7338, pp. 195–212. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-31235-9_13
Łuczak, T., Vigoda, E.: Torpid mixing of the Wang-Swendsen-Kotecký algorithm for sampling colorings. J. Discret. Algorithms 3(1), 92–100 (2005)
Mossel, E., Weitz, D., Wormald, N.: On the hardness of sampling independent sets beyond the tree threshold. Probab. Theory Relat. Fields 143(3), 401–439 (2009)
Patel, V., Regts, G.: Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials. SIAM J. Comput. 46(6), 1893–1919 (2017)
Patel, V., Regts, G.: Computing the number of induced copies of a fixed graph in a bounded degree graph. Algorithmica 81(5), 1844–1858 (2018)
Garey, M.R., Johnson, D.: The rectilinear steiner tree problem is NP-complete. SIAM J. Appl. Math. 32, 826–834 (1977)
Savoie, W., et al.: Phototactic supersmarticles. Artif. Life Robot. 23(4), 459–468 (2018). https://doi.org/10.1007/s10015-018-0473-7
Sinclair, A.: Algorithms for Random Generation and Counting: A Markov Chain Approach. Birkhauser Verlag, Basel (1993)
Sly, A.: Computational transition at the uniqueness threshold. In: Proceedings of the 51st IEEE Annual Symposium on Foundations of Computer Science, FOCS, pp. 287–296 (2010)
Stanley, R.P.: Enumerative Combinatorics: vol. 2, 1st edn. Cambridge University Press, New York (1999)
Vince, A.: Counting connected sets and connected partitions of a graph. Australas. J. Comb. 67(2), 281–293 (2017)
Weitz, D.: Counting independent sets up to the tree threshold. In: Proceedings of the 38th Annual ACM Symposium on Theory of Computing, STOC, pp. 140–149. ACM, New York (2006)
White, K., Farber, M., Pulleyblank, W.: Steiner trees, connected domination and strongly chordal graphs. Networks 15(1), 109–124 (1985)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Read-McFarland, A., Štefankovič, D. (2020). The Hardness of Sampling Connected Subgraphs. In: Kohayakawa, Y., Miyazawa, F.K. (eds) LATIN 2020: Theoretical Informatics. LATIN 2021. Lecture Notes in Computer Science(), vol 12118. Springer, Cham. https://doi.org/10.1007/978-3-030-61792-9_37
Download citation
DOI: https://doi.org/10.1007/978-3-030-61792-9_37
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-61791-2
Online ISBN: 978-3-030-61792-9
eBook Packages: Computer ScienceComputer Science (R0)