License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2016.44
URN: urn:nbn:de:0030-drops-68149
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6814/
Kawase, Yasushi ;
Miyauchi, Atsushi
The Densest Subgraph Problem with a Convex/Concave Size Function
Abstract
Given an edge-weighted undirected graph G = (V, E, w), the density of S subseteq V is defined as w(S)/|S|, where w(S) is the sum of weights of the edges in the subgraph induced by S. The densest subgraph problem asks for S subseteq V that maximizes the density w(S)/|S|. The problem has received significant attention recently because it can be solved exactly in polynomial time. However, the densest subgraph problem has a drawback; it may happen that the obtained subset is too large or too small in comparison with the desired size of the output.
In this study, we address the size issue by generalizing the density of S subseteq V. Specifically, we introduce the f -density of S subseteq V, which is defined as w(S)/f (|S|), where f : Z geq 0 to R geq 0 is a monotonically non-decreasing function. In the f-densest subgraph problem (f-DS), we are asked to find S subseteq V that maximizes the f-density w(S)/f (|S|). Although f-DS does not explicitly specify the size of the output subset of vertices, we can handle the above size issue using a convex size function f or a concave size function f appropriately. For f-DS with convex function f, we propose a nearly-linear-time algorithm with a provable approximation guarantee. In particular, for f-DS with f(x) = x^alpha (alpha in [1, 2]), our algorithm has an approximation ratio of 2 ยท n^{(alpha-1)(2-alpha)}. On the other hand, for f-DS with concave function f , we propose a linear-programming-based polynomial-time exact algorithm. It should be emphasized that this algorithm obtains not only an optimal solution to the problem but also subsets of vertices corresponding to the extreme points of the upper convex hull of {(|S|, w(S)) | S subseteq V }, which we refer to as the dense frontier points. We also propose a flow-based combinatorial exact algorithm for unweighted graphs that runs in O(n^3) time. Finally, we propose a nearly-linear-time 3-approximation algorithm.
BibTeX - Entry
@InProceedings{kawase_et_al:LIPIcs:2016:6814,
author = {Yasushi Kawase and Atsushi Miyauchi},
title = {{The Densest Subgraph Problem with a Convex/Concave Size Function}},
booktitle = {27th International Symposium on Algorithms and Computation (ISAAC 2016)},
pages = {44:1--44:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-026-2},
ISSN = {1868-8969},
year = {2016},
volume = {64},
editor = {Seok-Hee Hong},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6814},
URN = {urn:nbn:de:0030-drops-68149},
doi = {10.4230/LIPIcs.ISAAC.2016.44},
annote = {Keywords: graphs, dense subgraph extraction, densest subgraph problem, approxi- mation algorithms}
}
|
Keywords: |
|
graphs, dense subgraph extraction, densest subgraph problem, approxi- mation algorithms |
|
Collection: |
|
27th International Symposium on Algorithms and Computation (ISAAC 2016) |
|
Issue Date: |
|
2016 |
|
Date of publication: |
|
07.12.2016 |
