[Rule] 3-SATISFIABILITY to KERNEL

[isPANN]

Source: 3-SATISFIABILITY (3SAT)
Target: KERNEL

Motivation: Establishes NP-completeness of the KERNEL problem for directed graphs via polynomial-time reduction from 3SAT. The reduction by Chvátal (1973) shows that finding a kernel (an independent and absorbing vertex set in a digraph) is computationally hard. Kernels are fundamental in game theory (winning positions), logic programming (stable models), and argumentation frameworks (stable extensions).
Reference: Garey & Johnson, Computers and Intractability, A1.1 GT57; Chvátal 1973

GJ Source Entry

KERNEL
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.

Reduction Algorithm

Summary:
Given a KSatisfiability instance with n variables U = {u_1, ..., u_n} and m clauses C = {c_1, ..., c_m}, construct a Kernel instance (directed graph G = (V,A)) as follows:

1. Variable gadgets: For each variable u_i, create two vertices: v_i (representing u_i = True) and v̄_i (representing u_i = False). Add arcs (v_i, v̄_i) and (v̄_i, v_i) forming a directed 2-cycle. In any kernel, exactly one of {v_i, v̄_i} is selected (since they are mutually reachable, exactly one must be in the kernel for independence + absorption).

2. Clause gadgets: For each clause c_j = (l_1 ∨ l_2 ∨ l_3), create a small directed subgraph. One common construction uses a chain of auxiliary vertices that enforce the OR of the three literals:

   • Create vertices w_j^1, w_j^2, w_j^3 with arcs forming a directed path or cycle structure.
   • The gadget is designed so that the clause vertex can be absorbed by the kernel only if at least one literal vertex is in the kernel.

3. Connection arcs: For each literal occurrence l_k in clause c_j, add an arc from the clause gadget vertex to the corresponding literal vertex (v_i or v̄_i). This ensures the clause vertex is absorbed if the literal is in the kernel (i.e., the literal is true).

4. Solution extraction: From a kernel V', read off the truth assignment: u_i = True if v_i ∈ V', u_i = False if v̄_i ∈ V'. The clause gadget structure guarantees each clause has at least one true literal.

The key insight is that the 2-cycles force a consistent boolean assignment, and the clause gadgets enforce satisfiability via the absorption property.

Size Overhead

Symbols:

• n = num_vars of source 3SAT instance
• m = num_clauses of source 3SAT instance

Target metric (code name)	Polynomial (using symbols above)
num_vertices	2 * num_vars + 3 * num_clauses
num_arcs	2 * num_vars + 6 * num_clauses

Derivation:

• Variable gadgets: 2 vertices per variable (positive and negative literal), 2 arcs per variable (the 2-cycle). Total: 2n vertices, 2n arcs.
• Clause gadgets: ~3 auxiliary vertices per clause (for the OR chain), ~3 internal arcs plus 3 connection arcs per clause. Total: 3m vertices, 6m arcs.
• Grand total: 2n + 3m vertices, 2n + 6m arcs.
• Note: exact counts depend on the specific clause gadget variant from Chvátal's construction.

Validation Method

• Closed-loop test: reduce KSatisfiability instance to Kernel (directed graph), solve target with BruteForce, extract truth assignment from which literal vertices are in the kernel, verify all clauses satisfied
• Test with both satisfiable and unsatisfiable 3SAT instances
• Verify kernel properties: independence (no arc between kernel vertices) and absorption (every non-kernel vertex has arc to kernel)
• Note: Kernel uses a directed graph, requiring either a DiGraph type or arc representation

Example

Source instance (KSatisfiability):
2 variables: u_1, u_2 (n = 2)
1 clause (m = 1):

• c_1 = (u_1 ∨ ¬u_2 ∨ u_2)

Satisfiable: any assignment works (c_1 is a tautology since it contains u_2 and ¬u_2).

Constructed target instance (Kernel):
Vertices: {v_1, v̄_1, v_2, v̄_2, w_1^1, w_1^2, w_1^3} (22 + 31 = 7 vertices)

Arcs:

• Variable 2-cycles: (v_1, v̄_1), (v̄_1, v_1), (v_2, v̄_2), (v̄_2, v_2) — 4 arcs
• Clause gadget internal arcs: arcs among {w_1^1, w_1^2, w_1^3} — ~3 arcs
• Connection arcs: w_1^1 → v_1, w_1^2 → v̄_2, w_1^3 → v_2 — 3 arcs

Total: ~10 arcs

Solution: Kernel V' = {v_1, v_2, w_1^2}:

• Independence: no arcs within {v_1, v_2, w_1^2} (check the gadget design).
• Absorption: v̄_1 absorbed by v_1 via (v̄_1, v_1), v̄_2 absorbed by v_2 via (v̄_2, v_2), remaining clause vertices absorbed by w_1^2 or literal vertices.
• Truth assignment: u_1 = True, u_2 = True. Satisfies c_1.

References

• Chvátal, V. (1973). "On the computational complexity of finding a kernel." Report CRM-300, Centre de Recherches Mathématiques, Université de Montréal.
• Garey, M. R., & Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness, A1.1 GT57.
• Richardson, M. (1953). "Solutions of irreflexive relations." Annals of Mathematics, 58(3), 573-590.

[GiggleLiu]

Implemented in PR #999.