<p>In the current formulation, your problem can be proved to be NP-complete by a direct reduction from PARTITION.</p>

<p>Given $n$ positive integers, $S = \{a_1,a_2,...,a_n\}$ the PARTITION problem asks to find two disjoint subsets $S_1 \cup S_2 = S$ such that $\sum_{i\in S_1} a_i = \sum_{j \in S_2} a_j$.</p>

<p>So, just pick: $G = \{ V, \emptyset \}$ with $|V| = n$, set $m = 2$ and assign weight $a_i$ to node $u_i$ for all $i = 1,...,n$; set $B = \frac{1}{2} \sum a_i$, and set $K=0$ (arc costs and the acyclic constraints are irrelevant).</p>

<p>NOTE: my old answer was related to a different ACYCLIC PARTITION problem, and you can find it in the edits history below.</p>

CC BY-SA 3.0
2014-03-02T07:45:40.577Z
K cannot be zero, because the problem states that K should be a positive integer.
Ricky
CC BY-SA 3.0
2014-03-02T08:10:28.037Z
Do you happen to know any approximation algorithms for the problem?
Ricky
CC BY-SA 3.0
2014-03-02T10:13:21.350Z
@Ricky: you can set $K=1$ (there are no arcs, so you are sure that the constraint is satisfied). If you complain about the empty arc set, you can build a dummy graph: pick a node $u$ and add directed edges from the others to it with cost 1 and set $K = |A|$ (the partition will always be acyclic and cannot break the cost constraints). But the matter is that in the current formulation there is an immediate reduction from PARTITION (thanks to the node weights), indeed in G&J they say it remains hard even for w(v)=c(a)=1 (but it should be a different question).
Marzio De Biasi
CC BY-SA 3.0
2014-03-02T10:15:40.687Z
@Ricky: ... for what regards approximation, I don't know any algorithm :(
Marzio De Biasi
CC BY-SA 3.0
2014-03-02T11:01:52.307Z
Ah, but once ACYCLIC PARTITION is proven to be NP-complete by reduction from PARTITION, any approximation algorithm for PARTITION would also count as an approximation algorithm for ACYCLIC PARTITION, right?
Ricky
CC BY-SA 3.0
2014-03-02T11:08:17.327Z
@Ricky: no, I don't think that it works, because to prove NP-hardness you only use a special and very restricted case of ACYCLIC PARTITION.
Marzio De Biasi
CC BY-SA 3.0
2014-03-02T11:19:02.460Z
Indeed, to prove NP-completeness, you've used a special case of ACYCLIC PARTITION. But the end result is that PARTITION can be reduced to ACYCLIC PARTITION and vice-versa (you haven't done this in your answer though). If that is the case, then wouldn't any approximation algorithm for PARTITION be reducible to solve ACYCLIC PARTITION too?
Ricky
CC BY-SA 3.0
2014-03-02T11:24:41.360Z
@Ricky: no, to prove NP-completeness (NP-hardness to be more precise), you must only show a (polynomial time) reduction FROM an NP-complete problem (PARTITION in this case) TO your problem (ACYCLIC PARTITION in this case), and not the inverse.
Marzio De Biasi
CC BY-SA 3.0
2014-03-03T10:46:59.570Z
I agree, I never said that we need to do the inverse also to PROVE NP-completeness. I'm just saying that once we've proven NP-completeness of ACYCLIC PARTITION by reduction from PARTITION, we can be sure that a reduction in the opposite direction exists as well. And since it exists, we can say that any approximation algorithm for one problem can also serve as an approximation algorithm for the other. Isn't this true?
Ricky
CC BY-SA 4.0
2021-08-17T14:12:48.797Z
@Ricky, no.  Poly-time reductions do not necessarily (and usually don't) preserve approximate solutions.  For that you need a particular kind of reduction called an approximation-preserving reduction.
Neal Young
CC BY-SA 3.0
2014-03-01T12:33:54.920Z
2014-03-02T08:18:26.943Z
2014-03-02T08:18:26.943Z
Marzio De Biasi
<p>A useful reference is "Sitting Closer to Friends Than Enemies, Revisited" by Cygan, Pilipczuk, Pilipczuk and Wojtaszczyk, MFCS 2012. Not sure if the title should be interpreted literally though: it's probably better to keep your enemies close for various reasons (<a href="http://www.askmen.com/money/mafioso_60/67_mafia.html" rel="nofollow">http://www.askmen.com/money/mafioso_60/67_mafia.html</a>)</p>

CC BY-SA 3.0
2014-03-01T11:28:05.980Z
2014-03-01T11:48:26.097Z
2014-03-01T11:48:26.097Z
Super0
<p>I'm new to this site, so please pardon me for any mistakes and please feel free to edit the question to help get better answers.</p>

<p>I'm interested in reading any proof of ACYCLIC PARTITION (Garey and Johnson) being NP-complete, and I'd love it if you could share a proof for the same here. It'd be great if you could also give an approximation algorithm for the problem.</p>

<p>EDIT:</p>

<p>The problem is defined as follows (Garey and Johnson):</p>

<p>Let $G = (V,A)$ be a directed graph, with a weight function $w(v)$ mapping each vertex $v$ to a positive integer, cost function $c(a)$ mapping each edge $a$ to a positive integer, and let there be two positive integers $B$ and $K$.</p>

<p>Is there a partition of V into disjoint sets $V1, V2,..., V_m$ such that the directed graph $G' = (V',A')$, where $V' = \{V1, V2,..., V_m\}$, and $(V_i, V_j)$ is in $A'$ if and only if $(v_i,v_j)$ is in $A$ for some $v_i \in V_i$ and some $v_j \in V_j$, is acyclic, such that the sum of the weights of the vertices in each $V_i$ does not exceed $B$, and such that the sum of the costs of all those arcs having their endpoints in different sets does not exceed $K$?</p>

CC BY-SA 3.0
2014-03-01T14:19:20.610Z
[Crossposted to Math SE](http://math.stackexchange.com/questions/694859/proof-for-acyclic-partition-being-an-np-complete-problem)
Ricky
CC BY-SA 3.0
2014-03-01T18:10:34.973Z
We don't generally like simultaneous crossposting because it fragments the discussion. Since you've received answers here already we'll leave this as it stands, but in the future please refrain from crossposting till the first post has had a chance to receive answers (or not) for a few days.
Suresh Venkat
CC BY-SA 3.0
2014-03-01T21:50:37.900Z
Can you put the exact page (or chapter/paragrph) where the problem is defined in G&J (I gave a quick look, but didn't find it)?
Marzio De Biasi
CC BY-SA 3.0
2014-03-02T07:42:17.580Z
@MarzioDeBiasi The problem is perfectly defined in A2.2 Cuts and Connectivity
Ricky
CC BY-SA 3.0
2014-03-02T07:43:20.587Z
@SureshVenkat I'm sorry, I'll be sure to follow that henceforth.
Ricky
<graph-theory><approximation-algorithms><np-complete>
Proof for ACYCLIC PARTITION being NP-complete
Ricky
# Proof for ACYCLIC PARTITION being NP-complete

(Asked by: username_0 on 2014-03-01)

I'm new to this site, so please pardon me for any mistakes and please feel free to edit the question to help get better answers.

I'm interested in reading any proof of ACYCLIC PARTITION (Garey and Johnson) being NP-complete, and I'd love it if you could share a proof for the same here. It'd be great if you could also give an approximation algorithm for the problem.

EDIT:

The problem is defined as follows (Garey and Johnson):

Let $G = (V,A)$ be a directed graph, with a weight function $w(v)$ mapping each vertex $v$ to a positive integer, cost function $c(a)$ mapping each edge $a$ to a positive integer, and let there be two positive integers $B$ and $K$.

Is there a partition of V into disjoint sets $V1, V2,..., V\_m$ such that the directed graph $G' = (V',A')$, where $V' = \{V1, V2,..., V\_m\}$, and $(V\_i, V\_j)$ is in $A'$ if and only if $(v\_i,v\_j)$ is in $A$ for some $v\_i \in V\_i$ and some $v\_j \in V\_j$, is acyclic, such that the sum of the weights of the vertices in each $V\_i$ does not exceed $B$, and such that the sum of the costs of all those arcs having their endpoints in different sets does not exceed $K$?

**Tags:** graph-theory, approximation-algorithms, np-complete
> **Comments:**
> **username_0**: [Crossposted to Math SE](http://math.stackexchange.com/questions/694859/proof-for-acyclic-partition-being-an-np-complete-problem)  
> **username_1**: We don't generally like simultaneous crossposting because it fragments the discussion. Since you've received answers here already we'll leave this as it stands, but in the future please refrain from crossposting till the first post has had a chance to receive answers (or not) for a few days.  
> **username_2**: Can you put the exact page (or chapter/paragrph) where the problem is defined in G&J (I gave a quick look, but didn't find it)?  
> **username_0**: @MarzioDeBiasi The problem is perfectly defined in A2.2 Cuts and Connectivity  
> **username_0**: @SureshVenkat I'm sorry, I'll be sure to follow that henceforth.  

---

## 2 answers

### Answer by username_2 on 2014-03-01. Score: 3

In the current formulation, your problem can be proved to be NP-complete by a direct reduction from PARTITION.

Given $n$ positive integers, $S = \{a\_1,a\_2,...,a\_n\}$ the PARTITION problem asks to find two disjoint subsets $S\_1 \cup S\_2 = S$ such that $\sum\_{i\in S\_1} a\_i = \sum\_{j \in S\_2} a\_j$.

So, just pick: $G = \{ V, \emptyset \}$ with $|V| = n$, set $m = 2$ and assign weight $a\_i$ to node $u\_i$ for all $i = 1,...,n$; set $B = \frac{1}{2} \sum a\_i$, and set $K=0$ (arc costs and the acyclic constraints are irrelevant).

NOTE: my old answer was related to a different ACYCLIC PARTITION problem, and you can find it in the edits history below.

> **Comments:**
> **username_0**: K cannot be zero, because the problem states that K should be a positive integer.  
> **username_0**: Do you happen to know any approximation algorithms for the problem?  
> **username_2**: @Ricky: you can set $K=1$ (there are no arcs, so you are sure that the constraint is satisfied). If you complain about the empty arc set, you can build a dummy graph: pick a node $u$ and add directed edges from the others to it with cost 1 and set $K = |A|$ (the partition will always be acyclic and cannot break the cost constraints). But the matter is that in the current formulation there is an immediate reduction from PARTITION (thanks to the node weights), indeed in G&J they say it remains hard even for w(v)=c(a)=1 (but it should be a different question).  
> **username_2**: @Ricky: ... for what regards approximation, I don't know any algorithm :(  
> **username_0**: Ah, but once ACYCLIC PARTITION is proven to be NP-complete by reduction from PARTITION, any approximation algorithm for PARTITION would also count as an approximation algorithm for ACYCLIC PARTITION, right?  
> **username_2**: @Ricky: no, I don't think that it works, because to prove NP-hardness you only use a special and very restricted case of ACYCLIC PARTITION.  
> **username_0**: Indeed, to prove NP-completeness, you've used a special case of ACYCLIC PARTITION. But the end result is that PARTITION can be reduced to ACYCLIC PARTITION and vice-versa (you haven't done this in your answer though). If that is the case, then wouldn't any approximation algorithm for PARTITION be reducible to solve ACYCLIC PARTITION too?  
> **username_2**: @Ricky: no, to prove NP-completeness (NP-hardness to be more precise), you must only show a (polynomial time) reduction FROM an NP-complete problem (PARTITION in this case) TO your problem (ACYCLIC PARTITION in this case), and not the inverse.  
> **username_0**: I agree, I never said that we need to do the inverse also to PROVE NP-completeness. I'm just saying that once we've proven NP-completeness of ACYCLIC PARTITION by reduction from PARTITION, we can be sure that a reduction in the opposite direction exists as well. And since it exists, we can say that any approximation algorithm for one problem can also serve as an approximation algorithm for the other. Isn't this true?  
> **username_3**: @Ricky, no.  Poly-time reductions do not necessarily (and usually don't) preserve approximate solutions.  For that you need a particular kind of reduction called an approximation-preserving reduction.  

---

### Answer by username_4 on 2014-03-01. Score: 2

A useful reference is "Sitting Closer to Friends Than Enemies, Revisited" by Cygan, Pilipczuk, Pilipczuk and Wojtaszczyk, MFCS 2012. Not sure if the title should be interpreted literally though: it's probably better to keep your enemies close for various reasons (<http://www.askmen.com/money/mafioso_60/67_mafia.html>)


---

