Chlamtac, Eden ;
Dinitz, Michael ;
Konrad, Christian ;
Kortsarz, Guy ;
Rabanca, George
The Densest kSubhypergraph Problem
Abstract
The Densest kSubgraph (DkS) problem, and its corresponding minimization problem Smallest pEdge Subgraph (SpES), have come to play a central role in approximation algorithms. This is due both to their practical importance, and their usefulness as a tool for solving and establishing approximation bounds for other problems. These two problems are not well understood, and it is widely believed that they do not an admit a subpolynomial approximation ratio (although the best known hardness results do not rule this out).
In this paper we generalize both DkS and SpES from graphs to hypergraphs. We consider the Densest kSubhypergraph problem (given a hypergraph (V, E), find a subset W subseteq V of k vertices so as to maximize the number of hyperedges contained in W) and define the Minimum pUnion problem (given a hypergraph, choose p of the hyperedges so as to minimize the number of vertices in their union). We focus in particular on the case where all hyperedges have size 3, as this is the simplest nongraph setting. For this case we provide an O(n^{4(4sqrt{3})/13 + epsilon}) <= O(n^{0.697831+epsilon})approximation (for arbitrary constant epsilon > 0) for Densest kSubhypergraph and an ~O(n^{2/5})approximation for Minimum pUnion. We also give an O(sqrt{m})approximation for Minimum pUnion in general hypergraphs. Finally, we examine the interesting special case of interval hypergraphs (instances where the vertices are a subset of the natural numbers and the hyperedges are intervals of the line) and prove that both problems admit an exact polynomial time solution on these instances.
BibTeX  Entry
@InProceedings{chlamtac_et_al:LIPIcs:2016:6629,
author = {Eden Chlamtac and Michael Dinitz and Christian Konrad and Guy Kortsarz and George Rabanca},
title = {{The Densest kSubhypergraph Problem}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)},
pages = {6:16:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770187},
ISSN = {18688969},
year = {2016},
volume = {60},
editor = {Klaus Jansen and Claire Mathieu and Jos{\'e} D. P. Rolim and Chris Umans},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6629},
URN = {urn:nbn:de:0030drops66298},
doi = {10.4230/LIPIcs.APPROXRANDOM.2016.6},
annote = {Keywords: Hypergraphs, Approximation algorithms}
}
06.09.2016
Keywords: 

Hypergraphs, Approximation algorithms 
Seminar: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)

Issue date: 

2016 
Date of publication: 

06.09.2016 