非表示:
キーワード:
-
要旨:
The Clique problem is one of the best-studied problems in computer science.
However, there exist only few studies concerning the important Clique generalization,
called the s-Club problem. In particular there have been no intensive
investigations with respect to the parameterized complexity of this problem.
In this thesis we show that s-Club is fixed-parameter tractable with respect
to the number of vertices in the solution. In terms of polynomial time data
reduction, we show that s-Club does not admit a polynomial many-to-one kernel.
In contrast to that we give a cubic-vertex Turing kernel. In this context we also
show an interesting connection to the approximation of a solution for s-Club,
and give a combined algorithm to exploit this connection. Furthermore we study
the complexity of s-Club on some restricted graph classes.
In order to obtain efficient fixed-parameter algorithm, it is often useful to change
the parameterization. Therefore, we analyze s-Club with a dual parameterization,
which we define as the s-Club Vertex Deletion problem. We show that
this problem is fixed-parameter tractable with respect to the number of vertices
in the solution.
We also introduce the s-Club Cluster Vertex Deletion problem, which is
a generalization of the Cluster Vertex Deletion problem. For this problem
we show NP-completeness and fixed-parameter tractability with respect to the
combined parameter number of vertices in the solution and s.
