License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2021.28
URN: urn:nbn:de:0030-drops-154612
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/15461/
Nikoletseas, Sotiris ;
Raptopoulos, Christoforos ;
Spirakis, Paul
MAX CUT in Weighted Random Intersection Graphs and Discrepancy of Sparse Random Set Systems
Abstract
Let V be a set of n vertices, M a set of m labels, and let ? be an m × n matrix of independent Bernoulli random variables with probability of success p; columns of ? are incidence vectors of label sets assigned to vertices. A random instance G(V, E, ?^T ?) of the weighted random intersection graph model is constructed by drawing an edge with weight equal to the number of common labels (namely [?^T ?]_{v,u}) between any two vertices u, v for which this weight is strictly larger than 0. In this paper we study the average case analysis of Weighted Max Cut, assuming the input is a weighted random intersection graph, i.e. given G(V, E, ?^T ?) we wish to find a partition of V into two sets so that the total weight of the edges having exactly one endpoint in each set is maximized.
In particular, we initially prove that the weight of a maximum cut of G(V, E, ?^T ?) is concentrated around its expected value, and then show that, when the number of labels is much smaller than the number of vertices (in particular, m = n^α, α < 1), a random partition of the vertices achieves asymptotically optimal cut weight with high probability. Furthermore, in the case n = m and constant average degree (i.e. p = Θ(1)/n), we show that with high probability, a majority type randomized algorithm outputs a cut with weight that is larger than the weight of a random cut by a multiplicative constant strictly larger than 1. Then, we formally prove a connection between the computational problem of finding a (weighted) maximum cut in G(V, E, ?^T ?) and the problem of finding a 2-coloring that achieves minimum discrepancy for a set system Σ with incidence matrix ? (i.e. minimum imbalance over all sets in Σ). We exploit this connection by proposing a (weak) bipartization algorithm for the case m = n, p = Θ(1)/n that, when it terminates, its output can be used to find a 2-coloring with minimum discrepancy in a set system with incidence matrix ?. In fact, with high probability, the latter 2-coloring corresponds to a bipartition with maximum cut-weight in G(V, E, ?^T ?). Finally, we prove that our (weak) bipartization algorithm terminates in polynomial time, with high probability, at least when p = c/n, c < 1.
BibTeX - Entry
@InProceedings{nikoletseas_et_al:LIPIcs.ISAAC.2021.28,
author = {Nikoletseas, Sotiris and Raptopoulos, Christoforos and Spirakis, Paul},
title = {{MAX CUT in Weighted Random Intersection Graphs and Discrepancy of Sparse Random Set Systems}},
booktitle = {32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
pages = {28:1--28:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-214-3},
ISSN = {1868-8969},
year = {2021},
volume = {212},
editor = {Ahn, Hee-Kap and Sadakane, Kunihiko},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/15461},
URN = {urn:nbn:de:0030-drops-154612},
doi = {10.4230/LIPIcs.ISAAC.2021.28},
annote = {Keywords: Random Intersection Graphs, Maximum Cut, Discrepancy}
}
|
Keywords: |
|
Random Intersection Graphs, Maximum Cut, Discrepancy |
|
Collection: |
|
32nd International Symposium on Algorithms and Computation (ISAAC 2021) |
|
Issue Date: |
|
2021 |
|
Date of publication: |
|
30.11.2021 |
