Advertisement
Published in:
2012 | OriginalPaper | Chapter
Finding Dense Subgraphs of Sparse Graphs
Authors : Christian Komusiewicz, Manuel Sorge
Published in: Parameterized and Exact Computation
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. 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
.