# Item

ITEM ACTIONSEXPORT

Released

Thesis

#### Exact algorithms for s-club finding and related problems

##### MPS-Authors

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)

da_schaefer.pdf

(Preprint), 638KB

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

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

##### Abstract

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.