9
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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? $\endgroup$ – Neal Young Jun 10 at 12:29
  • $\begingroup$ Yes, finding the best ordering is NP-hard: cstheory.stackexchange.com/questions/38274 I think that this is the only thing that I know. $\endgroup$ – maxdan94 Jun 10 at 12:59
11
$\begingroup$

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 Yury 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.)

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – maxdan94 Jun 11 at 21:08
  • $\begingroup$ 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). $\endgroup$ – Yury Jun 12 at 11:22
  • $\begingroup$ 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? $\endgroup$ – maxdan94 Jun 12 at 13:02
  • 1
    $\begingroup$ 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}$). $\endgroup$ – Yury Jun 12 at 22:16
  • 1
    $\begingroup$ I've finally understood. Thanks Yury, really helps a lot! $\endgroup$ – maxdan94 Jun 14 at 9:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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