[Rule] Clique to Minimum Tardiness Sequencing

[isPANN]

Source: MaximumClique
Target: MinimumTardinessSequencing
Motivation: Establishes NP-completeness of MinimumTardinessSequencing by encoding J-clique selection as a scheduling problem where meeting an early edge-task deadline forces exactly J vertex-tasks and J(J−1)/2 edge-tasks to be scheduled early — which is only possible if those tasks form a complete J-vertex subgraph.

Reference: Garey & Johnson, Computers and Intractability, Theorem 3.10, p.73

⚠️ On Hold — Decision vs Optimization mismatch

This reduction is a Karp reduction between decision problems: "Does G have a J-clique?" ↔ "Is there a schedule with ≤ K tardy tasks?" The construction depends on the clique size parameter J (used to set edge deadlines = J(J+1)/2 and tardiness bound K = |E| − J(J−1)/2).

However, both MaximumClique and MinimumTardinessSequencing are optimization problems in the codebase (OptimizationProblem trait). The ReduceTo trait maps a source instance to a target instance without external parameters, so this reduction cannot be implemented as-is.

A clean optimization-to-optimization reformulation does not exist in the literature — setting a fixed deadline either trivializes the problem (all tasks fit) or encodes densest-subgraph rather than clique.

Unblocked by: a future KClique satisfaction model that carries the threshold parameter J.

Reduction Algorithm

MINIMUM TARDINESS SEQUENCING
INSTANCE: A set T of "tasks," each t ∈ T having "length" 1 and a "deadline" d(t) ∈ Z+, a partial order ≤ on T, and a non-negative integer K ≤ |T|.
QUESTION: Is there a "schedule" σ: T → {0,1, . . . , |T|−1} such that σ(t) ≠ σ(t') whenever t ≠ t', such that σ(t) < σ(t') whenever t ≤ t', and such that |{t ∈ T: σ(t)+1 > d(t)}| ≤ K?

Theorem 3.10 MINIMUM TARDINESS SEQUENCING is NP-complete.
Proof: Let the graph G = (V,E) and the positive integer J ≤ |V| constitute an arbitrary instance of CLIQUE. The corresponding instance of MINIMUM TARDINESS SEQUENCING has task set T = V ∪ E, K = |E|−(J(J−1)/2), and partial order and deadlines defined as follows:

t ≤ t'  ⟺  t ∈ V, t' ∈ E, and vertex t is an endpoint of edge t'

d(t) = { J(J+1)/2    if t ∈ E
        { |V|+|E|    if t ∈ V

Thus the "component" corresponding to each vertex is a single task with deadline |V|+|E|, and the "component" corresponding to each edge is a single task with deadline J(J+1)/2. The task corresponding to an edge is forced by the partial order to occur after the tasks corresponding to its two endpoints in the desired schedule, and only edge tasks are in danger of being tardy (being completed after their deadlines).

It is convenient to view the desired schedule schematically, as shown in Figure 3.10. We can think of the portion of the schedule before the edge task deadline as our "clique selection component." There is room for J(J+1)/2 tasks before this deadline. In order to have no more than the specified number of tardy tasks, at least J(J−1)/2 of these "early" tasks must be edge tasks. However, if an edge task precedes this deadline, then so must the vertex tasks corresponding to its endpoints. The minimum possible number of vertices that can be involved in J(J−1)/2 distinct edges is J (which can happen if and only if those edges form a complete graph on those J vertices). This implies that there must be at least J vertex tasks among the "early" tasks. However, there is room for at most

(J(J+1)/2) − (J(J−1)/2) = J

vertex tasks before the edge task deadline. Therefore, any such schedule must have exactly J vertex tasks and exactly J(J−1)/2 edge tasks before this deadline, and these must correspond to a J-vertex clique in G. Conversely, if G contains a complete subgraph of size J, the desired schedule can be constructed as in Figure 3.10. ∎

Summary:
Given a MaximumClique instance (G, J) where G = (V, E), construct a MinimumTardinessSequencing instance as follows:

1. Task set: Create one task t_v for each vertex v ∈ V and one task t_e for each edge e ∈ E. Thus |T| = |V| + |E|.
2. Deadlines: Set d(t_v) = |V| + |E| for all vertex tasks (very late, never tardy in practice) and d(t_e) = J(J+1)/2 for all edge tasks (an early "clique selection" deadline).
3. Partial order: For each edge e = {u, v} ∈ E, add precedence constraints t_u ≤ t_e and t_v ≤ t_e (both endpoints must be scheduled before the edge task).
4. Tardiness bound: Set K = |E| − J(J−1)/2. This is the maximum allowed number of tardy tasks (edge tasks that miss their early deadline).
5. Solution extraction: In any valid schedule with ≤ K tardy tasks, at least J(J−1)/2 edge tasks must be scheduled before time J(J+1)/2. The precedence constraints force their endpoints (vertex tasks) to also be early. A counting argument shows exactly J vertex tasks and J(J−1)/2 edge tasks are early, and those edges must form a complete subgraph on those J vertices — a J-clique in G.

Key invariant: G has a J-clique if and only if T has a valid schedule (respecting partial order) with at most K = |E| − J(J−1)/2 tardy tasks.

Size Overhead

Symbols:

• n = num_vertices of source graph G
• m = num_edges of source graph G
• J = clique size parameter from source instance

Target metric (code name)	Polynomial (using symbols above)
num_tasks	num_vertices + num_edges
num_precedences	2 * num_edges

Derivation:

• One task per vertex in G plus one task per edge in G → |T| = n + m
• The partial order has exactly 2·m precedence pairs (two vertex tasks per edge task)
• K = m − J(J−1)/2 is derived from the source instance parameters; the maximum possible K (when J=1) is m − 0 = m, and minimum K (when J=|V|) is m − |V|(|V|−1)/2 which may be 0 if G is complete

Note: The overhead expressions depend on J (the clique size parameter), which is not a size field of MaximumClique. The num_tasks and num_precedences metrics are not currently registered as size_fields on MinimumTardinessSequencing. Both issues are blocked on resolving the decision/optimization mismatch noted above.

Validation Method

• Closed-loop test: reduce a MaximumClique instance (G, J) to MinimumTardinessSequencing, solve the target with BruteForce (try all permutations σ respecting the partial order), check whether any valid schedule has at most K tardy tasks
• Verify the counting argument: in a satisfying schedule, identify the J vertex-tasks and J(J−1)/2 edge-tasks scheduled before time J(J+1)/2, confirm the corresponding subgraph is a complete graph on J vertices
• Test with K₄ (complete graph on 4 vertices) and J = 3: should find a valid schedule (any 3-clique works)
• Test with a triangle-free graph (e.g., C₅) and J = 3: should find no valid schedule since no 3-clique exists
• Verify the partial order is respected in all candidate schedules by checking that every edge task is scheduled after both its endpoint vertex tasks

Example

Source instance (MaximumClique):
Graph G with 4 vertices {0, 1, 2, 3} and 5 edges:

• Edges: {0,1}, {0,2}, {1,2}, {1,3}, {2,3}
• (K₄ minus the edge {0,3}: vertices 0,1,2 form a triangle, plus vertex 3 connected to 1 and 2)
• G contains a 3-clique: {0, 1, 2} (edges {0,1}, {0,2}, {1,2} all present)
• Clique parameter: J = 3

Constructed target instance (MinimumTardinessSequencing):

Tasks (|V| + |E| = 4 + 5 = 9 total):

• Vertex tasks: t₀, t₁, t₂, t₃ (deadlines d = |V| + |E| = 9)
• Edge tasks: t₀₁, t₀₂, t₁₂, t₁₃, t₂₃ (deadlines d = J(J+1)/2 = 3·4/2 = 6)

Partial order (endpoints must precede edge task):

• t₀ ≤ t₀₁, t₁ ≤ t₀₁
• t₀ ≤ t₀₂, t₂ ≤ t₀₂
• t₁ ≤ t₁₂, t₂ ≤ t₁₂
• t₁ ≤ t₁₃, t₃ ≤ t₁₃
• t₂ ≤ t₂₃, t₃ ≤ t₂₃

Tardiness bound: K = |E| − J(J−1)/2 = 5 − 3·2/2 = 5 − 3 = 2

Constructed schedule (from clique {0, 1, 2}):

Early portion (positions 0–5, before deadline 6 for edge tasks):

Schedule σ:

• σ(t₀) = 0 (position 0, finishes at 1 ≤ d=9 ✓)
• σ(t₁) = 1 (position 1, finishes at 2 ≤ d=9 ✓)
• σ(t₂) = 2 (position 2, finishes at 3 ≤ d=9 ✓)
• σ(t₀₁) = 3 (finishes at 4 ≤ d=6 ✓, not tardy — endpoints t₀,t₁ scheduled earlier ✓)
• σ(t₀₂) = 4 (finishes at 5 ≤ d=6 ✓, not tardy — endpoints t₀,t₂ scheduled earlier ✓)
• σ(t₁₂) = 5 (finishes at 6 ≤ d=6 ✓, not tardy — endpoints t₁,t₂ scheduled earlier ✓)

Late portion (positions 6–8, after deadline 6 for edge tasks):

• σ(t₃) = 6 (finishes at 7 ≤ d=9 ✓, not tardy)
• σ(t₁₃) = 7 (finishes at 8 > d=6 — TARDY ✗)
• σ(t₂₃) = 8 (finishes at 9 > d=6 — TARDY ✗)

Tardy tasks: {t₁₃, t₂₃}, count = 2 ≤ K = 2 ✓
Partial order respected: all vertex tasks precede their edge tasks ✓

Solution extraction:
The J(J−1)/2 = 3 edge tasks scheduled before deadline 6 are t₀₁, t₀₂, t₁₂. Their endpoint vertex tasks are {t₀, t₁, t₂}. These correspond to vertices {0, 1, 2} forming a triangle (complete subgraph) in G — a 3-clique ✓.

[zazabap]

Issue Quality Check — Rule

Check	Result	Details
Usefulness	✅ Pass	No existing path; target problem is novel (not yet in codebase)
Non-trivial	✅ Pass	Genuine structural transformation with vertex/edge task construction, partial order, and counting argument
Correctness	⚠️ Warn	Reference is credible (Garey & Johnson, Theorem 3.10) and the construction matches the well-known textbook proof, but the reduction is between decision problems while the codebase's MaximumClique is an optimization problem
Well-written	⚠️ Warn	Thorough and detailed, but has structural issues for implementation in this codebase (see below)

Overall: 2 passed, 0 failed, 2 warnings

---

Usefulness

MinimumTardinessSequencing does not exist in the codebase. There is no existing path from MaximumClique to any scheduling problem. This would be a novel reduction adding a new problem domain (scheduling) to the reduction graph.

Note: The target model must be implemented first before this rule can be added.

Non-trivial

The reduction involves genuine structural transformation:

• Vertex tasks and edge tasks with different deadline regimes
• A partial order derived from graph incidence structure
• A counting argument showing the "clique selection component" forces exactly J vertex tasks and J(J-1)/2 edge tasks before the deadline
• Solution extraction via identifying early-scheduled tasks

This is not a variable substitution, subtype coercion, or identity reduction.

Correctness

Reference verification: The citation is Garey & Johnson, Computers and Intractability, Theorem 3.10, p.73. The book (garey1979) is already in the project bibliography at docs/paper/references.bib. Web search confirms that the reduction from Clique to a scheduling problem with precedence constraints, vertex/edge tasks, and deadline-based clique selection is a well-known NP-completeness proof from this textbook. The construction in the issue matches the standard proof, and the issue even includes a verbatim quote.

Structural concern: The reduction as stated is between decision problems: "Does G have a J-clique?" maps to "Is there a schedule with at most K tardy tasks?" However, MaximumClique in this codebase is an OptimizationProblem (find the maximum weight clique), not a SatisfactionProblem. The reduction requires a specific clique size parameter J as input, which is not part of the MaximumClique optimization formulation. This creates a fundamental mismatch with the codebase's ReduceTo trait system, which maps a source problem instance to a target problem instance while preserving optimality.

To implement this as a valid reduction in the codebase, one of the following would be needed:

1. A decision variant of Clique (e.g., KClique as a SatisfactionProblem with parameter J), or
2. Reformulating the reduction to work with the optimization version (minimize total tardiness rather than deciding feasibility with a bound K)

Well-written

Strengths:

• The reduction algorithm is exceptionally detailed with a verbatim textbook quote plus a clear step-by-step summary
• The example is fully worked with a non-trivial graph (4 vertices, 5 edges), showing the complete schedule construction, tardiness counting, and solution extraction
• The validation method section includes multiple test cases with clear expected outcomes
• All symbols are defined and used consistently

Issues to address:

1. Source problem naming: The issue uses "CLIQUE" but the codebase name is MaximumClique. As noted above, the reduction assumes a decision formulation, not the optimization formulation.

2. Size overhead table is incomplete: Only num_tasks is listed. The target MinimumTardinessSequencing problem would also need metrics for:

   • Number of precedence pairs (2 * num_edges)
   • The tardiness bound K
   • The deadline value for edge tasks

3. Source num_edges is not a size field: The overhead formula uses num_edges but MaximumClique's size_fields only includes num_vertices. A num_edges getter would need to be added, or the overhead must be expressed differently.

4. Decision vs. optimization mismatch: The issue does not address how this reduction integrates with the codebase's trait system where MaximumClique is an OptimizationProblem and the target would be a SatisfactionProblem.

Recommendations

• Consider whether this reduction should instead source from a dedicated decision problem (e.g., a new KClique satisfaction problem) or whether the target should be reformulated as an optimization problem (minimize total tardiness)
• Expand the size overhead table to cover all target problem metrics
• Clarify how the clique size parameter J is derived from the source MaximumClique instance

[zazabap]

Issue Quality Check — Rule

Check	Result	Details
Usefulness	⚠️ Warn	Target problem MinimumTardinessSequencing does not exist in the codebase; requires a [Model] issue first
Non-trivial	✅ Pass	Genuine structural transformation: gadget construction with tasks, partial order, and deadline encoding
Correctness	✅ Pass	Reference is Garey & Johnson (1979), Theorem 3.10 — book is in project bibliography; proof text is consistent with known G&J Chapter 3 style
Well-written	⚠️ Warn	Overhead table is incomplete; source problem name uses informal alias "CLIQUE"

Overall: 2 passed, 0 failed, 2 warnings

---

Usefulness

The target problem MinimumTardinessSequencing does not currently exist in the reduction graph (pred show MinimumTardinessSequencing fails). This means the rule cannot be implemented until a corresponding [Model] issue is created and the target problem is added to the codebase. No existing path from MaximumClique to any scheduling problem exists, so if the model is added, this reduction would be novel. Pass on novelty, but warning on dependency.

Non-trivial

The reduction is genuinely non-trivial. It constructs:

• A task set from both vertices and edges of the source graph
• A partial order encoding adjacency (vertex tasks must precede their incident edge tasks)
• Deadline values computed from the clique parameter J
• A tardiness bound K = |E| - J(J-1)/2 that encodes the clique constraint via a counting argument

This is a classic gadget-based NP-completeness reduction, not a variable substitution or subtype coercion.

Correctness

The cited reference is Garey & Johnson, Computers and Intractability, Theorem 3.10, p.73. This book is already in the project bibliography as garey1979. The issue includes what appears to be a verbatim quotation of the theorem statement and proof from the book, including the figure reference (Figure 3.10).

The reduction structure (CLIQUE to a scheduling problem with precedence constraints) is consistent with the known Karp/Garey-Johnson reduction hierarchy, where scheduling problems are proven NP-complete via reductions from graph problems. The references.md file confirms "Knapsack -> Job Sequencing" as item #19 in Karp's 21 problems, showing scheduling reductions are well-established in this family.

I was unable to independently verify the exact theorem number and page number from freely available web sources (the full book text is not publicly accessible), but the proof structure, notation, and style are entirely consistent with Garey & Johnson Chapter 3 proofs. The mathematical argument (counting early tasks before the deadline) is sound: J vertex tasks + J(J-1)/2 edge tasks = J + J(J-1)/2 = J(J+1)/2 tasks fitting before the deadline, and the precedence constraints force the edge tasks to correspond to a complete subgraph.

Well-written

Strengths:

• The reduction algorithm is detailed and complete, including a verbatim book quotation plus a clear step-by-step summary
• The example is fully worked with a concrete graph (K4 minus one edge), showing the schedule, tardiness count, and solution extraction
• Symbols are defined (n, m, J) and used consistently
• The validation method is thorough with multiple test cases

Issues (warnings, not failures):

1. Source problem name: The issue uses "CLIQUE" / "Clique" but the codebase name is MaximumClique. The Source field should use the canonical name.

2. Incomplete overhead table: The table only lists num_tasks = num_vertices + num_edges. However, since MinimumTardinessSequencing does not exist yet, the actual size fields are unknown. When the model is created, additional overhead expressions will likely be needed for:

   • Number of precedence constraints: 2 * num_edges
   • The tardiness bound K (derived from source parameters)

3. Target problem not defined: Since the target model does not exist, the overhead table's num_tasks field name cannot be validated against actual getter methods. This will need to be reconciled when the model is implemented.

4. Page number: The issue cites "p.73" but Theorem 3.10 in G&J is typically in the range of pages 65-80 of Chapter 3. This could not be independently verified but is plausible.

Recommendations

• Create a [Model] issue for MinimumTardinessSequencing first, defining the problem schema (task set, deadlines, partial order, tardiness bound K), size fields, and complexity. The rule issue depends on this.
• Update the Source field to use MaximumClique (the canonical codebase name).
• Once the model is defined, revisit the overhead table to include all size fields from the target problem.

[isPANN]

Issue Quality Check — Rule

Check	Result	Details
Usefulness	✅ Pass	No existing path from MaximumClique to MinimumTardinessSequencing
Non-trivial	✅ Pass	Genuine gadget construction with tasks, partial order, deadline encoding, and counting argument
Correctness	❌ Fail	Decision-to-decision Karp reduction applied to optimization-to-optimization codebase models
Well-written	❌ Fail	Overhead metric num_tasks not in target's size_fields; source name mismatch

Overall: 2 passed, 2 failed, 0 warnings

---

Usefulness

pred path MaximumClique MinimumTardinessSequencing returns no path. This reduction would be the first connection from a graph problem to a scheduling problem in the reduction graph — genuinely novel. Motivation is substantive: explains how clique selection is encoded via deadline pressure.

Non-trivial

The reduction involves genuine structural transformation:

• Creates vertex tasks and edge tasks with different deadline regimes
• Constructs a partial order from graph incidence (endpoint vertices must precede their edge task)
• Uses a counting argument: J(J+1)/2 slots before the edge deadline must accommodate J vertex tasks + J(J−1)/2 edge tasks, forcing a complete subgraph
• Solution extraction identifies clique from early-scheduled tasks

Not a variable substitution, subtype coercion, or identity reduction.

Correctness

Reference verified: Garey & Johnson, Computers and Intractability, Theorem 3.10. The book garey1979 is in docs/paper/references.bib. The reduction from CLIQUE to MINIMUM TARDINESS SEQUENCING is confirmed as a well-known G&J Chapter 3 proof. Page 73 is plausible for Section 3.2.3. G&J Appendix entry SS2 confirms "Transformation from CLIQUE (see Section 3.2.3)."

Example verified: Brute-force enumeration of all 362,880 permutations found 5,760 valid schedules (respecting precedence). The minimum tardy count is exactly 2 = K, matching the issue's claim. There are 192 optimal schedules and 5,568 suboptimal schedules (all with 3 tardy tasks), confirming at least 2 suboptimal feasible solutions. Round-trip verified: in all optimal schedules, the early vertex tasks correspond to vertices {0,1,2}, a valid 3-clique.

Source/target definition mismatch (FAIL): The reduction is a Karp reduction between decision problems:

• Decision CLIQUE: "Does G have a clique of size ≥ J?"
• Decision MINIMUM TARDINESS SEQUENCING: "Is there a schedule with ≤ K tardy tasks?"

However, both problems in the codebase are optimization problems:

• MaximumClique implements OptimizationProblem (maximize clique weight, Direction::Maximize)
• MinimumTardinessSequencing implements OptimizationProblem (minimize tardy count, Direction::Minimize)

The reduction construction depends critically on the clique size parameter J (used to compute edge deadlines = J(J+1)/2 and tardiness bound K = |E| − J(J−1)/2). This parameter is not part of the MaximumClique optimization formulation — it's a decision threshold. The ReduceTo trait requires mapping one problem instance to another without external parameters, so the reduction as described cannot be implemented with the current trait system.

To fix, the issue should either:

1. Introduce a decision variant KClique as a SatisfactionProblem with parameter J, OR
2. Reformulate the reduction to work as optimization-to-optimization (but this doesn't follow naturally from the G&J proof)

Well-written

Strengths:

• Reduction algorithm is exceptionally detailed with verbatim G&J quote plus clear 5-step summary
• Example is fully worked: all 9 tasks listed by name, all precedence constraints enumerated, complete schedule with position-by-position verification
• Validation method is thorough with multiple test cases and specific expected outcomes
• Symbols (n, m, J, K) defined before use and consistent across sections

Failures:

1. Source name mismatch: Issue uses "CLIQUE" but codebase name is MaximumClique. The Source field should use the canonical name.

2. Overhead metric not in target's size_fields: The target MinimumTardinessSequencing has size_fields: [] (empty). The issue's overhead table lists num_tasks, which exists as a getter method but is not registered as a size field. Overhead expressions in #[reduction(overhead = {...})] must reference target size_fields. The table is also incomplete — it should include num_precedences (= 2 * num_edges).

3. Overhead expression variable num_edges: While num_edges is a valid size_field of MaximumClique, the overhead formula also implicitly depends on J (the clique parameter) for the tardiness bound K and edge deadlines, which cannot be expressed as a function of source size_fields alone.

Recommendations

• Resolve the decision-vs-optimization mismatch before implementation. The cleanest path is likely a new KClique satisfaction model with the J parameter, then reduce KClique → MinimumTardinessSequencing (reformulated as satisfaction with bound K).
• Register num_tasks and num_precedences as size_fields in the target model.
• Update the Source field to use MaximumClique (or the new KClique) canonical name.
• Expand the overhead table to cover all target size fields once they are registered.