Selecting vertices in a graph in an order to keep border vertices as few as possible

Question

I am given an undirected graph. Initially all vertices are white. I need to color them black in such an order that the maximum number of vertices which are on the border between black and white regions is minimal. Is there an algorithm to find an optimal order for that?

More formally. We are given an undirected, connected graph $G = (V,E)$ consisting of $n$ vertices. I am looking for a sequence of increasing subsets of vertices $V_0, V_1, ..., V_n$, where $V_0 = \emptyset$, $V_{i+1} = V_i \cup \{v\}$ for some $v\in V$, and $V_n = V$. For any subset $W \subset V$ we define a cost function $c(W)$ as the number of "border" vertices, i.e. size of $\{w\in W : \exists m\in V\setminus W: (w,m)\in E \}$. I am looking for such a sequence where $\max_i(c(V_i))$ is minimal.

I feel my problem is somehow related to maximum flow algorithms, the same way as minimum-cut problem is. I think there must be a name for this (or similar) problem. However, as I was mixing "minimal cut" in various ways in the search engines, I was unable to find it.

A bit of context: I have a series of tasks to perform (edges), each loading two files from a disk (vertices). In order to speed up the process, I don't want the reload every pair of files every time. Instead, I want to keep some files in memory so that I can reuse them when another task uses the same file. But I cannot keep all files that there are because of memory constriants. The above sequence would help me select an optimal processing order, keeping the number of active files to minimum.

Answer 1

At first I didn't see how the problem underlying your actual application of using file buffers optimally matched your formulation. But as you mentioned in a comment, they are in fact two equivalent ways of describing the same problem, which amounts to generating a valid maximum-buffer-size-minimising sequence of operations, with each operation being one of "Load file $x$ to a free buffer slot", "Discard buffered file $y$ from its buffer slot" or "Process edge $(u, v)$" with $u$ and $v$ both being currently-buffered files:

• Order vertices (your sequence of larger-by-one sets is equivalent to a vertex ordering) so as to minimise the maximum number of "border" vertices, which correspond to files already loaded into the buffer and which cannot be discarded yet because they are still needed in the future. A sequence of operations can be generated from this vertex order as follows: After choosing a vertex to blacken, load it to a free slot and immediately process all edges it has to existing black vertices (which we know by induction to be still in the buffer) in some arbitrary order, and then (again in arbitrary order) discard from the buffer any of them that have no more white neighbours.
• Order edges so as to minimise the maximum number of "live" vertices, where a vertex becomes live the first time an edge it is incident on appears, and ceases to be live just after the last such edge. A sequence of operations can be generated from this edge order as follows: Load any vertices necessary for the current edge (in either order if neither is in the buffer yet), process the edge, discard from the buffer any vertex that is no longer live (again in arbitrary order).

I see now that your "border" is the same as my "live".

It's NP-hard

Fewest buffer slots needed to avoid reloading

If you want to know the smallest number of buffer slots required to process every file-pair (edge) without ever reloading a file (vertex), this problem is equivalent to the Vertex separation number problem, in which the goal is to choose, from all possible vertex orderings, an ordering that minimises the maximum number of "live" vertices, where a vertex is live at time $i$ iff it appeared before position $i$ in the sequence and has an edge to any vertex at position $\ge i$ in the sequence. Basically, a live vertex at some point in time is a file that has been loaded already but can't be discarded from the buffer yet because it is needed again in the future.

The vertex separation number is another name for the pathwidth of a graph, which is known to be NP-hard to compute. (And finding an actual solution -- a sequence of loads that meets this bound -- is at least as hard as this, of course.) No one knows how to solve an NP-hard problem exactly in subexponential time w.r.t. its size, so any algorithm to solve this problem will be likely be very slow for $n > 20$ vertices or so. The only bright side here is that you don't have to feel bad about using a brute-force solution, like trying all possible vertex orderings. Some tricks may give good speedups in practice, like branch and bound (noticing when your sequence of vertices so far is already worse than a complete solution found earlier, and halting recursion early).

Fewest loads needed for given buffer size

If you have a fixed number $b$ of buffer slots and want to know the smallest number of loads that would be needed using that many slots, this problem is at least as hard as the former one: Any algorithm that answers this question can easily be changed to answer the former one, by binary-searching on $b$ until you find that the answer is equal to the number of vertices (files), $n$. (Again, finding a sequence of loads meeting this bound is at least as hard as this.)

Heuristics

The above explains why you can't expect to solve large instances of this problem quickly and optimally. If you don't care too much about optimality, many heuristics are possible.

Probably the simplest, and what I would try first, is just trying many different random orders, measuring each, and returning the best. Alternatively, start from a random order and look for local improvements, like swapping each pair of vertices, and greedily take the new solution if it is better. When no better solution can be found, restart with a fresh random order. Repeat this as many times as you feel like.

Alternatively you could repeatedly choose a vertex of minimum degree, and process all edges incident on it that have not already been processed. A minimum-degree vertex can be chosen in constant amortised time, and this approach bounds the number of loads by $kn$, where $k$ is the degeneracy of the input graph -- a number that is likely to be low on sparse graphs. Often there are multiple elimination orderings, which may require different numbers of reloads, so this basic strategy could probably be improved quite a bit by tracking which vertices currently have all their neighbours already in the buffer, immediately processing all edges incident on them, and then discarding them.