MSc thesis of Ioannis Nemparis
Counting complexity: compressed Hamming distance, vertex covers, and recent highlights
Supervisor: Aristeidis T. Pagourtzis
This thesis is made up of 3 parts, all related to counting algorithms, counting complexity, counting methods and counting results considered milestones. The first part tackles the Compressed Hamming Distance (C.H.D) Problem. The Hamming distance between two strings of equal length is the number of positions at which the corresponding symbols are different. The problem is trivial if the strings are given uncompressed. However, the strings may be given in a compressed form, known as Straight Line Programs (SLPs). Our target is to compute the Hamming Distance given only the compressed form of the strings (which can be up to exponentially shorter). This problem was shown to be #P-complete. We propose two algorithms for the problem. An exponential time one, for exact counting and a second one trying to achieve some kind of approximation. In the second part we first survey results that are already known in the literature: counting vertex covers in lines, cycles and complete binary tree graphs. Moreover, we design algorithms for two additional problems on lines and cycles. First, the problem of determining in what fraction of the total number of covers does some specific node takes part. Second, the problem of counting exactly the number of covers of any specific size. Finally, we show a hardness result for counting covers larger than the minimum on general graphs. The last part consists of a brief review of some celebrated results on counting complexity and the intuition behind the methods that led to them. We close by a reference to the connection of counting complexity with other areas of computational complexity theory.
Defended: May 4, 2015.