1
$\begingroup$

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

$\endgroup$
8
  • $\begingroup$ Do you have any hypothesis on the function $w$? If not, I am afraid that you cannot do better that a random selection of edges… $\endgroup$
    – Nathaniel
    Mar 7, 2022 at 15:40
  • $\begingroup$ @Nathaniel Thank you for the comment! The function is symmetric but it's not necessarily a metric, actually. However, if some solution exists that works supposing $w$ is a metric, it might be worth showing it, so I've edited the question $\endgroup$
    – incud
    Mar 7, 2022 at 16:03
  • $\begingroup$ I don't understand the problem. What are the inputs to the algorithm? I don't know what you mean by creating a graph; does that mean my algorithm can assign any weights it wants to each of the edges? That seems hard to believe. Do you mean the graph is provided as input? It sounds like you want to output a partition of the graph into multiple components. What is the objective function you are trying to minimize? Is it the sum of weights of edges that cross between two different components? It would help if you can articulate the problem clearly. $\endgroup$
    – D.W.
    Mar 8, 2022 at 4:07
  • $\begingroup$ @D.W. Thank you for your comment! Question fixed. Is this clearer? $\endgroup$
    – incud
    Mar 8, 2022 at 15:48
  • $\begingroup$ Much clearer, thank you. How is $w$ specified? Are we given an oracle for $w$, i.e., a subroutine we can call with any $i,j$ to obtain the value of $w(i,j)$? $\endgroup$
    – D.W.
    Mar 9, 2022 at 20:11

1 Answer 1

3
$\begingroup$

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"
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.