5
$\begingroup$

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$?

Improve this question
$\endgroup$
  • 1
    $\begingroup$ Crossposted to Math SE $\endgroup$ – Ricky Mar 1 '14 at 14:19
  • $\begingroup$ 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. $\endgroup$ – Suresh Venkat Mar 1 '14 at 18:10
  • $\begingroup$ 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)? $\endgroup$ – Marzio De Biasi Mar 1 '14 at 21:50
  • $\begingroup$ @MarzioDeBiasi The problem is perfectly defined in A2.2 Cuts and Connectivity $\endgroup$ – Ricky Mar 2 '14 at 7:42
  • $\begingroup$ @SureshVenkat I'm sorry, I'll be sure to follow that henceforth. $\endgroup$ – Ricky Mar 2 '14 at 7:43
3
$\begingroup$

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.

Improve this answer
$\endgroup$
  • $\begingroup$ K cannot be zero, because the problem states that K should be a positive integer. $\endgroup$ – Ricky Mar 2 '14 at 7:45
  • $\begingroup$ Do you happen to know any approximation algorithms for the problem? $\endgroup$ – Ricky Mar 2 '14 at 8:10
  • $\begingroup$ @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). $\endgroup$ – Marzio De Biasi Mar 2 '14 at 10:13
  • $\begingroup$ @Ricky: ... for what regards approximation, I don't know any algorithm :( $\endgroup$ – Marzio De Biasi Mar 2 '14 at 10:15
  • $\begingroup$ 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? $\endgroup$ – Ricky Mar 2 '14 at 11:01
2
$\begingroup$

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)

Improve this answer
$\endgroup$

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.