Executive Summary : | Graphs are mathematical structures that represent binary relationships among objects. The objects are called vertices and the relation between them are called edges. Graphs are tremendously powerful in modelling complex structures. Therefore, graph modification problems are of major importance in Computer Science. Typically, an input to such a problem consists of a graph and an integer k, and the objective is to decide whether a maximum of k modifications (vertex deletions, edge deletions/additions, edge contractions) can be made to the graph so that the resulting graph satisfies some predefined properties. The focus of this project is on graph modification problems where the only modification operation allowed is edge contraction. Contractions problems admit easy algorithms whose worst-case running time is an exponential function of input size. However, many of these problems are NP-complete and efficient (polynomial-time) algorithms for solving them are unlikely. Parameterized Complexity provides a framework for confronting this hardness. Here, the primary interest is in designing exponential-time algorithms for NP-complete problems where the exponential factor in the running time is a function depending only on a parameter associated with the input and not the input size. Such algorithms are called fixed-parameter tractable (FPT) algorithms or parameterized algorithms and a problem is said to be FPT if it has an FPT algorithm. Analogous to the NP-completeness theory in classical complexity, there is a fixed-parameter intractability theory (using the notion of W[i]-completeness) that is used to rule out FPT algorithms in parameterized complexity. In this project, I propose to address fundamental questions regarding classical and parameterized complexity of contraction problems. The questions posed are divided into three categories. The first and third sets of questions talk about the property required as a result of contractions while the second set of questions deals with problems on restricted graph classes. As the problems proposed in this project are fundamental, I believe that solving them would advance the understanding of the complexity of the problem of finding contractions in graphs. |