Novel Algorithms for Assessing the Number of Solutions in Graph Problems

Counting the number of subgraphs, or graph patterns, of a certain kind is at the heart of network analysis, data mining and graph-based machine learning. Some fundamental counting problems on graphs include counting perfect matchings, Eulerian tours, st-paths, and maximal cliques, to name a few. In this thesis, we propose a novel algorithmic technique alternative to counting, which we call assessment. In an assessment problem, we are given a counting problem instance and a threshold z, and we are asked to find whether the count is at least z. In other words, instead of answering the counting question “How many?”, we answer the assessment question “Are there enough?”. We present assessment algorithms that are efficient both in theory and in practice for several fundamental graph counting problems. Specifically, we show that assessment can be performed in time polynomial in z and in the input size n for two main classes of problems, yielding several implications: - If the counting problems are polynomial-time, this provides an assessment algorithm that is faster than counting when z is suitably chosen. We discuss this case for counting the number of Eulerian tours in directed graphs. - If the counting problems are instead #P-complete, we obtain a polynomial time assessment algorithm whenever z is polynomial in n, whereas no polynomial time counting algorithm exists. We show how to obtain this kind of assessment for counting Eulerian tours and st-paths in undirected graphs. Not only are our assessment algorithms theoretically better than counting for certain values of z, but our experimental results on real-world datasets also show that they outperform state-of-the-art counting algorithms in practice. Indeed, such practical efficiency, together with some lower bounding techniques employed by the algorithms, lead us to believe that assessment could be performed in o(z) time, under suitable assumption for the value of z. Overall, assessment is a versatile technique, providing algorithms that are efficient in theory and can be engineered on real-world data sets, for polynomial-time and #P-complete counting problems alike.