 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: https://drops.dagstuhl.de/opus/volltexte/2021/15461/
 Go to the corresponding LIPIcs Volume Portal

### MAX CUT in Weighted Random Intersection Graphs and Discrepancy of Sparse Random Set Systems

 pdf-format:

### 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

DROPS-Home | Fulltext Search | Imprint | Privacy 