Kawase, Yasushi ;
Miyauchi, Atsushi
The Densest Subgraph Problem with a Convex/Concave Size Function
Abstract
Given an edgeweighted 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 nondecreasing function. In the fdensest subgraph problem (fDS), we are asked to find S subseteq V that maximizes the fdensity w(S)/f (S). Although fDS 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 fDS with convex function f, we propose a nearlylineartime algorithm with a provable approximation guarantee. In particular, for fDS with f(x) = x^alpha (alpha in [1, 2]), our algorithm has an approximation ratio of 2 · n^{(alpha1)(2alpha)}. On the other hand, for fDS with concave function f , we propose a linearprogrammingbased polynomialtime 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 flowbased combinatorial exact algorithm for unweighted graphs that runs in O(n^3) time. Finally, we propose a nearlylineartime 3approximation 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:144:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770262},
ISSN = {18688969},
year = {2016},
volume = {64},
editor = {SeokHee Hong},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6814},
URN = {urn:nbn:de:0030drops68149},
doi = {10.4230/LIPIcs.ISAAC.2016.44},
annote = {Keywords: graphs, dense subgraph extraction, densest subgraph problem, approxi mation algorithms}
}
07.12.2016
Keywords: 

graphs, dense subgraph extraction, densest subgraph problem, approxi mation algorithms 
Seminar: 

27th International Symposium on Algorithms and Computation (ISAAC 2016)

Issue date: 

2016 
Date of publication: 

07.12.2016 