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


Nikoletseas, Sotiris, Raptopoulos, Christoforos ORCID: 0000-0002-9837-2632 and Spirakis, Paul ORCID: 0000-0001-5396-3749 (2023) MAX CUT in Weighted Random Intersection Graphs and Discrepancy of Sparse Random Set Systems. Algorithmica, 85 (9). pp. 2817-2842.

[img] Text
ISAAC_2021_paper_138 (1).pdf - Author Accepted Manuscript
Download (898kB) | Preview
[img] Text
MAX-CUT.pdf - Open Access published version
Download (465kB) | Preview

Abstract

<jats:title>Abstract</jats:title><jats:p>Let <jats:italic>V</jats:italic> be a set of <jats:italic>n</jats:italic> vertices, <jats:inline-formula><jats:alternatives><jats:tex-math>$${\mathcal M}$$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>M</mml:mi> </mml:math></jats:alternatives></jats:inline-formula> a set of <jats:italic>m</jats:italic> labels, and let <jats:inline-formula><jats:alternatives><jats:tex-math>$${\textbf{R}}$$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>R</mml:mi> </mml:math></jats:alternatives></jats:inline-formula> be an <jats:inline-formula><jats:alternatives><jats:tex-math>$$m \times n$$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>m</mml:mi> <mml:mo>×</mml:mo> <mml:mi>n</mml:mi> </mml:mrow> </mml:math></jats:alternatives></jats:inline-formula> matrix ofs independent Bernoulli random variables with probability of success <jats:italic>p</jats:italic>; columns of <jats:inline-formula><jats:alternatives><jats:tex-math>$${\textbf{R}}$$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>R</mml:mi> </mml:math></jats:alternatives></jats:inline-formula> are incidence vectors of label sets assigned to vertices. A random instance <jats:inline-formula><jats:alternatives><jats:tex-math>$$G(V, E, {\textbf{R}}^T {\textbf{R}})$$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>G</mml:mi> <mml:mo>(</mml:mo> <mml:mi>V</mml:mi> <mml:mo>,</mml:mo> <mml:mi>E</mml:mi> <mml:mo>,</mml:mo> <mml:msup> <mml:mrow> <mml:mi>R</mml:mi> </mml:mrow> <mml:mi>T</mml:mi> </mml:msup> <mml:mi>R</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math></jats:alternatives></jats:inline-formula> of the weighted random intersection graph model is constructed by drawing an edge with weight equal to the number of common labels (namely <jats:inline-formula><jats:alternatives><jats:tex-math>$$[{\textbf{R}}^T {\textbf{R}}]_{v,u}$$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mrow> <mml:mo>[</mml:mo> <mml:msup> <mml:mrow> <mml:mi>R</mml:mi> </mml:mrow> <mml:mi>T</mml:mi> </mml:msup> <mml:mi>R</mml:mi> <mml:mo>]</mml:mo> </mml:mrow> <mml:mrow> <mml:mi>v</mml:mi> <mml:mo>,</mml:mo> <mml:mi>u</mml:mi> </mml:mrow> </mml:msub> </mml:math></jats:alternatives></jats:inline-formula>) between any two vertices <jats:italic>u</jats:italic>, <jats:italic>v</jats:italic> for which this weight is strictly larger than 0. In this paper we study the average case analysis of <jats:sc>Weighted Max Cut</jats:sc>, assuming the input is a weighted random intersection graph, i.e. given <jats:inline-formula><jats:alternatives><jats:tex-math>$$G(V, E, {\textbf{R}}^T {\textbf{R}})$$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>G</mml:mi> <mml:mo>(</mml:mo> <mml:mi>V</mml:mi> <mml:mo>,</mml:mo> <mml:mi>E</mml:mi> <mml:mo>,</mml:mo> <mml:msup> <mml:mrow> <mml:mi>R</mml:mi> </mml:mrow> <mml:mi>T</mml:mi> </mml:msup> <mml:mi>R</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math></jats:alternatives></jats:inline-formula> we wish to find a partition of <jats:italic>V</jats:italic> 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 <jats:inline-formula><jats:alternatives><jats:tex-math>$$G(V, E, {\textbf{R}}^T {\textbf{R}})$$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>G</mml:mi> <mml:mo>(</mml:mo> <mml:mi>V</mml:mi> <mml:mo>,</mml:mo> <mml:mi>E</mml:mi> <mml:mo>,</mml:mo> <mml:msup> <mml:mrow> <mml:mi>R</mml:mi> </mml:mrow> <mml:mi>T</mml:mi> </mml:msup> <mml:mi>R</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math></jats:alternatives></jats:inline-formula> 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, <jats:inline-formula><jats:alternatives><jats:tex-math>$$m=n^{\alpha }, \alpha &lt;1$$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>m</mml:mi> <mml:mo>=</mml:mo> <mml:msup> <mml:mi>n</mml:mi> <mml:mi>α</mml:mi> </mml:msup> <mml:mo>,</mml:mo> <mml:mi>α</mml:mi> <mml:mo>&lt;</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:math></jats:alternatives></jats:inline-formula>), a random partition of the vertices achieves asymptotically optimal cut weight with high probability. Furthermore, in the case <jats:inline-formula><jats:alternatives><jats:tex-math>$$n=m$$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo>=</mml:mo> <mml:mi>m</mml:mi> </mml:mrow> </mml:math></jats:alternatives></jats:inline-formula> and constant average degree (i.e. <jats:inline-formula><jats:alternatives><jats:tex-math>$$p = \frac{\Theta (1)}{n}$$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>p</mml:mi> <mml:mo>=</mml:mo> <mml:mfrac> <mml:mrow> <mml:mi>Θ</mml:mi> <mml:mo>(</mml:mo> <mml:mn>1</mml:mn> <mml:mo>)</mml:mo> </mml:mrow> <mml:mi>n</mml:mi> </mml:mfrac> </mml:mrow> </mml:math></jats:alternatives></jats:inline-formula>), 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 <jats:inline-formula><jats:alternatives><jats:tex-math>$$G(V, E, {\textbf{R}}^T {\textbf{R}})$$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>G</mml:mi> <mml:mo>(</mml:mo> <mml:mi>V</mml:mi> <mml:mo>,</mml:mo> <mml:mi>E</mml:mi> <mml:mo>,</mml:mo> <mml:msup> <mml:mrow> <mml:mi>R</mml:mi> </mml:mrow> <mml:mi>T</mml:mi> </mml:msup> <mml:mi>R</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math></jats:alternatives></jats:inline-formula> and the problem of finding a 2-coloring that achieves minimum discrepancy for a set system <jats:inline-formula><jats:alternatives><jats:tex-math>$$\Sigma $$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>Σ</mml:mi> </mml:math></jats:alternatives></jats:inline-formula> with incidence matrix <jats:inline-formula><jats:alternatives><jats:tex-math>$${\textbf{R}}$$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>R</mml:mi> </mml:math></jats:alternatives></jats:inline-formula> (i.e. minimum imbalance over all sets in <jats:inline-formula><jats:alternatives><jats:tex-math>$$\Sigma $$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>Σ</mml:mi> </mml:math></jats:alternatives></jats:inline-formula>). We exploit this connection by proposing a (weak) bipartization algorithm for the case <jats:inline-formula><jats:alternatives><jats:tex-math>$$m=n, p = \frac{\Theta (1)}{n}$$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>m</mml:mi> <mml:mo>=</mml:mo> <mml:mi>n</mml:mi> <mml:mo>,</mml:mo> <mml:mi>p</mml:mi> <mml:mo>=</mml:mo> <mml:mfrac> <mml:mrow> <mml:mi>Θ</mml:mi> <mml:mo>(</mml:mo> <mml:mn>1</mml:mn> <mml:mo>)</mml:mo> </mml:mrow> <mml:mi>n</mml:mi> </mml:mfrac> </mml:mrow> </mml:math></jats:alternatives></jats:inline-formula> that, when it terminates, its output can be used to find a 2-coloring with minimum discrepancy in a set system with incidence matrix <jats:inline-formula><jats:alternatives><jats:tex-math>$${\textbf{R}}$$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>R</mml:mi> </mml:math></jats:alternatives></jats:inline-formula>. In fact, with high probability, the latter 2-coloring corresponds to a bipartition with maximum cut-weight in <jats:inline-formula><jats:alternatives><jats:tex-math>$$G(V, E, {\textbf{R}}^T {\textbf{R}})$$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>G</mml:mi> <mml:mo>(</mml:mo> <mml:mi>V</mml:mi> <mml:mo>,</mml:mo> <mml:mi>E</mml:mi> <mml:mo>,</mml:mo> <mml:msup> <mml:mrow> <mml:mi>R</mml:mi> </mml:mrow> <mml:mi>T</mml:mi> </mml:msup> <mml:mi>R</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math></jats:alternatives></jats:inline-formula>. Finally, we prove that our (weak) bipartization algorithm terminates in polynomial time, with high probability, at least when <jats:inline-formula><jats:alternatives><jats:tex-math>$$p = \frac{c}{n}, c&lt;1$$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>p</mml:mi> <mml:mo>=</mml:mo> <mml:mfrac> <mml:mi>c</mml:mi> <mml:mi>n</mml:mi> </mml:mfrac> <mml:mo>,</mml:mo> <mml:mi>c</mml:mi> <mml:mo>&lt;</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:math></jats:alternatives></jats:inline-formula>.</jats:p>

Item Type: Article
Divisions: Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User: Symplectic Admin
Date Deposited: 08 Sep 2021 08:33
Last Modified: 04 Apr 2024 14:40
DOI: 10.1007/s00453-023-01121-3
Related URLs:
URI: https://livrepository.liverpool.ac.uk/id/eprint/3136289
Dimensions
Altmetric
CORE (COnnecting REpositories)