[Model] Kernel

[isPANN]

Motivation

KERNEL (GT57) from Garey & Johnson, A1.1. Given a directed graph, find a kernel: an independent and absorbing set. A kernel is a set V' of vertices such that no two vertices in V' are connected by an arc, and every vertex outside V' has an arc to some vertex in V'. NP-complete (Chvátal 1973) via reduction from 3-Satisfiability. Kernels generalize stable matchings and appear in game theory (winning positions in combinatorial games), logic (stable extensions of argumentation frameworks), and cooperative game theory.

Associated rules:

• [Rule] 3-SATISFIABILITY to KERNEL #882: 3-SATISFIABILITY → Kernel (classical NP-completeness proof)

Definition

Name: Kernel
Reference: Garey & Johnson, Computers and Intractability, A1.1 GT57; Chvátal 1973

Mathematical definition:

INSTANCE: Directed graph G = (V,A).
QUESTION: Does G have a kernel, i.e., is there a set V' ⊆ V such that (1) no two vertices in V' are joined by an arc of A, and (2) for every vertex u ∈ V − V' there is a vertex v ∈ V' such that (u,v) ∈ A?

Condition (1) says V' is independent in the directed sense; condition (2) says V' is absorbing (every non-member has an out-neighbor in V').

Variables

• Count: |V| (one per vertex)
• Per-variable domain: {0, 1} (binary: in the kernel or not)
• Meaning: Whether each vertex is included in the kernel. The selected set must be independent (no arcs between selected vertices) and absorbing (every non-selected vertex has an arc to some selected vertex).

Schema (data type)

Type name: Kernel
Variants: none

Field	Type	Description
graph	DirectedGraph	The directed graph G = (V,A)

Notes:

• This is a feasibility (decision) problem: Value = Or.
• Key getter methods: num_vertices() (= |V|), num_arcs() (= |A|), delegated from DirectedGraph.
• Uses the existing DirectedGraph type in src/topology/directed_graph.rs.
• Self-loops should be excluded.

Complexity

• Decision complexity: NP-complete (Chvátal, 1973; transformation from 3-Satisfiability). Not every digraph has a kernel — deciding existence is the NP-complete part.
• Best known exact algorithm: O*(2^n) by brute-force subset enumeration. No sub-2^n exact algorithm is known for general digraphs.
• Concrete complexity expression: "2^num_vertices" (for declare_variants!)
• Tractable cases: Every directed acyclic graph (DAG) has a unique kernel, computable in polynomial time. Every digraph with no odd directed cycle has a kernel (Richardson's theorem).
• References:
  • V. Chvátal (1973). "On the computational complexity of finding a kernel." Report CRM-300, Centre de Recherches Mathématiques, Université de Montréal.

Extra Remark

Full book text:

INSTANCE: Directed graph G = (V,A).
QUESTION: Does G contain a kernel, i.e., is there a subset V' ⊆ V such that no two vertices in V' are joined by an arc of A and such that, for every vertex u ∈ V − V', there is a vertex v ∈ V' such that (u,v) ∈ A?

Reference: [Chvátal, 1973]. Transformation from 3-SATISFIABILITY.
Comment: Every directed acyclic graph has a kernel. Solvable in polynomial time for DAGs.

How to solve

• It can be solved by (existing) bruteforce. (Enumerate all 2^|V| subsets; check independence and absorption.)
• It can be solved by reducing to integer programming.
• Other:

Example Instance

Positive instance:
V = {0, 1, 2, 3, 4}, A = {(0,1), (0,2), (1,3), (2,3), (3,4), (4,0), (4,1)}

Kernel: V' = {0, 3}

• Independence: no arc (0,3) or (3,0) in A ✓
• Absorption:
  • vertex 1 ∉ V': arc (1,3) ∈ A, 3 ∈ V' ✓
  • vertex 2 ∉ V': arc (2,3) ∈ A, 3 ∈ V' ✓
  • vertex 4 ∉ V': arc (4,0) ∈ A, 0 ∈ V' ✓

Answer: YES — {0, 3} is the unique kernel (1 out of 32 subsets).

Near-miss candidates:

• {0, 4}: arc (4,0) ∈ A violates independence ✗
• {1, 3}: arc (1,3) ∈ A violates independence ✗
• {0}: vertex 1 has no arc to {0} (only (1,3)), violates absorption ✗

Negative instance:
Remove arc (4,0) from the positive example: A' = {(0,1), (0,2), (1,3), (2,3), (3,4), (4,1)}.
Now vertex 4 has only arc (4,1). For absorption, 4 must have an arc to some kernel member. But vertex 1 cannot be in the kernel together with 3 (arc (1,3) violates independence), and without vertex 0 in the kernel, vertex 4 has no arc to any valid kernel member. Exhaustive search confirms no kernel exists. Answer: NO.

Python validation script

from itertools import combinations

def find_kernels(n, arcs):
    arc_set = set(arcs)
    kernels = []
    for size in range(n + 1):
        for subset in combinations(range(n), size):
            s = set(subset)
            indep = all((u,v) not in arc_set for u in s for v in s if u != v)
            if not indep: continue
            absorb = all(
                any((u,v) in arc_set for v in s)
                for u in range(n) if u not in s
            )
            if absorb:
                kernels.append(s)
    return kernels

# Positive
arcs_pos = [(0,1),(0,2),(1,3),(2,3),(3,4),(4,0),(4,1)]
k_pos = find_kernels(5, arcs_pos)
assert k_pos == [{0, 3}]
print(f"Positive: {len(k_pos)} kernel(s): {k_pos}")

# Negative (remove (4,0))
arcs_neg = [(0,1),(0,2),(1,3),(2,3),(3,4),(4,1)]
k_neg = find_kernels(5, arcs_neg)
assert len(k_neg) == 0
print(f"Negative: {len(k_neg)} kernels (correct)")

[isPANN]

Issue Quality Check — Model

Check	Result	Details
Usefulness	⚠️ Warn	Novel problem, but no planned reduction rules connecting it to the existing graph
Non-trivial	✅ Pass	Distinct feasibility constraints (independent + absorbing) from all existing problems
Correctness	❌ Fail	Richardson's theorem misquoted; complexity bound is naive brute force
Well-written	❌ Fail	Missing Expected Outcome; chaotic example with false starts; incorrect schema note about DiGraph

Overall: 1 passed, 1 warning, 2 failed

---

Usefulness

The Kernel problem does not yet exist in the codebase (pred show Kernel returns not found). It models a genuinely useful concept from combinatorial game theory and argumentation frameworks.

However, the issue does not mention any planned reduction rules to/from existing problems. A problem without any reduction connectivity is an orphan node in the reduction graph. The "How to solve" section only checks brute force — no ILP reduction is planned (though the issue body does sketch an ILP formulation in the notes). There is no "Reduction Rule Crossref" section linking to companion [Rule] issues.

Verdict: Warn — add at least one concrete planned reduction (e.g., Kernel → ILP, or 3-SAT → Kernel via Chvátal's original construction).

Non-trivial

Kernel requires a set V' that is simultaneously independent (no arc between members) and absorbing (every non-member has an out-arc to some member). This is a distinct feasibility condition from:

• MaximumIndependentSet (independent but not absorbing, undirected)
• MinimumDominatingSet (dominating but not independent in the same directed sense)
• MinimumFeedbackVertexSet (hitting all cycles, different structure)

Verdict: Pass.

Correctness

3a — Definition: The formal definition is correct and matches Garey & Johnson GT57.

3b — Complexity: The issue claims 2^num_vertices brute force, which is the naive bound. This is technically correct but uninformative — it is just exhaustive enumeration. No attempt is made to cite a faster exact algorithm. For comparison, problems like MIS have well-studied exact algorithms with bases below 2 (e.g., 1.1996^n). The kernel problem may admit similar improvements.

3c — Richardson's theorem is misquoted. The issue states:

"Every directed graph where every vertex has odd out-degree has a kernel (Richardson's theorem for finite tournaments)."

This is incorrect. Richardson's theorem states that every digraph with no odd directed cycle has a kernel. The "odd out-degree" claim is a fabrication and does not appear in the literature. The parenthetical "(Richardson's theorem for finite tournaments)" is also misleading — Richardson's theorem is not specific to tournaments.

3d — Chvátal 1973 reference: The Chvátal 1973 technical report (Report CRM-300, Université de Montréal) does exist and does prove NP-completeness of kernel existence via reduction from SAT. This reference is correct.

Verdict: Fail — Richardson's theorem is misquoted with a fabricated condition ("odd out-degree").

Well-written

4a — Information Completeness:

Section	Status
Motivation	✅ Present and substantive
Name	✅ Kernel
Reference	✅ Garey & Johnson GT57, Chvátal 1973
Definition	✅ Well-formed
Variables	✅ Correct binary encoding
Schema	⚠️ Incorrectly claims "The codebase may need a DiGraph type" — DirectedGraph already exists in src/topology/directed_graph.rs
Complexity	⚠️ Only naive brute force cited
How to solve	⚠️ Only brute force checked; ILP formulation sketched in notes but not formally planned
Example Instance	❌ See below
Expected Outcome	❌ Missing — no explicit "Answer: YES/NO" with justification

4b — Definition Completeness: The definition is precise and implementable. Good.

4c — Notation: Consistent use of G=(V,A), V', etc.

4d — Example Quality:

The example section has serious issues:

1. Chaotic presentation: The first example (4 vertices) includes multiple false-start candidate kernels ({v0,v3}, {v2,v3}, {v0}, {v2}) that all fail, with inline reasoning corrections ("wait, we need..."). This reads like scratch work, not a clear worked example. The final answer is "this graph has no kernel" — a NO instance is not useful as the primary example for a feasibility problem.

2. Trivially small YES instance: The second example (3 vertices, 2 arcs) has a trivially obvious singleton kernel {v1}. With only 2^3 = 8 configurations and an obvious answer, this cannot meaningfully validate an implementation.

3. No round-trip testing value: Neither example has enough structure to catch implementation bugs. A good example should have multiple candidate kernels that are close to valid but fail on one condition, so that correctness is meaningfully tested.

Recommendation: Replace with a single well-structured YES instance of 5-6 vertices where the kernel is not immediately obvious, with a clear worked verification. Include at least one near-miss candidate that fails either independence or absorption.

Recommendations

• Add a "Reduction Rule Crossref" section with at least one planned reduction (Chvátal's 3-SAT → Kernel construction would be natural, or a direct Kernel → ILP rule)
• Fix the Richardson's theorem statement to: "Every digraph with no odd directed cycle has a kernel"
• Update the schema note to reference the existing DirectedGraph type in src/topology/directed_graph.rs
• Replace the example with a single non-trivial YES instance (5+ vertices) with a clear expected outcome
• Consider citing faster exact algorithms if any exist in the literature

[isPANN]

Fix-issue changelog

• Associated rules: Linked rule [Rule] 3-SATISFIABILITY to KERNEL #882 (3-SATISFIABILITY → Kernel).
• Richardson's theorem: Fixed misquoted statement — "Every digraph where every vertex has odd out-degree" (fabricated) → "Every digraph with no odd directed cycle" (correct).
• Schema: Updated from raw num_vertices/arcs fields to graph: DirectedGraph, matching existing directed graph models.
• Example: Replaced chaotic example (multiple false-start candidates on a 4-vertex graph with no kernel) with clean 5-vertex instance with unique kernel {0,3}. Includes near-miss candidates showing both independence and absorption failures. Added negative example (remove one arc, 0 kernels).
• Complexity: Added concrete expression "2^num_vertices" for declare_variants!.
• Added Python validation script verifying both positive (1 kernel) and negative (0 kernels).

Applied by /fix-issue.