1 Search Results for "Khanna, Yash"

Document

DOI: 10.4230/LIPIcs.FSTTCS.2020.27

Planted Models for the Densest k-Subgraph Problem

Authors: Yash Khanna and Anand Louis

Published in: LIPIcs, Volume 182, 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)

Abstract

Given an undirected graph G, the Densest k-subgraph problem (DkS) asks to compute a set S ⊂ V of cardinality |S| ≤ 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 𝒪(n^{1/4 + ε}) approximation in time n^{𝒪(1/ε)}, for any ε > 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.

Cite as

Yash Khanna and Anand Louis. Planted Models for the Densest k-Subgraph Problem. In 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 182, pp. 27:1-27:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{khanna_et_al:LIPIcs.FSTTCS.2020.27,
  author =	{Khanna, Yash and Louis, Anand},
  title =	{{Planted Models for the Densest k-Subgraph Problem}},
  booktitle =	{40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)},
  pages =	{27:1--27:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-174-0},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{182},
  editor =	{Saxena, Nitin and Simon, Sunil},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2020.27},
  URN =		{urn:nbn:de:0030-drops-132682},
  doi =		{10.4230/LIPIcs.FSTTCS.2020.27},
  annote =	{Keywords: Densest k-Subgraph, Semi-Random models, Planted Models, Semidefinite Programming, Approximation Algorithms, Beyond Worst Case Analysis}
}

Refine by Author
1 Khanna, Yash
1 Louis, Anand

Refine by Classification
1 Theory of computation → Discrete optimization
1 Theory of computation → Graph algorithms analysis
1 Theory of computation → Semidefinite programming

Refine by Keyword
1 Approximation Algorithms
1 Beyond Worst Case Analysis
1 Densest k-Subgraph
1 Planted Models
1 Semi-Random models
Show More...

Refine by Type
1 document

Refine by Publication Year
1 2020

1 Search Results for "Khanna, Yash"

Planted Models for the Densest k-Subgraph Problem

Abstract

Cite as

Thanks for your feedback!

Could not send message