6
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Quick observation: As soon as any degree-2 vertex is chosen that already has a chosen neighbour, continue choosing the other neighbour while it is also of degree 2. Equivalently, it's safe to contract every path of degree-2 vertices in the input graph to a single degree-2 vertex. $\endgroup$ Feb 29, 2020 at 14:01
  • 2
    $\begingroup$ I don't think the optimisation problem you formulated quite matches your application, though it may still be helpful. You are actually looking for a sequence of edges such that the maximum number of vertices that are "live" at any time is minimised, where a vertex becomes live the first time an edge incident on it appears in the sequence, and ceases to be live just after the last such edge appears: this maximum number of live vertices is the minimum number of buffer slots you need to prevent any file being loaded twice. $\endgroup$ Feb 29, 2020 at 17:25
  • 2
    $\begingroup$ @j_random_hacker I think it's equivalent. If both ends of a given edge belong to some $V_i$ but not $V_{i-1}$, that's when I process that edge/task. You want to order the tasks, I want to order the files which are needed to execute the tasks. One implies the other and vice versa. $\endgroup$
    – CygnusX1
    Mar 1, 2020 at 6:16
  • 1
    $\begingroup$ I'm sorry, you're absolutely right -- they are equivalent. I'll edit my question in a moment. $\endgroup$ Mar 1, 2020 at 11:53

1 Answer 1

4
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ I will explore the heuristics then. My graph is quite space, with degrees hardly ever exceeding 5. Btw. isn't the Vertex separation number problem exactly what I described in the question, just in a bit convoluted way? $\endgroup$
    – CygnusX1
    Mar 1, 2020 at 6:35
  • 1
    $\begingroup$ You're right -- I updated my answer. Sorry for the confusion! $\endgroup$ Mar 1, 2020 at 12:32

Your Answer

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

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