The Complexity of Counting in Sparse, Regular, and Planar Graphs

Salil Vadhan

Type: Article

Publication Date: 2001-01-01

Citations: 266

DOI: https://doi.org/10.1137/s0097539797321602

View Publication

Locations

SIAM Journal on Computing - View

Similar Works

Action	Title	Year	Authors
+	FPTAS for Counting Monotone CNF	2013	Jing‐Cheng Liu Pinyan Lu
+ PDF Chat	FPTAS for Counting Monotone CNF	2014	Jing‐Cheng Liu Pinyan Lu
+	Large induced subgraphs via triangulations and CMSO	2013	Fedor V. Fomin Ioan Todinca Yngve Villanger
+	The complexity of counting colourings and independent sets in sparse graphs and hypergraphs	2000	Catherine Greenhill
+ PDF Chat	Large Induced Subgraphs via Triangulations and CMSO	2015	Fedor V. Fomin Ioan Todinca Yngve Villanger
+	Weighted Counting of Matchings in Unbounded-Treewidth Graph Families	2022	Antoine Amarilli Mikaël Monet
+	Guest column	2011	X. Chen
+	Approximate Counting	1995	Rajeev Motwani Prabhakar Raghavan
+ PDF Chat	Exponential Time Complexity of Weighted Counting of Independent Sets	2010	Christian Herzog
+ PDF Chat	Faster exponential-time algorithms for approximately counting independent sets	2021	Leslie Ann Goldberg John Lapinskas David Richerby
+	Faster Exponential-time Algorithms for Approximately Counting Independent Sets	2020	Leslie Ann Goldberg John Lapinskas David Richerby
+	A computational proof of complexity of some restricted counting problems	2010	Jin‐Yi Cai Pinyan Lu Mingji Xia
+	Faster Exponential-time Algorithms for Approximately Counting Independent Sets	2020	Leslie Ann Goldberg John Lapinskas David Richerby
+ PDF Chat	Block Interpolation: A Framework for Tight Exponential-Time Counting Complexity	2015	Radu Curticapean
+	The Complexity of Planar Counting Problems	1998	Harry B. Hunt Madhav Marathe Venkatesh Babu Radhakrishnan Richard E. Stearns
+	Approximate counting of regular hypergraphs via switchings	2013	Andrzej Dudek Alan Frieze Andrzej Ruciński Matas Šileikis
+ PDF Chat	Approximately Counting $H$-Colorings is $\#\mathrm{BIS}$-Hard	2016	Andreas Galanis Leslie Ann Goldberg Mark Jerrum
+	Counting Matchings in Graphs	1987	Edward J. Farrell
+	Counting Problems in Parameterized Complexity.	2019	Radu Curticapean
+	Large induced subgraphs via triangulations and CMSO	2013	Fedor V. Fomin Ioan Todinca Yngve Villanger

Works That Cite This (177)

Action	Title	Year	Authors
+ PDF Chat	Counting independent sets in cocomparability graphs	2018	Martin Dyer Haiko Müller
+	Counting <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si9.gif" display="inline" overflow="scroll"><mml:mn>4</mml:mn><mml:mo>×</mml:mo><mml:mn>4</mml:mn></mml:math> matrix partitions of graphs	2016	Martin Dyer Leslie Ann Goldberg David Richerby
+	Complexity Dichotomies for Counting Problems	2017	Jin‐Yi Cai Xi Chen
+	On Planar Toeplitz Graphs	2012	Reinhardt Euler Tudor Zamfirescu
+ PDF Chat	A Method for Computing the Merrifield–Simmons Index on Benzenoid Systems	2022	Guillermo De Ita Luna Pedro Bello Meliza Contreras
+ PDF Chat	Planar graphical models which are easy	2010	Vladimir Chernyak Michael Chertkov
+	On Threshold Models over Finite Networks	2012	Elie M. Adam Munther A. Dahleh Asuman Ozdaglar
+	Sampling Eulerian orientations of triangular lattice graphs	2007	Páidí Creed
+	Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model.	2020	Nima Anari Kuikui Liu Shayan Oveis Gharan
+ PDF Chat	Approximate Counting of Matchings in Sparse Uniform Hypergraphs	2013	Marek Karpiński Andrzej Ruciński Edyta Szymańska

Works Cited by This (31)

Action	Title	Year	Authors
+	The Markov chain Monte Carlo method: an approach to approximate counting and integration	1996	Mark Jerrum Alistair Sinclair
+ PDF Chat	Two-dimensional monomer-dimer systems are computationally intractable	1990	Mark Jerrum
+	Dimer Statistics and Phase Transitions	1963	Piet Kasteleyn
+	Graph orientations with no sink and an approximation for a hard case of #SAT	1997	Russ Bubley Martin Dyer
+	On Markov Chains for Independent Sets	2000	Martin Dyer Catherine Greenhill
+	On Unapproximable Versions of $NP$-Complete Problems	1996	David Zuckerman
+	Analyzing Glauber dynamics by comparison of Markov chains	2000	Dana Randall Prasad Tetali
+	The complexity of computing the permanent	1979	Leslie G. Valiant
+	On Approximation Algorithms for # P	1985	Larry Stockmeyer
+	Polynomial-Time Approximation Algorithms for the Ising Model	1993	Mark Jerrum Alistair Sinclair