dc.contributor.author 
Somnath Sikdar 

dc.date.accessioned 
20101004T11:53:06Z 

dc.date.available 
20101004T11:53:06Z 

dc.date.issued 
20101004T11:53:06Z 

dc.date.submitted 
2010 

dc.identifier.uri 
http://hdl.handle.net/123456789/236 

dc.description.abstract 
Parameterized complexity is a newly developed subarea of computational complexity that allows for a more refined analysis of problems that are considered hard in the classical sense. In contrast to the classical theory where the complexity of a problem is measured in terms of the input size only, parameterized complexity seeks to exploit the internal structure of a problem. The complexity of a problem in this case is measured not just in terms of the input size but in terms of the input size and, what is called, the parameter.
A parameterized problem is a decision problem whose instances consist of tuples (I, k), where n = I is the size of the input instance and k is the parameter. The goal here is to design algorithms that decide whether (I, k) is a yesinstance in time f(k) ・ nO(1), where f is a computable function of k alone, as against a trivial algorithm with running time nk+O(1). Problems that admit such algorithms are said to be fixedparameter tractable and FPT denotes the class of all fixedparameter tractable problems. The parameter, however, is not unique and often there are several ways in which a problem can be parameterized. This is, in fact, one of the strengths of parameterized complexity as it allows the same problem to be analyzed in different ways depending on the parameter. In this thesis, different parameterizations of NPoptimization problems are studied with the intent of identifying those parameterizations that are feasible and most likely to be useful in practice. A commonly studied parameterization of NPoptimization problems is the standard parameterized version, where the parameter is the solution size. To start with, it is shown that a number of NPoptimization problems, and in particular problems in MAX SNP, have the property that their optimum solution size is bounded below by an unbounded function of the input size. It is also shown that the standard parameterized version of these problems is trivially in FPT and it is argued that the natural parameter in such cases is the deficit between the optimum and the lower bound. That is, one ought to parameterize above the guaranteed lower bound and such a parameterization could be called as an “aboveguarantee” parameterization. One can similarly define parameterizations below a guaranteed upper bound. Then the notion of “tight” lower and upper bounds are introduced and problems for which the aboveguarantee and belowguarantee parameterization with respect to a tight bound is fixedparameter tractable or Whard. It is shown that if one 'parameterize “sufficiently” above or below tight bounds', then these parameterized versions are not in FPT, unless P = NP, for a class of NPoptimization problems. Then related questions in the approximation algorithms setting are considered. It investigates the possibility of obtaining an approximation algorithm for an NPoptimization problem that is an Efraction better than the best known approximation ratio for the problem. Since the bestknown ratio could also be the approximation lowerbound for the problem, the algorithm in question could possibly have a worstcase exponentialtime complexity. But the challenge is to obtain moderately exponentialtime algorithms, whose runtime is possibly a function of E and the inputsize, that
deliver (alpha + Epsilon)approximate solutions. It is discussed that a technique that allows to author to obtain such algorithms for a class of NPoptimization problems.
It is studied that the parameterized complexity (and occasionally the approximability) of a number of concrete problems: Konig Subgraph problems, Unique Coverage and its weighted variant, a version of the Induced Subgraph problem in directed graphs, and the Directed FullDegree Spanning Tree problem. The Konig Subgraph problem is actually a set of problems where the goal is to decide whether a given graph has a Konig subgraph of a certain size. A graph is Konig if the size of a maximum matching equals that of a minimum vertex cover in the graph. Such graphs have been studied extensively from a structural pointofview. In this thesis, the study of the parameterized complexity and approximability of finding Konig subgraphs of a given graph is initiated. It is seen that one of the Konig Subgraph problems, namely Konig Vertex Deletion, is closely related to a wellknown problem in parameterized complexity called Above Guarantee Vertex Cover. While studying the parameterized complexity of Konig Vertex Deletion, it is also observed some interesting structural relations between matchings and vertex covers of a graph. Unique Coverage is a natural maximization version of the wellknown Set Cover problem and has applications in wireless networking and radio broadcasting. It is also a natural generalization of the wellknown Max Cut problem. In this problem given a family of subsets of a finite universe and a nonnegative integer k as parameter, and the goal is to decide whether there exists a subfamily that covers at least k elements exactly once. It shows that this problem is fixedparameter tractable by exhibiting a problem kernel with 4k sets. A weighted variant of it called Budgeted Unique Coverage is also considered and, by an application of the colorcoding technique, shows it to be fixedparameter tractable. Application of colorcoding uses an interesting variation of kperfect
hash families where for every selement subset S of the universe, and for every kelement subset X of S, there exists a function that maps X injectively and maps the remaining elements of S into a different range. Such families are called (k, s)hash families and were studied before in the context of coding theory. The existence of such hash families of size smaller than that of the bestknown Sperfect hash families, is proved using the Probabilistic method. Explicit constructions of such hash families of size promised by the probabilistic method is open.
A version of the Induced Subgraph problem in directed graphs defined as follows: given a hereditary property P on digraphs, an input digraph D and a nonnegative integer k, decide whether D has an induced sub digraph on k vertices with property P. Hereditary properties are completely characterized for which this induced sub graph problem is W[1]complete for two classes of directed graphs: general directed graphs and oriented graphs. Also those properties for which the induced subgraph problem is W[1]complete are characterized for general directed graphs but fixedparameter tractable for oriented graphs.
A directed analog of a problem called Full Degree Spanning Tree is studied which has applications in water distribution networks. This problem is defined as follows: given a digraph D and a nonnegative integer k, decide whether there exists a spanning outtree of D with at least k
vertices of full outdegree. It is shown that this problem is W[1]hard on two important digraph classes: directed acyclic digraphs and strongly connected digraphs. In the dual version, called Reduced Degree Spanning Tree, one has to decide whether there exists a spanning outtree with at most k vertices of reduced outdegree. It is shown that this problem is fixedparameter tractable and admits a problem kernel with at most 8k vertices on strongly connected digraphs and O(k2) vertices on general digraphs. An algorithm is given for this problem on general digraphs with runtime O(5.942k). 
en_US 
dc.publisher.publisher 


dc.relation.isbasedon 
List of Publications:
1. M. Mahajan, V. Raman and S. Sikdar. Parameterizing NPoptimization
Problems Above or Below Guaranteed Values. Journal of Computer and
System Sciences, Volume 75, Issue 2, Pages 137153, 2009. A preliminary
version appeared in Proceedings of the 2nd International Workshop on Pa
rameterized and Exact Computation (IWPEC 2006), SpringerVerlag, LNCS
Volume 4169, Pages 3849, 2006.
2. V. Raman and S. Sikdar. Approximating Beyond the Limit of Approximation.
Manuscript.
3. S. Mishra, V. Raman, S. Saurabh, S. Sikdar and C.R. Subramanian. The
Complexity of K˝onig Subgraph Problems and AboveGuarantee Vertex Cover.
To appear in Algorithmica. This paper was an amalgamation of the following
two papers.
(a) S. Mishra, V. Raman, S. Saurabh, S. Sikdar and C. R. Subramanian.
The Complexity of Finding Subgraphs whose Matching Number Equals
the Vertex Cover Number. In Proceedings of the 18th International
Symposium on Algorithms and Computation (ISAAC 2007), Springer
LNCS Volume 4835, Pages 268279, 2007.
4. (b) S. Mishra, V. Raman, S. Saurabh and S. Sikdar. K˝onig Deletion
Sets and Vertex Covers Above the Matching Size. In Proceedings of
the 19th International Symposium on Algorithms and Computation
(ISAAC 2008), Springer LNCS Volume 5369, Pages 836847, 2008.
5. H. Moser, V. Raman and S. Sikdar. The Complexity of the Unique Coverage
Problem. In Proceedings of the 18th International Symposium on Algorithms
and Computation (ISAAC 2007), Springer LNCS Volume 4835, Pages 621
631, 2007.
6. N. Misra, V. Raman, S. Saurabh and S. Sikdar. Budgeted Unique Coverage
and ColorCoding. In Proceedings of the 4th Computer Science Symposium
in Russia, CSR 2009, Springer LNCS, Volume 5675, Pages 310321, 2009.
7. V. Raman and S. Sikdar. Parameterized Complexity of the Induced Subgraph
Problem in Directed Graphs. Information Processing Letters, Volume 104,
Pages 7985, 2007.
8. D. Lokshtanov, V. Raman, S. Saurabh and S. Sikdar. On the Directed Degree
Preserving Spanning Tree Problem. In Proceedings of the Fourth Interna
tional Workshop on Parameterized and Exact Computation (IWPEC 2009),
Springer LNCS, Volume 5917, Pages 276287, 2009. 
en_US 
dc.subject 
Parameterizations 
en_US 
dc.subject 
HBNI Th 22 
en_US 
dc.title 
Parameterizing from the extremes: Feasible parameterizations of some NPOptimization problems [HBNI Th 22] 
en_US 
dc.type.degree 
Ph.D 
en_US 
dc.type.institution 
HBNI 
en_US 
dc.description.advisor 
Venkatesh Raman 

dc.description.pages 
155p. 
en_US 
dc.type.mainsub 
Computer Science 
en_US 