Planted Models for the Densest \(k\)-Subgraph Problem

Given an undirected graph \(G\), the Densest \(k\)-subgraph problem (DkS) asks to compute a set \(S \subset V\) of cardinality \(\left\lvert S\right\rvert \leq k\) such that the weight of edges inside \(S\) is maximized. This is a fundamental NP-hard problem whose approximability, inspite of many de...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2020-11
Main Authors: Khanna, Yash, Anand, Louis
Format: Article
Language:English
Subjects:
Algorithms
Approximation
Graph theory
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Given an undirected graph \(G\), the Densest \(k\)-subgraph problem (DkS) asks to compute a set \(S \subset V\) of cardinality \(\left\lvert S\right\rvert \leq k\) such that the weight of edges inside \(S\) is maximized. This is a fundamental NP-hard problem whose approximability, inspite of many decades of research, is yet to be settled. The current best known approximation algorithm due to Bhaskara et al. (2010) computes a \(\mathcal{O}\left({n^{1/4 + \epsilon}}\right)\) approximation in time \(n^{\mathcal{O}\left(1/\epsilon\right)}\), for any \(\epsilon > 0\). We ask what are some "easier" instances of this problem? We propose some natural semi-random models of instances with a planted dense subgraph, and study approximation algorithms for computing the densest subgraph in them. These models are inspired by the semi-random models of instances studied for various other graph problems such as the independent set problem, graph partitioning problems etc. For a large range of parameters of these models, we get significantly better approximation factors for the Densest \(k\)-subgraph problem. Moreover, our algorithm recovers a large part of the planted solution.
ISSN:2331-8422