1
$\begingroup$

I'm working on the following problem: let $G = (V, E)$ be a connected, planar graph. Our goal is to find a $d$-partition of $G$, $P = \{V_1, \ldots, V_d\}$, such that $G[V_i]$ is connected, and $\min_{V_i \in P} |V_i|$ is maximized. (That is, the partitions are as balanced in size as possible.) This is the balanced connected partition problem on planar graphs, and is known to be NP-complete.

I'm trying to use hill-climbing to solve this problem. Let $C$ be a $|V|$-length array, such that $C[i] = j$ implies that vertex $i$ is in $V_j$. This represents a partition $P_C$ of $V$, such that $V_k = \{i \in V \mid C[i] = k\}$. Let $G_C = (V, E_C)$ be the corresponding graph $\bigcup_{V_i \in P_C} G[V_i]$. Thus, $E \setminus E_C$ is the set of all edges $(u, v)$ such that $u$ and $v$ are in different vertex subsets.

A "move" in this space (for the purposes of hill-climbing) is performed as follows. Let $N(v) = \{w \in V \mid (w, v) \in E\}$ be the neighbors of a vertex $v$ in the original graph. Let $(u, v)$ be an edge in $E \setminus E_C$. For all $w \in N(v)$, if $C[w] = C[v]$, remove $(w, v)$ from $E_C$; otherwise, if $C[w] = C[u]$, add $(w, v)$ to $E_C$. This induces a different partition, one where $v$ is in $u$'s subset.

It's of course possible that the graph induced by these partitions contains more than $d$ connected components. I want to penalize these, proportional to the absolute difference between the number of connected components in the graph and $d$. The problem is that finding these connected components is expensive—$O(|V| + |E|)$ time per step—and I'd like to reduce that.

I did some snooping around in the space of fully dynamic graph connectivity algorithms. For general graphs, Holm et al. (see [1]) achieve $O(\log^2 n/\log \log n)$ insert/delete and $O(\log n/\log \log n)$ connectivity queries (i.e., are $u$ and $v$ connected?) by using Henzinger and King's Euler-tour trees (see [2]). For planar graphs, Eppstein et al. (see [3]) achieve $O(\log n)$ insert/delete/connectivity.

The problem is that I'm not sure that it's trivial to adapt any of these results to my problem, since I'm not sure that transforming connectivity queries into connected-component counts is easy or possible. The other thing is that those results support general edge insertion and deletion, which is good, but I want to know if I can exploit the fact that I know all of the edges that can ever be inserted or deleted ahead of time to do some precomputation and speed up connected component counting.

I've also had the following insight. Let's say we move $v$ to $u$'s subset as described above. Call the original graph $G_1$ and the new graph $G_2$. Then the number of connected components in $G_2$ is the number of connected components in $G_1$, minus the number of vertices $w$ in $N(v)$ that weren't connected to $u$ before but are now (i.e., every path from $u$ to $w$ goes through $v$), plus the number of bridge edges $(w, v)$ for $w \in N(v)$ and $C[w] = C[v]$ (i.e., the number of $v$'s neighboring edges that, upon removal break connectedness of $v$'s original subset).

Does anyone know of any kind of solution to this problem? Or does anyone have any suggestions for papers to read?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.