Abstract
Parameterized Complexity has become quite popular in recent years. Its main motivation stems from the fact that in classical complexity theory almost all s tructural information of the problems under consideration is lost. This is due to the fact that, for example, the time needed to solve a certain problem is measured solely by the size of the input. Parameterized complexity aims at describing some (important) part of the structure of a problem by a paramet er. This idea together with some of its implications has led to new paradigms in designing efficient algorithms and encouraged the development of a wh ole new theory of intractability.
Parameterized Counting Complexity is a fairly new branch of parameterized complexity. The theory of parameterized counting problems is still in its early s tages. Structural issues of this theory, for example, have been considered only by McCartin and Flum and Grohe.
In this thesis we will consider two parts of parameterized complexity in the context of counting problems. The first part will be devoted mainly to paramet erized algorithm design. For decision problems there is an important technique called kernelization that is applied in many parameterized algorith ms. As this technique has yet no analog for counting problems, we will examine ways of applying it to counting problems. This will be the work of chapter 1 and 2. In chapter 3, we will know enough about the application of this technique such that we will be able to develop a formal characterization of it. Fur thermore we will see that this characterization is equivalent to the notion of the tractability of parameterized counting problems.
As certain results from chapter 2 have implications on the structural theory of parameterized counting problems, we will reckon these by proposing a redefi nition of some of its complexity classes.
The second part of this work deals with the intractability of parameterized counting problems. Most importantly, we will see that the parameterized problem of counting bipartite cliques in bipartite graphs is complete for the class #A[1]. To a certain extend, this class can be considered as a parameterized an alog of #P.
Furthermore, in chapter 6, we will prove that the parameterized problems of counting induced cycles and paths are #A[1]-complete as well. Eventually, we wi ll summarize some of the results demonstrated and give an impression of the difference between (classical) complexity theory and parameterized complexity t heory in classifying certain problems.
Keywords:
Parameterized Complexity, Parameterized Counting Problems
Table of Contents
Preliminary Definitions I. Kernelization and The Tractability of Parameterized Counting Problems Time measures for arithmetic computations 1. Vertex Cover 1.1. Applying Buss' Kernelization to p-#VertexCover 1.1.1. Logarithmic Cost Measure 1.2. Crown Rule Reduction 1.3. Linear Programming 1.4. A Note on the Crown Rule Reduction 2. Exploring #FPT 2.1. p-#Cover 2.2. p-card-#HittingSet 2.3. p-#UniqueHittingSet 2.3.1. Applying the Logarithmic Cost Measure Once More 2.4. p-#NearlyAPartition 2.5. p-#BipartiteEdgeDomination 3. Drawing Consequences 3.1. Redefining #W[P] 3.2. Counting Kernelization 3.3. Characterizing #FPT by Counting Kernelizations II. The Intractability of Parameterized Counting Problems 4. An Introduction to Parameterized Intractability 4.1. The Class #A[1] 5. Bipartite Cliques 5.1. The complexity of p-#Hom(C) 5.1.1. Proving the Complexity 5.2. Counting Bipartite Cliques is #A[1]-complete 6. Counting Induced Cycles and Paths 7. A Digression 7.1. Tractable Cases of Counting Matchings Conclusion Guidelines For Future Research Bibliography
