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

CC BY-SA 4.0
2018-12-02T06:15:55.397Z
Thanks. That helps a lot. Do you have a reference for the approximation algorithm?
Joe Fitzsimons
CC BY-SA 4.0
2018-12-02T06:30:50.833Z
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.
daniello
CC BY-SA 4.0
2018-12-02T04:39:42.090Z
2018-12-02T04:39:42.090Z
daniello
<p>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.</p>

<p>The property is as follows: </p>

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

<p><span class="math-container">$A_i$</span> and <span class="math-container">$B_i$</span> can be thought of as the <span class="math-container">$i$</span>th step in a process of moving vertices of the graph from one side of a partition (the <span class="math-container">$A$</span> side) to the other (the <span class="math-container">$B$</span> 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.</p>

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

<graph-theory><graph-algorithms><co.combinatorics>
Pulling a graph across a partition
Joe Fitzsimons
# Pulling a graph across a partition

(Asked by: username_0 on 2018-12-02)

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.

**Tags:** graph-theory, graph-algorithms, co.combinatorics


---

## 1 answers

### Answer by username_1 on 2018-12-02. Score: 6

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.

> **Comments:**
> **username_0**: Thanks. That helps a lot. Do you have a reference for the approximation algorithm?  
> **username_1**: 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.  

---

