[Model] MinimumDummyActivitiesPert

[isPANN]

---

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

Motivation

MINIMIZING DUMMY ACTIVITIES IN PERT NETWORKS (P120) from Garey & Johnson, A2 ND44. A classical NP-complete problem arising in project management. When converting an activity-on-node (AON) project representation to an activity-on-arc (AOA) PERT network, dummy activities (arcs without real work) are needed to encode precedence constraints. Since network computation time is proportional to the number of arcs, minimizing dummy activities directly impacts project scheduling efficiency.

Associated reduction rules:

• As source: None found in current rule set.
• As target: MinimumVertexCover → MinimumDummyActivitiesPert (issue [Rule] VERTEX COVER to MINIMIZING DUMMY ACTIVITIES IN PERT NETWORKS #374, Krishnamoorthy and Deo 1979)

Definition

Name: MinimumDummyActivitiesPert
Canonical name: Minimizing Dummy Activities in PERT Networks (also: Minimum Dummy Arc Problem)
Reference: Garey & Johnson, Computers and Intractability, A2 ND44

Mathematical definition:

INSTANCE: Directed acyclic graph G = (V,A) where vertices represent tasks and the arcs represent precedence constraints.
QUESTION: Find a PERT network corresponding to G with the minimum number of dummy activities, i.e., a directed acyclic graph G' = (V',A') where V' = {v_i^-, v_i^+: v_i in V} and {(v_i^-, v_i^+): v_i in V} subset of A', such that |A'| - |V| is minimized and there is a path from v_i^+ to v_j^- in G' if and only if there is a path from v_i to v_j in G.

Note: The GJ formulation is a decision problem with bound K ("is there a PERT network with K or fewer dummy activities?"). We implement the optimization version (minimize dummy arcs), which is more common in the literature (Krishnamoorthy & Deo 1979, Syslo 1984, Michael et al. 1993).

Variables

• Count: The number of potential dummy arcs to decide upon. In the worst case, this is O(|V|^2) (any pair of event nodes could potentially have a dummy arc). The decision is which dummy arcs to include in the PERT network.
• Per-variable domain: binary {0, 1} — whether a potential dummy arc between event nodes is included.
• Meaning: The variable assignment encodes the set of dummy arcs in the PERT network G'. A valid solution must preserve the reachability relation: v_i^+ can reach v_j^- in G' if and only if v_i can reach v_j in G. The metric is SolutionSize<i32>: the number of dummy arcs (|A'| - |V|), with Invalid if the reachability constraint is violated.

Schema (data type)

Type name: MinimumDummyActivitiesPert
Variants: none

Field	Type	Description
graph	DirectedGraph	The precedence DAG G = (V, A) where vertices are tasks (acyclicity enforced by constructor)

Notes:

• This is an optimization problem: Metric = SolutionSize<i32>, implementing OptimizationProblem with Direction::Minimize.
• Key getter methods: num_vertices() (= |V|, number of tasks), num_arcs() (= |A|, number of precedence constraints).
• The PERT network G' has event nodes (not task nodes). Each task v_i becomes an arc (v_i^-, v_i^+), and dummy arcs encode the precedence relations.
• The number of activity arcs is exactly |V| (one per task). Dummy arcs are the additional arcs beyond these |V| activity arcs.

Complexity

• Decision complexity: NP-complete (Krishnamoorthy and Deo, 1979; transformation from VERTEX COVER on graphs of degree <= 3).
• Best known exact algorithm: Brute force enumeration of all possible event-node merging strategies and dummy arc placements. No faster exact algorithm is known for the general case.
• Complexity string: "2^num_arcs" (brute force over all possible dummy arc configurations; no better exact algorithm is known)
• Polynomial special cases: Solvable in polynomial time for:
  • Interval orders (precedence is an interval order)
  • Two-dimensional partial orders
  • Series-parallel partial orders
• References:
  • M.S. Krishnamoorthy and N. Deo (1979). "Complexity of the minimum-dummy-activities problem in a PERT network." Networks, 9(3):189-194.
  • M.M. Syslo (1984). "On the computational complexity of the minimum-dummy-activities problem in a PERT network." Networks, 14(1):37-45. Alternative analysis and polynomial special cases.

Extra Remark

Full book text:

INSTANCE: Directed acyclic graph G = (V,A) where vertices represent tasks and the arcs represent precedence constraints, and a positive integer K <= |V|.
QUESTION: Is there a PERT network corresponding to G with K or fewer dummy activities, i.e., a directed acyclic graph G' = (V',A') where V' = {v_i^-, v_i^+: v in V} and {(v_i^-, v_i^+): v_i in V} subset of A', and such that |A'| <= |V|+K and there is a path from v_i^+ to v_j^- in G' if and only if there is a path from v_i to v_j in G?
Reference: [Krishnamoorthy and Deo, 1977b]. Transformation from VERTEX COVER.

How to solve

• It can be solved by (existing) bruteforce. Enumerate all possible dummy arc configurations (up to O(|V|^2) potential arcs) and verify the reachability constraint. Find the configuration minimizing dummy arcs.
• It can be solved by reducing to integer programming. Binary variable for each potential dummy arc, with reachability constraints (for every pair (i,j) with a path in G, ensure a path exists in G'; for every pair without a path in G, ensure no path in G'). Minimize the number of dummy arcs.
• Other: Heuristic algorithms (e.g., Syslo's algorithm) that find near-optimal PERT networks in polynomial time for many practical instances. Also reducible to Set Cover (Michael et al. 1993).

Example Instance

Instance (6 tasks with precedence constraints):

Precedence DAG G with 6 tasks {A, B, C, D, E, F} and 5 arcs:

• A → C (task A must complete before C starts)
• A → D
• B → D
• B → E
• C → F

Naive PERT network (no merging):

• 12 event nodes: A-, A+, B-, B+, C-, C+, D-, D+, E-, E+, F-, F+
• 6 activity arcs (one per task): (A-,A+), (B-,B+), (C-,C+), (D-,D+), (E-,E+), (F-,F+)
• 5 dummy arcs (one per precedence arc): (A+,C-), (A+,D-), (B+,D-), (B+,E-), (C+,F-)
• Total: 6 + 5 = 11 arcs, 5 dummy arcs

Optimal PERT network (with event-node merging):

Merge event nodes when a task has a single predecessor:

• Merge A+ = C- into node e1 (only predecessor of C is A) → eliminates dummy (A+,C-)
• Merge B+ = E- into node e3 (only predecessor of E is B) → eliminates dummy (B+,E-)
• Merge C+ = F- into node e2 (only predecessor of F is C) → eliminates dummy (C+,F-)

Final PERT network with 9 event nodes:

• Event nodes: A-, e1(=A+=C-), e2(=C+=F-), F+, B-, e3(=B+=E-), E+, D-, D+
• Activity arcs (6): A:(A-,e1), B:(B-,e3), C:(e1,e2), D:(D-,D+), E:(e3,E+), F:(e2,F+)
• Dummy arcs (2): (e1,D-) for A→D, (e3,D-) for B→D
• Total: 6 + 2 = 8 = |V| + 2

Reachability verification:

• A→C: A+ = e1 = C-, path of length 0 ✓
• A→D: e1 → D- via dummy ✓
• B→D: e3 → D- via dummy ✓
• B→E: B+ = e3 = E-, path of length 0 ✓
• C→F: C+ = e2 = F-, path of length 0 ✓
• A→F: e1 → e2 (task C) → F+ (task F), i.e., A→C→F ✓
• No spurious reachability (B cannot reach C or F; A cannot reach E) ✓

Optimal value: 2 dummy arcs

No further merging is possible: D has two predecessors (A and B), so D- cannot be merged with either e1 or e3 without creating spurious reachability between A and B's subnetworks.

[zazabap]

Issue Quality Check — Model

Check	Result	Details
Usefulness	⚠️ Warn	Novel problem, but no reductions connected to existing graph
Non-trivial	✅ Pass	Distinct feasibility constraints from all existing problems
Correctness	⚠️ Warn	References verified; GJ number and year need minor clarification
Well-written	❌ Fail	Name inconsistency, missing graph type, incomplete definition

Overall: 1 passed, 2 warnings, 1 failed

---

Usefulness

The problem does not currently exist in the codebase (confirmed via pred show). It is listed in Garey & Johnson's appendix under Network Design, and is a classical NP-complete problem from project management.

However, the issue lists no reduction rules as source and only one unverified association as target ("R65: Vertex Cover to Minimizing Dummy Activities in PERT Networks"). Without at least one concrete, planned reduction rule connecting this problem to the existing reduction graph, this problem would be an orphan node — it cannot be reached from or reduce to any existing problem. The motivation section explains the practical relevance well, but does not address graph connectivity.

Verdict: Warn — the problem is novel and legitimate, but the issue should specify at least one concrete reduction rule (likely from MinimumVertexCover, per the NP-completeness proof) that will be implemented.

---

Non-trivial

This problem has genuinely distinct feasibility constraints and structure from all 24 existing problems. The input is a DAG representing task precedence, and the feasibility condition involves constructing a PERT network (activity-on-arc representation) that preserves reachability while minimizing dummy arcs. No existing problem in the codebase captures this structure.

Verdict: Pass.

---

Correctness

Reference verification:

1. Krishnamoorthy and Deo (1979) — "Complexity of the minimum-dummy-activities problem in a PERT network," Networks, 9(3):189-194. Verified. The paper exists and proves NP-completeness via transformation from Vertex Cover on degree-3 graphs. The issue correctly describes the reduction source and the NP-completeness result.

2. Syslo (1984) — "On the computational complexity of the minimum-dummy-activities problem in a PERT network," Networks, 14(1):37-45. Verified. The paper exists and provides alternative analysis plus polynomial special cases.

3. Garey & Johnson reference — The issue claims "A2 ND44." The problem is indeed in the Network Design (ND) section of GJ's appendix, though the exact numbering could not be independently verified from online sources. The GJ book cites "Krishnamoorthy and Deo, 1977b" (a tech report predating the 1979 journal publication); the issue cites the 1979 journal version, which is fine.

Minor issues:

• The issue title says MinimizingDummyActivitiesPert but the body says MinimumDummyActivitiesPert — these are inconsistent (see Well-written section).
• The complexity string "2^num_tasks" is a crude brute-force bound. No better exact algorithm was found in the literature, so this is acceptable as a placeholder, but it should be noted that this is not a tight bound from any specific algorithm paper.

Verdict: Warn — references are real and support the claims, but the year citation style ("1977b" vs "1979") and GJ numbering could not be fully cross-checked.

---

Well-written

Several issues found:

4a — Name inconsistency (Fail):

• The issue title uses MinimizingDummyActivitiesPert but the body uses MinimumDummyActivitiesPert. Per project naming conventions, optimization problems use Minimum/Maximum prefix. The correct name should be MinimumDummyActivitiesPert (consistent with MinimumVertexCover, MinimumDominatingSet, etc.). The title should be updated to match.

4a — Missing graph type (Fail):

• The schema references DirectedAcyclicGraph as a type, but no such type exists in the codebase. The project currently supports SimpleGraph, PlanarGraph, BipartiteGraph, UnitDiskGraph, KingsSubgraph, and TriangularSubgraph — all undirected. Implementing this problem would require either:

  • Adding a new DirectedAcyclicGraph type to the codebase, or
  • Representing the DAG differently (e.g., adjacency matrix, or a new graph module)

  The issue should acknowledge this dependency and describe the planned approach.

4a — Decision vs Optimization ambiguity (Fail):

• The issue defines the problem as a decision problem (Metric = bool, "is there a PERT network with K or fewer dummy activities?") but also mentions an optimization version ("minimize K"). The issue should commit to one formulation. Looking at the project's existing satisfaction problems (e.g., Satisfiability, KSatisfiability), the decision formulation is fine, but the schema must then include the dummy_bound field as described. The "Notes" section hedges between both without committing.

4b — Definition completeness:

• The formal definition (from GJ) is complete and well-stated. The reachability condition is clearly specified.

4c — Symbol consistency:

• Symbols are generally consistent between sections. The definition uses G = (V, A) and this is carried through.
• The getter method num_precedence_arcs() is proposed for |A|, which is reasonable.

4d — Example quality (Warn):

• The example with 6 tasks is reasonable in size and non-trivial.
• The worked solution shows the merging process step by step, which is good.
• However, the merging steps are somewhat hand-wavy ("Can merge D^- to receive from both A^+ and B^+") — a more rigorous step-by-step construction of the final PERT network (listing all nodes and arcs) would be more implementable.

Verdict: Fail — name inconsistency between title and body, missing DirectedAcyclicGraph type dependency, and ambiguous decision/optimization formulation.

---

Recommendations

• Fix the name: Use MinimumDummyActivitiesPert consistently (title and body). This follows the Minimum prefix convention.
• Address the DAG type: Either propose adding DirectedAcyclicGraph as a prerequisite model issue, or describe an alternative representation (e.g., storing the DAG as an adjacency list in a custom struct without using the graph type system).
• Commit to one formulation: Choose either decision (SatisfactionProblem with dummy_bound) or optimization (OptimizationProblem minimizing dummy count). The decision version is more faithful to the GJ definition.
• Add a planned reduction rule: At minimum, propose a MinimumVertexCover -> MinimumDummyActivitiesPert rule (which is the NP-completeness proof transformation) to ensure the problem connects to the existing reduction graph.
• Improve the example: Show the final PERT network explicitly — list all event nodes and all arcs (activity + dummy) in the optimized solution.

[GiggleLiu]

Fix-issue changelog

• Fixed YAML frontmatter title from MinimizingDummyActivitiesPert to MinimumDummyActivitiesPert
• Added explicit reference to rule issue [Rule] VERTEX COVER to MINIMIZING DUMMY ACTIVITIES IN PERT NETWORKS #374 (MinimumVertexCover → MinimumDummyActivitiesPert) in Associated reduction rules
• Switched from decision (SatisfactionProblem with dummy_bound) to optimization framing (OptimizationProblem, SolutionSize<i32>, Direction::Minimize) — matches literature consensus (Krishnamoorthy & Deo 1979, Syslo 1984, Michael et al. 1993)
• Removed dummy_bound field from schema (optimization minimizes directly)
• Changed schema type from DirectedAcyclicGraph (nonexistent) to DirectedGraph (existing type, DAG enforced by constructor)
• Renamed getter num_precedence_arcs() to num_arcs() (standard DirectedGraph getter)
• Updated complexity string from "2^num_tasks" to "2^num_arcs" with note that no better exact algorithm is known
• Replaced broken example (claimed optimal=3, actual optimal=2, hand-wavy merging) with fully explicit PERT network construction showing optimal=2 dummy arcs, including complete reachability verification

Applied by /fix-issue.