Split a graph before actually creating it

Question

Consider a weighted graph $G=(V,E)$ of vertex set $V = \{v_1, ..., v_n\}$ and weighted edge set $E = \{\langle v_i, v_j, w(i,j)\rangle \mid i, j \in 1, ..., n\}$, where $w$ is the function that assign the weight of a certain edge. This function $w$ is symmetric.

Suppose I want to partition the graph into multiple components $G_1, ..., G_k$:

• each component $G_i = (V_i, E_i)$ is such that $V_i \subseteq V$ and $E_i = \{ \langle v_i, v_j, w(i,j) \rangle \mid v_i, v_j \in V_i \} \subseteq E$;
• it holds that $\forall i, j \in 1, ..., k \quad V_i \cap V_j = \varnothing$ and $\bigcup\limits_{i=1}^k V_i = V$;
• the set of edges lost by performing the partition is denoted with $E_\text{lost} = E \setminus (E_1 \cup ... \cup E_k)$ and the sum of lost weights is denoted with $w_\text{lost} = \sum\limits_{\langle v_i,v_j,w_{ij}\rangle \in E_\text{lost}} w_{ij}$

Do exist in the literature heuristics to solve this weighted graph partition problem, running in linear or quasi-linear time in $n$ (*), that minimize $w_\text{lost}$:

1. supposing $w$ is a metric, and
2. supposing $w$ is not a metric, and no further hypothesis holds except for the symmetry?

(*) solutions having quadratic complexity are not accepted

Answer 1

You can't solve this in subquadratic time with any guarantees at all; there is a simple adversary argument. Consider any linear- or quasi-linear-time algorithm, and suppose it outputs the partition $G_1,\dots,G_k$. For any non-trivial* partition, the number of lost edges is more than linear/quasi-linear, so there must exist some lost edge whose weight was not examined by the algorithm; call this edge $e$. It follows that this algorithm will produce the same output regardless of whether the weight on edge $e$ is $0$ or $10^9$ (or some other huge value). As a result, the value of $w_\text{lost}$ can be arbitrarily high.

So, it follows that for any algorithm that runs in linear time or quasi-linear-time, there exists some input where the partition it suggests is horrible.

If you don't care about guarantees, then you can do anything you want. If you want a very simple heuristic, here is one. Randomly sample linearly (or quasi-linearly) many edges, calculate their edge weights, and compute the $k-1$ lowest-weight edges. For each those $k-1$ edges, arbitrarily pick one endpoint, and put it in a group of its own (containing only that one vertex and no other vertices). Finally, put the remaining $n-k+1$ vertices into the final group.

If the algorithm can choose $k$, then the optimal solution is to set $k=1$ and put all vertices into a single group.

• = for an appropriate definition of "non-trivial"