The densest κ-subhypergraph problem

Eden Chlamtác, Michael Dinitz, Christian Konrad, Guy Kortsarz, George Rabanca

Research output: Chapter in Book/Report/Conference proceedingConference contribution

5 Citations (Scopus)

Abstract

The Densest κ-Subgraph (DκS) problem, and its corresponding minimization problem Smallest p-Edge 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 k-Subhypergraph problem (given a hypergraph (V,E), find a subset W C V of k vertices so as to maximize the number of hyperedges contained in W) and define the Minimum p-Union 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 non-graph setting. For this case we provide an O(n4 (4-√3)/13+ϵ) ≤ O(n0.697831+ϵ)-approximation (for arbitrary constant ϵ > 0) for Densest κ-Subhypergraph and an O(√m)-approximation for Minimum p-Union. We also give an O(p m)-Approximation for Minimum p-Union 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.

Original languageEnglish (US)
Title of host publicationApproximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 19th International Workshop, APPROX 2016 and 20th International Workshop, RANDOM 2016
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Volume60
ISBN (Electronic)9783959770187
DOIs
StatePublished - Sep 1 2016
Event19th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2016 and the 20th International Workshop on Randomization and Computation, RANDOM 2016 - Paris, France
Duration: Sep 7 2016Sep 9 2016

Other

Other19th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2016 and the 20th International Workshop on Randomization and Computation, RANDOM 2016
CountryFrance
CityParis
Period9/7/169/9/16

Fingerprint

Approximation algorithms
Hardness
Polynomials

All Science Journal Classification (ASJC) codes

  • Software

Cite this

Chlamtác, E., Dinitz, M., Konrad, C., Kortsarz, G., & Rabanca, G. (2016). The densest κ-subhypergraph problem. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 19th International Workshop, APPROX 2016 and 20th International Workshop, RANDOM 2016 (Vol. 60). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2016.6
Chlamtác, Eden ; Dinitz, Michael ; Konrad, Christian ; Kortsarz, Guy ; Rabanca, George. / The densest κ-subhypergraph problem. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 19th International Workshop, APPROX 2016 and 20th International Workshop, RANDOM 2016. Vol. 60 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2016.
@inproceedings{ece647dbbbb74aa08e624956b2b04e95,
title = "The densest κ-subhypergraph problem",
abstract = "The Densest κ-Subgraph (DκS) problem, and its corresponding minimization problem Smallest p-Edge 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 k-Subhypergraph problem (given a hypergraph (V,E), find a subset W C V of k vertices so as to maximize the number of hyperedges contained in W) and define the Minimum p-Union 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 non-graph setting. For this case we provide an O(n4 (4-√3)/13+ϵ) ≤ O(n0.697831+ϵ)-approximation (for arbitrary constant ϵ > 0) for Densest κ-Subhypergraph and an O(√m)-approximation for Minimum p-Union. We also give an O(p m)-Approximation for Minimum p-Union 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.",
author = "Eden Chlamt{\'a}c and Michael Dinitz and Christian Konrad and Guy Kortsarz and George Rabanca",
year = "2016",
month = "9",
day = "1",
doi = "10.4230/LIPIcs.APPROX-RANDOM.2016.6",
language = "English (US)",
volume = "60",
booktitle = "Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 19th International Workshop, APPROX 2016 and 20th International Workshop, RANDOM 2016",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
address = "Germany",

}

Chlamtác, E, Dinitz, M, Konrad, C, Kortsarz, G & Rabanca, G 2016, The densest κ-subhypergraph problem. in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 19th International Workshop, APPROX 2016 and 20th International Workshop, RANDOM 2016. vol. 60, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 19th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2016 and the 20th International Workshop on Randomization and Computation, RANDOM 2016, Paris, France, 9/7/16. https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2016.6

The densest κ-subhypergraph problem. / Chlamtác, Eden; Dinitz, Michael; Konrad, Christian; Kortsarz, Guy; Rabanca, George.

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 19th International Workshop, APPROX 2016 and 20th International Workshop, RANDOM 2016. Vol. 60 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2016.

Research output: Chapter in Book/Report/Conference proceedingConference contribution

TY - GEN

T1 - The densest κ-subhypergraph problem

AU - Chlamtác, Eden

AU - Dinitz, Michael

AU - Konrad, Christian

AU - Kortsarz, Guy

AU - Rabanca, George

PY - 2016/9/1

Y1 - 2016/9/1

N2 - The Densest κ-Subgraph (DκS) problem, and its corresponding minimization problem Smallest p-Edge 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 k-Subhypergraph problem (given a hypergraph (V,E), find a subset W C V of k vertices so as to maximize the number of hyperedges contained in W) and define the Minimum p-Union 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 non-graph setting. For this case we provide an O(n4 (4-√3)/13+ϵ) ≤ O(n0.697831+ϵ)-approximation (for arbitrary constant ϵ > 0) for Densest κ-Subhypergraph and an O(√m)-approximation for Minimum p-Union. We also give an O(p m)-Approximation for Minimum p-Union 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.

AB - The Densest κ-Subgraph (DκS) problem, and its corresponding minimization problem Smallest p-Edge 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 k-Subhypergraph problem (given a hypergraph (V,E), find a subset W C V of k vertices so as to maximize the number of hyperedges contained in W) and define the Minimum p-Union 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 non-graph setting. For this case we provide an O(n4 (4-√3)/13+ϵ) ≤ O(n0.697831+ϵ)-approximation (for arbitrary constant ϵ > 0) for Densest κ-Subhypergraph and an O(√m)-approximation for Minimum p-Union. We also give an O(p m)-Approximation for Minimum p-Union 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.

UR - http://www.scopus.com/inward/record.url?scp=84990855923&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84990855923&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.APPROX-RANDOM.2016.6

DO - 10.4230/LIPIcs.APPROX-RANDOM.2016.6

M3 - Conference contribution

AN - SCOPUS:84990855923

VL - 60

BT - Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 19th International Workshop, APPROX 2016 and 20th International Workshop, RANDOM 2016

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

ER -

Chlamtác E, Dinitz M, Konrad C, Kortsarz G, Rabanca G. The densest κ-subhypergraph problem. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 19th International Workshop, APPROX 2016 and 20th International Workshop, RANDOM 2016. Vol. 60. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. 2016 https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2016.6