<p>The problem is very similar to Min Uncut. In Min Uncut, given a graph <span class="math-container">$G = (V, E)$</span>, we need to find a subset of edges <span class="math-container">$E'$</span> s.t. <span class="math-container">$G - E'$</span> is bipartite; the objective is to minimize the size of <span class="math-container">$|E'|$</span>. For brevity, let me call you problem <span class="math-container">$\cal P$</span> and Min Uncut <span class="math-container">$\cal U$</span>.</p>
<p><strong>Observation.</strong> An instance <span class="math-container">$G$</span> of <span class="math-container">$\cal P$</span> has a solution of cost 0 if and only if <span class="math-container">$G$</span> is bipartite.</p>
<p><em>Proof:</em> Assume that <span class="math-container">$G$</span> is bipartite with parts <span class="math-container">$L$</span> and <span class="math-container">$R$</span>. Consider <span class="math-container">$\pi$</span> that first puts the vertices from <span class="math-container">$L$</span> and then the vertices from <span class="math-container">$R$</span> (the relative ordering of vertices in <span class="math-container">$L$</span> and <span class="math-container">$R$</span> may be arbitrary). Then the cost of this solution is <span class="math-container">$0$</span>, as required.</p>
<p>Now assume that <span class="math-container">$G$</span> has a solution <span class="math-container">$\pi$</span> of cost <span class="math-container">$0$</span>. Note that <span class="math-container">$G$</span> cannot have an odd cycle. Indeed if <span class="math-container">$a_1  \to a_2 \to \dots \to a_k$</span> is an odd cycle, then the direction of edges along the cycle should alternate: say <span class="math-container">$(a_1, a_2)$</span> goes forward (w.r.t. <span class="math-container">$\pi$</span>), then <span class="math-container">$(a_2, a_3)$</span> goes backward, then <span class="math-container">$(a_3, a_4)$</span> goes forward etc (or the other way around). That is impossible since the cycle is odd. We conclude that <span class="math-container">$G$</span> doesn't have any odd cycles and thus is bipartite.</p>
<p><strong>QED</strong></p>
<p><strong>Claim.</strong> Let <span class="math-container">$G$</span> be a <em>regular</em> graph, whose vertices have degree <span class="math-container">$d$</span>. Denote the costs of optimal solutions of problems <span class="math-container">$\cal U$</span> and <span class="math-container">$\cal P$</span> in <span class="math-container">$G$</span> by <span class="math-container">$U_G$</span> and <span class="math-container">$P_G$</span>, respectively. Then
<span class="math-container">$$P_G =\Theta(d\cdot U_G).$$</span></p>
<p><strong>Proof:</strong> Let <span class="math-container">$E'$</span> be an optimal solution for <span class="math-container">$\cal U$</span> in <span class="math-container">$G$</span>. Then <span class="math-container">$|E'| = U_G$</span>. Let <span class="math-container">$(L, R)$</span> be a bipartition of <span class="math-container">$G - E'$</span>. Consider a permutation <span class="math-container">$\pi$</span> defined by <span class="math-container">$L$</span> and <span class="math-container">$R$</span>, as in the proof of Observation. The cost of <span class="math-container">$\pi$</span> is at most <span class="math-container">$d \cdot |E'| = d\cdot U_G$</span> (to get this, write the formula for the cost of <span class="math-container">$\pi$</span>; upper bound <span class="math-container">$|\mathrm{succ}_{\pi}(u)|$</span> by <span class="math-container">$d$</span> for vertices in <span class="math-container">$L$</span>; upper bound <span class="math-container">$|\mathrm{pred}_{\pi}(u)|$</span> by <span class="math-container">$d$</span> for vertices in <span class="math-container">$R$</span>). Thus, <span class="math-container">$P_G \leq d\cdot U_G$</span>.</p>
<p>Now consider an optimal solution <span class="math-container">$\pi$</span> for <span class="math-container">$\cal P$</span>. For every vertex <span class="math-container">$u$</span>, either <span class="math-container">$|\mathrm{pred}_{\pi}(u)| \leq d/2$</span> or <span class="math-container">$|\mathrm{succ}_{\pi}(u)| \leq d/2$</span>. In the former case, mark edges from <span class="math-container">$u$</span> to <span class="math-container">$\mathrm{pred}_{\pi}(u)$</span> as bad; in the latter case, mark edges from <span class="math-container">$u$</span> to <span class="math-container">$\mathrm{succ}_{\pi}(u)$</span> as bad. Note that when we process <span class="math-container">$u$</span>, we mark <span class="math-container">$\min(|\mathrm{pred}_{\pi}(u)|, |\mathrm{succ}_{\pi}(u)|)$</span> edges. We have,
<span class="math-container">$$\min(|\mathrm{pred}_{\pi}(u)|, |\mathrm{succ}_{\pi}(u)|) \leq |\mathrm{pred}_{\pi}(u)| \times |\mathrm{succ}_{\pi}(u)| / (d/2).$$</span>
Adding up this inequality over all <span class="math-container">$u$</span>, we get that the total number of bad edges is at most <span class="math-container">$2P_G/d$</span>. Now let <span class="math-container">$E'$</span> be the set of bad edges. Clearly, <span class="math-container">$P_{G- E'} = 0$</span>. From Observation, we get that <span class="math-container">$G-E'$</span> is bipartite. Thus, <span class="math-container">$E'$</span> is a feasible solution for <span class="math-container">$\cal U$</span>. We conclude that <span class="math-container">$U_G \leq 2P_G/d$</span>.</p>
<p>We have proved that
<span class="math-container">$$\frac{d}{2} U_G \leq P_G \leq d\cdot U_G.$$</span></p>
<p><strong>QED</strong></p>
<p>We see that in regular graphs, <span class="math-container">$\cal P$</span> and <span class="math-container">$\cal U$</span> are essentially equivalent. Note that it was shown in</p>
<blockquote>
<p>Chawla, Shuchi, Robert Krauthgamer, Ravi Kumar, Yuval Rabani, and D.
Sivakumar. &quot;On the hardness of approximating Multicut and
Sparsest-cut.&quot; Computational Complexity 15, no. 2 (2006): 94-114.</p>
</blockquote>
<p>that there is no constant factor approximation for <span class="math-container">$\cal U$</span> if the Unique Games Conjecture holds. On the other hand, there is an <span class="math-container">$O(\sqrt{\log n})$</span> approximation algorithm for <span class="math-container">$\cal U$</span>; see</p>
<blockquote>
<p>Agarwal, Amit, Moses Charikar, Konstantin Makarychev, and Yury
Makarychev. &quot;<span class="math-container">$O(\sqrt{\log n})$</span> approximation algorithms for Min UnCut, Min
2CNF Deletion, and directed cut problems.&quot; In Proceedings of STOC 2005, pp. 573-581.</p>
</blockquote>
<p><strong>What about the regularity assumption?</strong>
The regularity assumption is not really necessary and was made above to simplify the exposition.</p>
<p><strong>Hardness of approximation.</strong> We can start with any (not necessarily regular) instance <span class="math-container">$G = (V, E)$</span> of <span class="math-container">$\cal U$</span>. Let <span class="math-container">$d$</span> be the maximum degree of <span class="math-container">$G$</span>. Attach <span class="math-container">$d - \deg u$</span> new vertices to every vertex <span class="math-container">$u\in V$</span>. We will obtain a new graph <span class="math-container">$G' = (V', E')$</span>, in which every vertex has degree <span class="math-container">$d$</span> or <span class="math-container">$1$</span>. Clearly, <span class="math-container">$U_{G} = U_{G'}$</span>. Now we apply the reduction from Claim to <span class="math-container">$G'$</span>. It's easy to see that the reduction still works for <span class="math-container">$G'$</span>, even though it's not regular (since <span class="math-container">$\deg u\in\{1, d\}$</span> for every <span class="math-container">$u$</span>).</p>
<p><strong>Algorithm.</strong> Given an instance <span class="math-container">$G = (V, E)$</span> of <span class="math-container">$\cal U$</span>, we create a weighted graph <span class="math-container">$G'$</span>; <span class="math-container">$G' = (V, E, w)$</span> is the same graph as <span class="math-container">$G$</span> except that edge <span class="math-container">$(u,v)$</span> has weight
<span class="math-container">$$w(u,v) = \min(\deg u, \deg v).$$</span>
We solve <span class="math-container">$\cal U$</span> in <span class="math-container">$G'$</span>, and get a partition <span class="math-container">$(L,R)$</span> of <span class="math-container">$V$</span>. We define <span class="math-container">$\pi$</span> as follows: first put vertices from <span class="math-container">$L$</span> and then vertices from <span class="math-container">$R$</span>. Importantly, the order of vertices in <span class="math-container">$L$</span> and in <span class="math-container">$R$</span> is not arbitrary now. We put vertices with smaller degrees closer to the boundary between <span class="math-container">$L$</span> and <span class="math-container">$R$</span>. (In other words, vertices in <span class="math-container">$L$</span> and <span class="math-container">$R$</span> are sorted by their degrees in the descending and ascending orders, respectively.) It's not hard to see that this algorithm gives <span class="math-container">$O(\sqrt{\log n})$</span> approximation.</p>
<p><strong>Conclusion:</strong></p>
<ol>
<li>There is no constant factor approximation for <span class="math-container">$\cal P$</span> if the Unique
Games Conjecture holds.</li>
<li>There is an <span class="math-container">$O(\sqrt{\log n})$</span> approximation algorithm.</li>
<li>In order to get a better approximation factor, one needs to improve the best known approximation algorithm for Min Uncut (which would be a breakthrough result in the field, especially since the problem is closely related to Sparsest Cut and Balanced Cut).</li>
</ol>
<p>(Informal note: we will not get any better algorithms if we assume that the graph has a high average degree or a relatively low average degree.)</p>
<p><strong>Generalization:</strong> The proof can be adapted in a straightforward way to <a href="https://cstheory.stackexchange.com/questions/48571">this problem</a>, where instead of looking for a permutation of the nodes, we look for an orientation of the edges (that is a less constrained problem where the edge orientation does not have to induce a DAG).<br />
It can also be adapted in a straightforward way to the case where the objective to minimize is <span class="math-container">$\sum_{v\in V} ~\min(\left|\text{succ}_{\pi}(v)\right|, 
\left|\text{pred}_{\pi}(v)\right|)$</span> instead of <span class="math-container">$\sum_{v\in V} ~\left|\text{succ}_{\pi}(v)\right|\times
\left|\text{pred}_{\pi}(v)\right|$</span>. Interestingly, with that new objective we have <span class="math-container">$U_G = P_G$</span>.</p>

CC BY-SA 4.0
2020-06-11T21:08:19.317Z
Magnificent proof. Thanks!
What if the maximum degree $d$ is large, say $d\in\Theta(n)$? Then there is no polynomial time $O(n)$-approximation algorithm for my problem if UGC is true. Correct?
maxdan94
CC BY-SA 4.0
2020-06-12T11:22:19.703Z
UGC implies that there is no polynomial-time constant factor approximation algorithm. Since the problem can be reduced to Min Uncut and there is a ~sqrt(log n) approximation algorithm for Min Uncut, there is a ~ sqrt (log n) approximation algorithm for this problem as well. (I showed this only for regular graphs in my post, but this is true for arbitrary graphs; I will expand my post later).
Yury
CC BY-SA 4.0
2020-06-12T13:02:01.083Z
I see. Yes a proof for arbitrary graphs would help.
Assume $d=floor(n/2)$, then your claim becomes $P_G=\Theta(n\cdot U_G)$ and thus a $O(n)$-approximation of $P_G$ implies a constant approximation of $U_G$. But maybe in "$floor(n/2)$-regular graphs", $U_G$ can be approximated within a constant factor in polynomial time under UGC? Something I've missed?
maxdan94
CC BY-SA 4.0
2020-06-12T15:09:27.247Z
(1) I've added the algorithm. (2) I am not following your argument. We are talking about multiplicative approximation, so, in regular graphs, an $\alpha$ approximation for $\cal U$ implies a $2\alpha$ approximation for $\cal P$ and vice versa. What $d$ is is more or less irrelevant.
Yury
CC BY-SA 4.0
2020-06-12T20:25:08.753Z
Let me rephrase it.
If $d$ is a function of $n$, e.g. $d=n/2$, then the equivalence between the two problems do not hold anymore. It only holds for a fixed value of $d$.
In particular, with Claim., we can see that if $d$ is an increasing function of $n$ (e.g. $d=n/2$ or $d=\sqrt{n}$), then $P$ is harder to approximate than $U$.
maxdan94
CC BY-SA 4.0
2020-06-12T22:16:58.987Z
I don't make any assumptions on $d$; it may depend on $n$, and, in particular, be equal to $n/2$. Regarding Claim: The problems are equivalent no matter what the value of d is. To solve $\cal P$, just approximately solve $\cal U$, then you get a $2\alpha$ approximation (in particular when $n = d/2$ or $\sqrt{n}$).
Yury
CC BY-SA 4.0
2020-06-14T09:37:19.313Z
I've finally understood. Thanks Yury, really helps a lot!
maxdan94
CC BY-SA 4.0
2020-06-14T19:21:45.347Z
I think that the key point is the construction from the proof. It allows us not only say how optimal costs are related to each other, but also construct a solution (not necessarily optimal) for one problem from the solution of another problem, and write $2/d C_{U_G} \leqslant C_{P_G} \leqslant d C_{U_G} $, where $ C_{U_G}$ and $P_{U_G}$ are corresponding (not necessarily optimal) solution costs.
kerzol
CC BY-SA 4.0
2021-02-07T17:33:20.443Z
Dear @Yury, I actually do not understand the link between the algorithm you have proposed and your claim generalized to non-regular graphs. For the algorithm, why not simply computing a cut in G (the $O(\sqrt{\log(n)})$) approx) and putting first the vertices in L and then the ones in R?
maxdan94
CC BY-SA 4.0
2020-06-10T14:41:42.693Z
2021-03-17T14:56:49.007Z
2021-03-17T14:56:49.007Z
Yury
<p>Let <span class="math-container">$G=(V,E)$</span> be an undirected graph, and let <span class="math-container">$\pi$</span> be a permutation of the vertices in <span class="math-container">$V$</span>.<br>
For a node <span class="math-container">$v\in V$</span>, we denote by <span class="math-container">$\text{pred}_{\pi}(v)$</span> (respectively <span class="math-container">$\text{succ}_{\pi}(v)$</span>) the set of neighbors of <span class="math-container">$v$</span> that occur before <span class="math-container">$v$</span> 
(respectively after <span class="math-container">$v$</span>) in the permutation <span class="math-container">$\pi$</span>.</p>

<blockquote>
  <p><strong>Problem.</strong> For a given undirected graph <span class="math-container">$G=(V,E)$</span>, find a 
  permutation <span class="math-container">$\pi$</span> of the vertices that minimizes the objective value 
  <span class="math-container">$$\sum_{v\in V} ~\left|\text{succ}_{\pi}(v)\right|\times
\left|\text{pred}_{\pi}(v)\right|.$$</span> </p>
</blockquote>

<p>Is there a polynomial time approximation algorithm for this problem, that approximates the optimal objective value within a constant factor?  The problem is known to be <a href="https://cstheory.stackexchange.com/questions/38274/">NP-hard</a>.</p>

CC BY-SA 4.0
2020-06-10T12:29:54.800Z
What do you already know about the problem?  Is it NP-complete?  If so can you cite or describe a proof of that?  Do you know any (non-constant-factor) poly-time approximation algorithms?
Neal Young
CC BY-SA 4.0
2020-06-10T12:59:44.430Z
Yes, finding the best ordering is NP-hard: https://cstheory.stackexchange.com/questions/38274
I think that this is the only thing that I know.
maxdan94
<graph-theory><approximation-algorithms><optimization><approximation-hardness><approximation>
Is the following graph optimization problem approximable within a constant factor?
maxdan94
# Is the following graph optimization problem approximable within a constant factor?

(Asked by: username_0 on 2020-06-10)

Let $G=(V,E)$ be an undirected graph, and let $\pi$ be a permutation of the vertices in $V$.  
For a node $v\in V$, we denote by $\text{pred}\_{\pi}(v)$ (respectively $\text{succ}\_{\pi}(v)$) the set of neighbors of $v$ that occur before $v$
(respectively after $v$) in the permutation $\pi$.

> **Problem.** For a given undirected graph $G=(V,E)$, find a
> permutation $\pi$ of the vertices that minimizes the objective value
> $$\sum\_{v\in V} ~\left|\text{succ}\_{\pi}(v)\right|\times
> \left|\text{pred}\_{\pi}(v)\right|.$$

Is there a polynomial time approximation algorithm for this problem, that approximates the optimal objective value within a constant factor? The problem is known to be [NP-hard](https://cstheory.stackexchange.com/questions/38274/).

**Tags:** graph-theory, approximation-algorithms, optimization, approximation-hardness, approximation

> **Comments:**
> **username_1**: What do you already know about the problem?  Is it NP-complete?  If so can you cite or describe a proof of that?  Do you know any (non-constant-factor) poly-time approximation algorithms?  
> **username_0**: Yes, finding the best ordering is NP-hard: https://cstheory.stackexchange.com/questions/38274 I think that this is the only thing that I know.  

---

## 1 answers

### Answer by username_2 on 2020-06-10. Score: 14 | Accepted answer

The problem is very similar to Min Uncut. In Min Uncut, given a graph $G = (V, E)$, we need to find a subset of edges $E'$ s.t. $G - E'$ is bipartite; the objective is to minimize the size of $|E'|$. For brevity, let me call you problem $\cal P$ and Min Uncut $\cal U$.

**Observation.** An instance $G$ of $\cal P$ has a solution of cost 0 if and only if $G$ is bipartite.

*Proof:* Assume that $G$ is bipartite with parts $L$ and $R$. Consider $\pi$ that first puts the vertices from $L$ and then the vertices from $R$ (the relative ordering of vertices in $L$ and $R$ may be arbitrary). Then the cost of this solution is $0$, as required.

Now assume that $G$ has a solution $\pi$ of cost $0$. Note that $G$ cannot have an odd cycle. Indeed if $a\_1 \to a\_2 \to \dots \to a\_k$ is an odd cycle, then the direction of edges along the cycle should alternate: say $(a\_1, a\_2)$ goes forward (w.r.t. $\pi$), then $(a\_2, a\_3)$ goes backward, then $(a\_3, a\_4)$ goes forward etc (or the other way around). That is impossible since the cycle is odd. We conclude that $G$ doesn't have any odd cycles and thus is bipartite.

**QED**

**Claim.** Let $G$ be a *regular* graph, whose vertices have degree $d$. Denote the costs of optimal solutions of problems $\cal U$ and $\cal P$ in $G$ by $U\_G$ and $P\_G$, respectively. Then
$$P\_G =\Theta(d\cdot U\_G).$$

**Proof:** Let $E'$ be an optimal solution for $\cal U$ in $G$. Then $|E'| = U\_G$. Let $(L, R)$ be a bipartition of $G - E'$. Consider a permutation $\pi$ defined by $L$ and $R$, as in the proof of Observation. The cost of $\pi$ is at most $d \cdot |E'| = d\cdot U\_G$ (to get this, write the formula for the cost of $\pi$; upper bound $|\mathrm{succ}\_{\pi}(u)|$ by $d$ for vertices in $L$; upper bound $|\mathrm{pred}\_{\pi}(u)|$ by $d$ for vertices in $R$). Thus, $P\_G \leq d\cdot U\_G$.

Now consider an optimal solution $\pi$ for $\cal P$. For every vertex $u$, either $|\mathrm{pred}\_{\pi}(u)| \leq d/2$ or $|\mathrm{succ}\_{\pi}(u)| \leq d/2$. In the former case, mark edges from $u$ to $\mathrm{pred}\_{\pi}(u)$ as bad; in the latter case, mark edges from $u$ to $\mathrm{succ}\_{\pi}(u)$ as bad. Note that when we process $u$, we mark $\min(|\mathrm{pred}\_{\pi}(u)|, |\mathrm{succ}\_{\pi}(u)|)$ edges. We have,
$$\min(|\mathrm{pred}\_{\pi}(u)|, |\mathrm{succ}\_{\pi}(u)|) \leq |\mathrm{pred}\_{\pi}(u)| \times |\mathrm{succ}\_{\pi}(u)| / (d/2).$$
Adding up this inequality over all $u$, we get that the total number of bad edges is at most $2P\_G/d$. Now let $E'$ be the set of bad edges. Clearly, $P\_{G- E'} = 0$. From Observation, we get that $G-E'$ is bipartite. Thus, $E'$ is a feasible solution for $\cal U$. We conclude that $U\_G \leq 2P\_G/d$.

We have proved that
$$\frac{d}{2} U\_G \leq P\_G \leq d\cdot U\_G.$$

**QED**

We see that in regular graphs, $\cal P$ and $\cal U$ are essentially equivalent. Note that it was shown in

> Chawla, Shuchi, Robert Krauthgamer, Ravi Kumar, Yuval Rabani, and D.
> Sivakumar. "On the hardness of approximating Multicut and
> Sparsest-cut." Computational Complexity 15, no. 2 (2006): 94-114.

that there is no constant factor approximation for $\cal U$ if the Unique Games Conjecture holds. On the other hand, there is an $O(\sqrt{\log n})$ approximation algorithm for $\cal U$; see

> Agarwal, Amit, Moses Charikar, Konstantin Makarychev, and username_2
> Makarychev. "$O(\sqrt{\log n})$ approximation algorithms for Min UnCut, Min
> 2CNF Deletion, and directed cut problems." In Proceedings of STOC 2005, pp. 573-581.

**What about the regularity assumption?**
The regularity assumption is not really necessary and was made above to simplify the exposition.

**Hardness of approximation.** We can start with any (not necessarily regular) instance $G = (V, E)$ of $\cal U$. Let $d$ be the maximum degree of $G$. Attach $d - \deg u$ new vertices to every vertex $u\in V$. We will obtain a new graph $G' = (V', E')$, in which every vertex has degree $d$ or $1$. Clearly, $U\_{G} = U\_{G'}$. Now we apply the reduction from Claim to $G'$. It's easy to see that the reduction still works for $G'$, even though it's not regular (since $\deg u\in\{1, d\}$ for every $u$).

**Algorithm.** Given an instance $G = (V, E)$ of $\cal U$, we create a weighted graph $G'$; $G' = (V, E, w)$ is the same graph as $G$ except that edge $(u,v)$ has weight
$$w(u,v) = \min(\deg u, \deg v).$$
We solve $\cal U$ in $G'$, and get a partition $(L,R)$ of $V$. We define $\pi$ as follows: first put vertices from $L$ and then vertices from $R$. Importantly, the order of vertices in $L$ and in $R$ is not arbitrary now. We put vertices with smaller degrees closer to the boundary between $L$ and $R$. (In other words, vertices in $L$ and $R$ are sorted by their degrees in the descending and ascending orders, respectively.) It's not hard to see that this algorithm gives $O(\sqrt{\log n})$ approximation.

**Conclusion:**

1. There is no constant factor approximation for $\cal P$ if the Unique
   Games Conjecture holds.
2. There is an $O(\sqrt{\log n})$ approximation algorithm.
3. In order to get a better approximation factor, one needs to improve the best known approximation algorithm for Min Uncut (which would be a breakthrough result in the field, especially since the problem is closely related to Sparsest Cut and Balanced Cut).

(Informal note: we will not get any better algorithms if we assume that the graph has a high average degree or a relatively low average degree.)

**Generalization:** The proof can be adapted in a straightforward way to [this problem](https://cstheory.stackexchange.com/questions/48571), where instead of looking for a permutation of the nodes, we look for an orientation of the edges (that is a less constrained problem where the edge orientation does not have to induce a DAG).  
It can also be adapted in a straightforward way to the case where the objective to minimize is $\sum\_{v\in V} ~\min(\left|\text{succ}\_{\pi}(v)\right|,
\left|\text{pred}\_{\pi}(v)\right|)$ instead of $\sum\_{v\in V} ~\left|\text{succ}\_{\pi}(v)\right|\times
\left|\text{pred}\_{\pi}(v)\right|$. Interestingly, with that new objective we have $U\_G = P\_G$.

> **Comments:**
> **username_0**: Magnificent proof. Thanks! What if the maximum degree $d$ is large, say $d\in\Theta(n)$? Then there is no polynomial time $O(n)$-approximation algorithm for my problem if UGC is true. Correct?  
> **username_2**: UGC implies that there is no polynomial-time constant factor approximation algorithm. Since the problem can be reduced to Min Uncut and there is a ~sqrt(log n) approximation algorithm for Min Uncut, there is a ~ sqrt (log n) approximation algorithm for this problem as well. (I showed this only for regular graphs in my post, but this is true for arbitrary graphs; I will expand my post later).  
> **username_0**: I see. Yes a proof for arbitrary graphs would help. Assume $d=floor(n/2)$, then your claim becomes $P_G=\Theta(n\cdot U_G)$ and thus a $O(n)$-approximation of $P_G$ implies a constant approximation of $U_G$. But maybe in "$floor(n/2)$-regular graphs", $U_G$ can be approximated within a constant factor in polynomial time under UGC? Something I've missed?  
> **username_2**: (1) I've added the algorithm. (2) I am not following your argument. We are talking about multiplicative approximation, so, in regular graphs, an $\alpha$ approximation for $\cal U$ implies a $2\alpha$ approximation for $\cal P$ and vice versa. What $d$ is is more or less irrelevant.  
> **username_0**: Let me rephrase it. If $d$ is a function of $n$, e.g. $d=n/2$, then the equivalence between the two problems do not hold anymore. It only holds for a fixed value of $d$. In particular, with Claim., we can see that if $d$ is an increasing function of $n$ (e.g. $d=n/2$ or $d=\sqrt{n}$), then $P$ is harder to approximate than $U$.  
> **username_2**: I don't make any assumptions on $d$; it may depend on $n$, and, in particular, be equal to $n/2$. Regarding Claim: The problems are equivalent no matter what the value of d is. To solve $\cal P$, just approximately solve $\cal U$, then you get a $2\alpha$ approximation (in particular when $n = d/2$ or $\sqrt{n}$).  
> **username_0**: I've finally understood. Thanks username_2, really helps a lot!  
> **username_3**: I think that the key point is the construction from the proof. It allows us not only say how optimal costs are related to each other, but also construct a solution (not necessarily optimal) for one problem from the solution of another problem, and write $2/d C_{U_G} \leqslant C_{P_G} \leqslant d C_{U_G} $, where $ C_{U_G}$ and $P_{U_G}$ are corresponding (not necessarily optimal) solution costs.  
> **username_0**: Dear @username_2, I actually do not understand the link between the algorithm you have proposed and your claim generalized to non-regular graphs. For the algorithm, why not simply computing a cut in G (the $O(\sqrt{\log(n)})$) approx) and putting first the vertices in L and then the ones in R?  

---

