2012 | OriginalPaper | Buchkapitel
Finding Dense Subgraphs of Sparse Graphs
verfasst von : Christian Komusiewicz, Manuel Sorge
Erschienen in: Parameterized and Exact Computation
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We investigate the computational complexity of the
Densest-
k
-Subgraph
(
D
k
S
) problem, where the input is an undirected graph
G
= (
V
,
E
) and one wants to find a subgraph on exactly
k
vertices with a maximum number of edges. We extend previous work on
D
k
S
by studying its parameterized complexity. On the positive side, we show that, when fixing some constant minimum density
μ
of the sought subgraph,
D
k
S
becomes fixed-parameter tractable with respect to either of the parameters maximum degree and
h
-index of
G
. Furthermore, we obtain a fixed-parameter algorithm for
D
k
S
with respect to the combined parameter “degeneracy of
G
and |
V
| −
k
”. On the negative side, we find that
D
k
S
is W[1]-hard with respect to the combined parameter “solution size
k
and degeneracy of
G
”. We furthermore strengthen a previous hardness result for
D
k
S
[Cai, Comput. J., 2008] by showing that for every fixed
μ
, 0 <
μ
< 1, the problem of deciding whether
G
contains a subgraph of density at least
μ
is W[1]-hard with respect to the parameter |
V
| −
k
.