[Model] AcyclicPartition

[isPANN]

---

name: Problem
about: Propose a new problem type
title: "[Model] AcyclicPartition"
labels: model
assignees: ''

Motivation

ACYCLIC PARTITION from Garey & Johnson, A2 ND15. An NP-complete graph partitioning problem on directed graphs. Given a directed graph with vertex weights and arc costs, the problem asks for a partition of the vertices into bounded-weight groups such that the quotient graph (where groups become super-nodes with arcs between groups inheriting from original arcs) is acyclic, while also bounding the total inter-group arc cost. This problem arises in task scheduling, parallel computation, and automatic differentiation where preserving topological ordering across partitions is essential.

Associated rules:

• X3C -> AcyclicPartition (ND15) [Garey & Johnson, 1979]

Definition

Name: AcyclicPartition
Canonical name: Acyclic Partition (also: Acyclic Graph Partitioning, DAG Partitioning)
Reference: Garey & Johnson, Computers and Intractability, A2 ND15

Mathematical definition:

INSTANCE: Directed graph G = (V, A), weight w(v) ∈ Z⁺ for each v ∈ V, cost c(a) ∈ Z⁺ for each a ∈ A, positive integers B and K.
QUESTION: Is there a partition of V into disjoint sets V₁, V₂, ..., Vₘ such that:

1. The quotient graph G' = (V', A'), where V' = {V₁, V₂, ..., Vₘ} and (Vᵢ, Vⱼ) ∈ A' if and only if there exist vᵢ ∈ Vᵢ and vⱼ ∈ Vⱼ with (vᵢ, vⱼ) ∈ A, is acyclic (a DAG),
2. For each Vᵢ, the sum of vertex weights ∑{v ∈ Vᵢ} w(v) ≤ B, and
3. The total cost of inter-partition arcs ∑{(u,v) ∈ A : u ∈ Vᵢ, v ∈ Vⱼ, i ≠ j} c(u,v) ≤ K?

Variables

• Count: n = |V| variables (one per vertex)
• Per-variable domain: {0, 1, ..., n-1} — the partition index assigned to each vertex
• Meaning: variable x_v = i means vertex v is assigned to partition Vᵢ. A valid assignment satisfies: (1) the quotient graph on {V₁, ..., Vₘ} is a DAG, (2) for each Vᵢ, ∑{v ∈ Vᵢ} w(v) ≤ B, and (3) the total cost of inter-partition arcs ≤ K.

Dims

Config space: [n; n] — each of the n vertices can be assigned to any of n partition groups (0-indexed). This matches the KColoring pattern ([k; n] for k colors).

Schema (data type)

Type name: AcyclicPartition<W>
Variants: weight type W (default i32). DirectedGraph is used as a concrete type (not a type parameter), consistent with MinimumFeedbackArcSet, MinimumFeedbackVertexSet, and MultipleChoiceBranching.

Field	Type	Description
graph	DirectedGraph	The directed graph G = (V, A)
vertex_weights	Vec<W>	Weight w(v) for each vertex v
arc_costs	Vec<W>	Cost c(a) for each arc a, indexed in the same order as graph.arcs()
weight_bound	W::Sum	Maximum total vertex weight B per partition group
cost_bound	W::Sum	Maximum total inter-partition arc cost K

Notes:

• This is a satisfaction (decision) problem: Metric = bool, implementing SatisfactionProblem.
• Parallels MultipleChoiceBranching<W> (satisfaction problem on DirectedGraph with weight threshold).
• variant_params![W], declare_variants! entry: default sat AcyclicPartition<i32> => "num_vertices^num_vertices".

Size fields

Getter	Meaning
num_vertices()	Number of vertices, |V| (delegates to self.graph.num_vertices())
num_arcs()	Number of arcs, |A| (delegates to self.graph.num_arcs())

Complexity

• Decision complexity: NP-complete (Garey and Johnson, 1979; transformation from X3C). NP-complete even if all v ∈ V have w(v) = 1 and all a ∈ A have c(a) = 1.
• Best known exact algorithm: Exhaustive enumeration of all partition assignments in O*(n^n) time, where n = |V|. For the case when the number of parts k is fixed, dynamic programming over subset assignments gives O(k^n · poly(n)) time.
• Concrete complexity string: "num_vertices^num_vertices"
• Parameterized complexity: Moser et al. (2017), "Fixed-Parameter Algorithms for DAG Partitioning," give an FPT algorithm running in O(2^k · (n+m)) time where k is the total cut cost.
• Special cases:
  • Can be solved in polynomial time if G contains a Hamiltonian path (verifiable in O(V+A) time for acyclic digraphs) [Kernighan, 1971].
  • If G is a tree, the general problem is NP-complete in the ordinary sense but solvable in pseudo-polynomial time [Lukes, 1974].
  • The tree problem can be solved in polynomial time if all edge weights are equal [Hadlock, 1974] or if all vertex weights are equal [Garey and Johnson, 1979].
• References:
  • M.R. Garey, D.S. Johnson (1979). "Computers and Intractability." W.H. Freeman.
  • J.A. Lukes (1974). "Efficient Algorithm for the Partitioning of Trees." IBM Journal of Research and Development, 18(3):217-224.
  • B.W. Kernighan (1971). "Optimal Sequential Partitions of Graphs." Journal of the ACM, 18(1):34-40.
  • R. Moser, R. Niedermeier, M. Schubert (2017). "Fixed-Parameter Algorithms for DAG Partitioning." Discrete Applied Mathematics.

How to solve

• It can be solved by (existing) bruteforce. Enumerate all possible partition assignments of V (n^n configurations), check acyclicity of quotient graph, weight bounds, and cost bounds.
• It can be solved by reducing to integer programming. Integer variable per vertex indicating partition assignment, with acyclicity enforced via topological ordering constraints (auxiliary variables for group ordering).
• Other: Multilevel heuristic algorithms (dagP tool), ILP formulations for exact solutions.

Example Instance

Directed graph G with 6 vertices {0, 1, 2, 3, 4, 5} and 8 arcs:

• Arcs (indexed 0..7): (0→1), (0→2), (1→3), (1→4), (2→4), (2→5), (3→5), (4→5)
• Vertex weights: w = [2, 3, 2, 1, 3, 1]
• Arc costs: all c(a) = 1
• Weight bound B = 5, Cost bound K = 5

Config (partition assignment): [0, 1, 0, 2, 2, 2]

• Vertex 0 → group 0, vertex 1 → group 1, vertex 2 → group 0, vertices 3,4,5 → group 2.

Partition groups:

• V₀ = {0, 2} (weight 2 + 2 = 4 ≤ 5) ✓
• V₁ = {1} (weight 3 ≤ 5) ✓
• V₂ = {3, 4, 5} (weight 1 + 3 + 1 = 5 ≤ 5) ✓

Quotient graph verification:

• V₀→V₁: arc (0→1) crosses from V₀ to V₁
• V₀→V₂: arcs (2→4), (2→5) cross from V₀ to V₂
• V₁→V₂: arcs (1→3), (1→4) cross from V₁ to V₂
• Quotient graph edges: V₀→V₁, V₀→V₂, V₁→V₂ — this is a DAG (topological order: V₀, V₁, V₂) ✓

Inter-partition arc cost:

• Arcs crossing partitions: (0→1), (2→4), (2→5), (1→3), (1→4) = 5 arcs × cost 1 = total cost 5 ≤ K = 5 ✓

Intra-partition arcs (not counted):

• Within V₀: (0→2) — cost not counted
• Within V₂: (3→5), (4→5) — costs not counted

Answer: YES — evaluate([0, 1, 0, 2, 2, 2]) returns true.

Expected Outcome

The config [0, 1, 0, 2, 2, 2] (partition V₀ = {0, 2}, V₁ = {1}, V₂ = {3, 4, 5}) is a valid solution because:

1. Acyclicity: quotient graph has edges V₀→V₁, V₀→V₂, V₁→V₂ which form a DAG
2. Weight bound: group weights are 4, 3, 5, all ≤ B = 5
3. Cost bound: inter-partition arc cost is 5 ≤ K = 5

There are 4 distinct valid configs for this instance (verified by brute-force enumeration of all 46656 assignments):

1. [0, 0, 1, 2, 1, 2] → {0,1}, {2,4}, {3,5} — weights 5, 5, 2; cost 5
2. [0, 0, 1, 2, 2, 2] → {0,1}, {2}, {3,4,5} — weights 5, 2, 5; cost 5
3. [0, 1, 0, 1, 2, 2] → {0,2}, {1,3}, {4,5} — weights 4, 4, 4; cost 5
4. [0, 1, 0, 2, 2, 2] → {0,2}, {1}, {3,4,5} — weights 4, 3, 5; cost 5

(Note: many more configs map to the same partitions via label permutation; the 4 listed above use canonical label ordering.)

With K = 4, no valid partition exists (answer: NO). The minimum feasible cost for B = 5 is exactly 5.

Extra Remark

Full book text:

INSTANCE: Directed graph G = (V,A), weight w(v) in Z+ for each v in V, cost c(a) in Z+ for each a in A, positive integers B and K.
QUESTION: Is there a partition of V into disjoint sets V1,V2,...,Vm such that the directed graph G' = (V',A'), where V' = {V1,V2,...,Vm}, and (Vi,Vj) in A' if and only if (vi,vj) in A for some vi in Vi and some vj in Vj, is acyclic, such that the sum of the weights of the vertices in each Vi 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?

Reference: [Garey and Johnson, ----]. Transformation from X3C.
Comment: Remains NP-complete even if all v in V have w(v) = 1 and all a in A have c(a) = 1. Can be solved in polynomial time if G contains a Hamiltonian path (a property that can be verified in polynomial time for acyclic digraphs) [Kernighan, 1971]. If G is a tree the general problem is NP-complete in the ordinary sense, but can be solved in pseudo-polynomial time [Lukes, 1974]. The tree problem can be solved in polynomial time if all edge weights are equal (see [Hadlock, 1974]) or if all vertex weights are equal [Garey and Johnson, ----].

[zazabap]

Issue Quality Check — Model

Check	Result	Details
Usefulness	✅ Pass	Novel problem not yet in reduction graph
Non-trivial	✅ Pass	Distinct feasibility constraints (acyclicity of quotient graph + weight/cost bounds) from all existing problems
Correctness	❌ Fail	Contradictory NP-completeness reduction source; Kernighan thesis year wrong; GJ number inconsistency
Well-written	❌ Fail	Example is incomplete/broken; DirectedGraph type does not exist in codebase; notation issues

Overall: 2 passed, 0 warnings, 2 failed

---

Usefulness

Pass. The problem AcyclicPartition does not exist in the current codebase (24 problems currently implemented). The motivation is reasonable — acyclic graph partitioning arises in task scheduling, parallel computation, and automatic differentiation. The associated rule (3SAT → AcyclicPartition) would connect it to the existing reduction graph through KSatisfiability.

Non-trivial

Pass. This is a genuinely distinct problem. No existing problem in the codebase involves directed graphs with both vertex weight bounds per partition and inter-partition arc cost bounds, combined with an acyclicity constraint on the quotient graph. It is not a variant or renaming of any existing model.

Correctness

Fail. Several factual issues found:

1. Contradictory reduction source: The Definition/Complexity section states the NP-completeness proof is via "transformation from 3SAT," but the Extra Remark section (which reproduces the book text) states "Transformation from X3C" (Exact 3-Cover). These are different reductions. The Garey & Johnson book uses X3C, not 3SAT. The issue's "Associated rules" section also says "3SAT -> ACYCLIC PARTITION" — this should be reconciled with the book's claim.

2. GJ number inconsistency: The Motivation says "P91" while the Definition says "A2 ND15." The "P91" designation is unclear — it could be a page number or a different numbering scheme, but it should be clarified or removed.

3. Kernighan thesis year: The issue cites "Kernighan (1971)" but the PhD thesis was completed at Princeton in 1969, not 1971. (The more commonly cited Kernighan-Lin paper is from 1970 in Bell System Technical Journal.)

4. Lukes 1974 reference: Verified — J. A. Lukes, "Efficient Algorithm for the Partitioning of Trees," IBM Journal of Research and Development, 18(3):217–224, 1974. The page range in the issue (217-224) is correct.

5. Garey & Johnson 1979: Verified — the book exists and is already in the project bibliography (garey1979 in references.bib).

6. Complexity claims are vague: The "best known exact algorithm" section mentions O*(n^n) exhaustive enumeration and O(k^n) DP, but does not identify a specific named algorithm with a precise time bound. For declare_variants!, a concrete complexity string is needed (e.g., "n^n" or "k^n"). The issue should specify which bound to use.

Well-written

Fail. Multiple issues:

Example is broken

The example section is disorganized and does not provide a single clean worked instance:

• The first attempted partition (V2 = {1,4}) is immediately flagged as INVALID
• The "revised partition" exceeds the cost bound K=4 (cost = 6)
• The author then tries B=5, K=5 which still fails
• The final conclusion is "With K=6: answer is YES. With K=4: answer is NO" — but the stated instance has K=4, so the answer is NO

A proper example should provide instance parameters where the answer is YES and show a valid partition. The current example reads like scratch work, not a finished illustration.

Schema references non-existent type

The schema proposes DirectedGraph as a type, but no DirectedGraph type exists in the codebase. The existing graph types are: SimpleGraph, PlanarGraph, BipartiteGraph, UnitDiskGraph, KingsSubgraph, TriangularSubgraph — all undirected. Implementing this model would first require adding directed graph support, which is a significant infrastructure change that should be noted.

Missing getter method validation

The schema claims getter methods num_vertices() and num_arcs(), but since there is no DirectedGraph type, these cannot be validated. The overhead field names for future reduction rules are also unverifiable.

Notation issues

• The Variables section uses m (number of partitions) but this is not carried through consistently — the Example section just uses numeric partition labels
• The Schema uses arc_costs as Vec<i32> indexed by arc, but the ordering convention (how arcs map to vector indices) is not specified
• vertex_weights uses i32 but the mathematical definition specifies Z+ (positive integers), so the type should perhaps be u32 or validation should enforce positivity

Missing sections

• No declare_variants! complexity string is proposed (needed for implementation)
• The "How to solve" section checks brute-force and ILP but gives no detail on how acyclicity would be enforced in an ILP formulation

---

Recommendations

• Fix the NP-completeness reduction source to match Garey & Johnson (X3C, not 3SAT). Update the "Associated rules" accordingly.
• Correct the Kernighan thesis year to 1969.
• Provide a clean, small example with parameters where the answer is YES. For instance, use a 4-vertex DAG with carefully chosen weights and bounds.
• Address the DirectedGraph infrastructure gap — either note that a new graph type is needed as a prerequisite, or propose an alternative representation (e.g., adjacency list stored directly in the struct).
• Specify a concrete complexity string for declare_variants!.
• Clarify the "P91" reference or remove it.