1
$\begingroup$

I am looking for the name for a particular graph property, if it has been studied, and efficient algorithms for computing it, if they exist. I realise that this may be a well known property that I am just ignorant of, in which case I apologise, and would be grateful to be set right.

The property is as follows:

Take a graph $G=(V,E)$ on $n$ vertices, where $V$ is the vertex set and $E$ is the edge set. Let me define two families of subsets of vertices, $A_i$ and $B_i$, with the relationship that $B = V \setminus A$. I require that $A_0 = V$ and $A_n$ is the empty set. Each intermediate $A_i$ is obtained from $A_{I-1}$ by removing one vertex (according to some strategy). The property I care about is $\max_i |\{(a,b): a\in A_i, b\in B_i,(a,b) \in E\}|$, minimised over all strategies for choosing $A_1 \ldots A_{n-1}$ according to the rules above.

$A_i$ and $B_i$ can be thought of as the $i$th step in a process of moving vertices of the graph from one side of a partition (the $A$ side) to the other (the $B$ side). Thus the property I am concerned with has an operational interpretation as the maximum number of edges that need to cross the partition at any one point in time as we move the graph from one side to another, minimised over all strategies for moving vertices across the partition.

Aside from computing the value of this property, an algorithm for determining the optimal strategy would also be helpful.

$\endgroup$
6
$\begingroup$

What you are looking for is known as Cutwidth. The problem is NP complete and quite well studied. For example it has a $O((\log n)^{3/2})$- approximation algorithm and is fixed parameter tractable when parameterized by the objective function value.

$\endgroup$
  • $\begingroup$ Thanks. That helps a lot. Do you have a reference for the approximation algorithm? $\endgroup$ – Joe Fitzsimons Dec 2 '18 at 6:15
  • 1
    $\begingroup$ A paper to cite does not come to mind but it is just applying the $\sqrt{\log n}$ approximation for balanced cut (Arora, Rao, Vazirani) in a divide and conquer manner (find balanced cut, solve the two sides recursively, put solution to left side before the solution to the right side). Better algorithms might be known, I am not sure. $\endgroup$ – daniello Dec 2 '18 at 6:30

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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