Help Privacy Policy Disclaimer
  Advanced SearchBrowse





Exact algorithms for s-club finding and related problems

There are no MPG-Authors in the publication available
External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)

(Preprint), 638KB

Supplementary Material (public)
There is no public supplementary material available

Schäfer, A. (2009). Exact algorithms for s-club finding and related problems. Diploma Thesis, Friedrich-Schiller-University, Jena.

Cite as: https://hdl.handle.net/11858/00-001M-0000-000E-72CF-5
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.