2020/08/19 by Christine T. Cheng, Cheng, Christine T., Will Rosenbaum +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Markov Chains and Monte Carlo Methods
paper · pdf · doi:10.48550/arxiv.2008.08479
openalex publication_date 2020/08/19 · openalex created_date 2020/08/24 · openalex updated_date 2026/07/28
In this paper, we consider the problem of counting and sampling structures in graphs. We define a class of "edge universal labeling problems"---which include proper k-colorings, independent sets, and downsets---and describe simple algorithms for counting and uniformly sampling valid labelings of graphs, assuming a path decomposition is given. Thus, we show that several well-studied counting and sampling problems are fixed parameter tractable (FPT) when parameterized by the pathwidth of the input graph. We discuss connections to counting and sampling problems for distributive lattices and, in particular, we give a new FPT algorithm for exactly counting and uniformly sampling stable matchings.