Seven Ways of Deciding Whether Most Vertex Sets Cover a Graph

Abstract

Given an undirected graph G = (V, E), it is a difficult problem (complete for #P) to determine the total number of vertex covers C ⊆ V of G. In contrast, deciding whether most C cover a graph (meaning, at least half of all possible C ⊆ V are covers) turns out to be tractable. Intriguingly, this can be proved in very different ways, namely using search trees from fpt theory, using backdoor sets from sat solving, using randomized sampling in conjunction with gaps in probability spectra, using algorithmic meta- theorems, using forbidden minors from graph minor theory, using forbidden subgraphs in conjunction with bounded tree-depth, and using the construction of algorithmically simple well-quasi-orderings. The present paper explains and celebrates how this diverse crowd of approaches, ideas, and methods, which Theoretical Computer Science has developed over the last fifty years, can be applied to solve a basic problem like “decide whether most vertex sets cover a given graph,” but also to solve many (at least superficially) harder counting–threshold problems.