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

Nikoletseas, S, Raptopoulos, C and Spirakis, P ORCID: 0000-0001-5396-3749 (2021) MAX CUT in Weighted Random Intersection Graphs and Discrepancy of Sparse Random Set Systems. Leibniz International Proceedings in Informatics, LIPIcs, 212.

Text [2nd revision] MaxCutDiscrepancy_20230307.pdf - Author Accepted Manuscript Available under License Creative Commons Attribution. Download (872kB) | Preview

Abstract

Let V be a set of n vertices, M a set of m labels, and let R be an m × n matrix of independent Bernoulli random variables with probability of success p; columns of R are incidence vectors of label sets assigned to vertices. A random instance G(V, E, RT R) of the weighted random intersection graph model is constructed by drawing an edge with weight equal to the number of common labels (namely [RT R]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, RT R) 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, RT R) 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, RT R) and the problem of finding a 2-coloring that achieves minimum discrepancy for a set system Σ with incidence matrix R (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 R. In fact, with high probability, the latter 2-coloring corresponds to a bipartition with maximum cut-weight in G(V, E, RT R). Finally, we prove that our (weak) bipartization algorithm terminates in polynomial time, with high probability, at least when p = nc , c < 1.

Item Type:	Article
Divisions:	Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User:	Symplectic Admin
Date Deposited:	27 Jun 2023 10:20
Last Modified:	27 Mar 2024 13:33
DOI:	10.4230/LIPIcs.ISAAC.2021.28
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3171318