[Model] MinimumIntersectionGraphBasis

[isPANN]

Motivation

INTERSECTION GRAPH BASIS (P70) from Garey & Johnson, A1.5 GT59. A classical NP-hard problem useful for reductions. The intersection number of a graph is a fundamental invariant in intersection graph theory, equivalent to the edge clique cover number. Applications include database keyword conflict resolution (Kou et al., 1978) and intersection graph recognition.

Associated rules:

• [Rule] COVERING BY CLIQUES to MinimumIntersectionGraphBasis #848: MinimumCoveringByCliques → MinimumIntersectionGraphBasis (equivalence via edge clique cover)

Definition

Name: MinimumIntersectionGraphBasis
Reference: Garey & Johnson, Computers and Intractability, A1.5 GT59

Mathematical definition:

INSTANCE: Graph G = (V,E).
OBJECTIVE: Find the minimum cardinality of a set S and an assignment of subsets S[v] ⊆ S for each v ∈ V such that {u,v} ∈ E if and only if S[u] ∩ S[v] ≠ ∅.

The objective value is Min(|S|), the minimum universe size for an intersection representation of G.

Variables

• Count: |V| * K_max (one binary variable per vertex-element pair, where K_max ≤ |E| is an upper bound on the universe size)
• Per-variable domain: {0, 1}
• Meaning: Variable (v, s) = 1 if element s ∈ S is included in the subset S[v] assigned to vertex v. The assignment is valid if: (1) for every edge {u,v} ∈ E, S[u] ∩ S[v] ≠ ∅; and (2) for every non-edge {u,v} ∉ E, S[u] ∩ S[v] = ∅. The objective minimizes |S|, the number of universe elements actually used.

Schema (data type)

Type name: MinimumIntersectionGraphBasis
Variants: (SimpleGraph, One) — unweighted, simple graph input

Field	Type	Description
graph	SimpleGraph	The input graph G = (V, E)

Notes:

• This is an optimization problem: Value = Min<usize>.
• Key getter methods: num_vertices() (= |V|), num_edges() (= |E|).
• The intersection number equals the edge clique cover number.

Complexity

• Decision complexity: NP-hard (Kou, Stockmeyer, and Wong, 1978; Orlin, 1976). Transformation from COVERING BY CLIQUES. NP-hard even for planar graphs and graphs of maximum degree 6. Polynomial for maximum degree ≤ 5.
• Best known exact algorithm: FPT parameterized by solution size k with kernel of at most 2^k vertices, yielding 2^(2^O(k)) · n^O(1) time.
• Concrete complexity expression: "num_edges^num_edges" (for declare_variants!; brute-force bound, since intersection number ≤ |E|)
• References:
  • L.T. Kou, L.J. Stockmeyer, C.K. Wong (1978). "Covering Edges by Cliques with Regard to Keyword Conflicts among in a File." Comm. ACM 21(2), pp. 135-139.

Extra Remark

Full book text:

INSTANCE: Graph G = (V,E), positive integer K ≤ |E|.
QUESTION: Is G the intersection graph for a family of sets whose union has cardinality K or less, i.e., is there a K-element set S and for each v ∈ V a subset S[v] ⊆ S such that {u,v} ∈ E if and only if S[u] and S[v] are not disjoint?

Reference: [Kou, Stockmeyer, and Wong, 1978]. Transformation from COVERING BY CLIQUES.

How to solve

• It can be solved by (existing) bruteforce. (Enumerate all possible subset assignments for increasing universe sizes; return the smallest universe that gives a valid intersection representation.)
• It can be solved by reducing to integer programming. (Binary variables x_{v,s} for each vertex-element pair; constraints ensuring edges intersect and non-edges don't; binary variables y_s indicating element usage; minimize Σ y_s. Companion rule issue to be filed separately.)
• Other: (TBD)

Example Instance

Input: Path graph P_4 on 4 vertices:
V = {0, 1, 2, 3}, E = {(0,1), (1,2), (2,3)}

Optimal intersection representation (|S| = 3):
Universe S = {a, b, c}:

• S[0] = {a}
• S[1] = {a, b}
• S[2] = {b, c}
• S[3] = {c}

Edge verification: S[0]∩S[1]={a}≠∅ ✓, S[1]∩S[2]={b}≠∅ ✓, S[2]∩S[3]={c}≠∅ ✓
Non-edge verification: S[0]∩S[2]=∅ ✓, S[0]∩S[3]=∅ ✓, S[1]∩S[3]=∅ ✓

Optimal value: Min(3) — the intersection number of P_4 equals its edge clique cover number (3 edges, each an edge-clique). No 2-element universe suffices because the 3 edges form 3 maximal cliques that pairwise share vertices.

Python validation script

# P4: 4 vertices, 3 edges
edges = [(0,1), (1,2), (2,3)]
non_edges = [(0,2), (0,3), (1,3)]

# Intersection representation with |S|=3
S = {0: {0}, 1: {0, 1}, 2: {1, 2}, 3: {2}}  # using integers for universe

# Check edges intersect
for u, v in edges:
    assert S[u] & S[v], f"Edge ({u},{v}) not covered"

# Check non-edges don't intersect
for u, v in non_edges:
    assert not (S[u] & S[v]), f"Non-edge ({u},{v}) falsely intersects"

print("Intersection representation verified: Min(3)")

[isPANN]

Issue Quality Check — Model

Check	Result	Details
Usefulness	❌ Fail	ILP solvability claimed but no companion [Rule] IntersectionGraphBasis to ILP issue linked
Non-trivial	✅ Pass	Distinct feasibility constraints from all existing problems
Correctness	⚠️ Warn	Complexity section uses asymptotic big-O with hidden constants instead of a concrete expression
Well-written	❌ Fail	Missing Expected Outcome section; complexity expression not concrete; no ILP companion issue crossref

Overall: 1 passed, 1 warning, 2 failed

---

Usefulness

Problem novelty: IntersectionGraphBasis does not exist in the codebase — confirmed via pred show IntersectionGraphBasis (not found). ✅

Planned reductions: The issue mentions a planned reduction from CoveringByCliques (issue #836 exists as [Model] CoveringByCliques). This connects the problem to the reduction graph. ✅

ILP solvability without companion issue: The "How to solve" section checks "It can be solved by reducing to integer programming," but no companion [Rule] IntersectionGraphBasis to ILP issue is linked anywhere in the issue body. Per the template requirements, if direct ILP solving is claimed, a companion issue must be linked. ❌ Fail.

Motivation: The motivation references Garey & Johnson A1.5 GT59 and describes the problem as "useful for reductions." This is adequate but could be more specific about concrete use cases.

Non-trivial

The intersection number problem (equivalently, edge clique cover number) has genuinely distinct feasibility constraints from all existing problems in the codebase. The closest related problems are:

• BicliqueCover — covers edges by bicliques, not cliques
• KClique — finds a single clique of size k, not a set cover of edges by cliques
• MinimumVertexCover / MinimumSetCovering — cover vertices/elements, not edges by cliques

The problem involves assigning subsets to vertices such that adjacency is characterized by non-empty intersection — a fundamentally different structure. ✅ Pass.

Correctness

Reference verification:

• Kou, Stockmeyer, and Wong (1978): Verified. "Covering edges by cliques with regard to keyword conflicts and intersection graphs," Communications of the ACM, Vol. 21, No. 2, pp. 135–139. The paper establishes NP-completeness of the edge clique cover problem (equivalent to the intersection number problem). ✅
• NP-hardness for planar graphs and max degree 6: Confirmed via Wikipedia on intersection number (graph theory). The problem is polynomial-time solvable for graphs with maximum degree ≤ 5 and NP-hard for maximum degree ≥ 6. ✅
• FPT with 2^K vertex kernel: Confirmed. The edge clique cover problem is FPT parameterized by K with a kernel of at most 2^K vertices (via twin reduction). ✅

Complexity expression: The issue states 2^(2^O(K)) * n^O(1) which uses asymptotic notation with hidden constants. The declare_variants! macro requires a concrete complexity expression in terms of problem getter methods (e.g., num_vertices, universe_size). The issue does not provide one. ⚠️ Warn — the FPT claim is correct but needs a concrete expression for implementation.

Note on the "max degree 5" claim: The issue attributes this to Kou, Stockmeyer, and Wong (1978), but the polynomial-time result for max degree ≤ 5 may come from later work. The original 1978 paper focuses on NP-completeness. This is not a failure since the result itself is correct, but the attribution should be verified.

Well-written

4a — Information Completeness:

Section	Status
Motivation	✅ Present
Name	✅ IntersectionGraphBasis
Reference	✅ Garey & Johnson A1.5 GT59
Definition	✅ Clear INSTANCE/QUESTION format
Variables	✅ Present with count, domain, meaning
Schema	✅ Fields and types specified
Complexity	⚠️ Present but lacks concrete expression (e.g., 2^(2 * 2^universe_size) * num_vertices^2)
How to solve	❌ ILP claimed but no companion issue linked
Example Instance	✅ Present
Expected Outcome	❌ Missing — the example shows a solution but does not have a dedicated "Expected Outcome" section stating the answer (YES) with brief justification

4b — Definition Completeness: The definition is precise and implementable — it clearly states the input (graph G, integer K), the feasibility constraints (intersection iff edge, disjoint iff non-edge), and the decision question. ✅

4c — Symbol and Notation Consistency: Symbols are consistent between sections (G, V, E, K, S, S[v]). ✅

4d — Example Quality:

• Non-trivial: P4 with K=3 exercises the core structure — 4 vertices, 3 edges, 3 non-edges, all constraints exercised. ✅
• Correctness verified: Python verification confirms the solution is valid and K=3 is optimal (K=2 yields 0 valid assignments). ✅
• Multiple feasible configs: There are 6 valid assignments with K=3, providing adequate coverage for testing. ✅
• Round-trip testable: For a decision/feasibility problem, K=3 (YES) vs K=2 (NO) provides meaningful test coverage. ✅

4e — Representation Feasibility: SimpleGraph and usize for universe_size are adequate for the stated problem domain. ✅

Recommendations

• Add an "Expected Outcome" section to the example: "Answer: YES. The intersection number of P4 is 3, achieved by the assignment above."
• File a companion [Rule] IntersectionGraphBasis to ILP issue and link it in the "How to solve" section, or remove the ILP checkbox.
• Provide a concrete complexity expression for declare_variants!, e.g., "2^(2^universe_size) * num_vertices^2" (or a tighter bound based on the FPT kernel).
• The motivation could mention specific applications: intersection graphs arise in database keyword conflict resolution (per the Kou et al. paper) and in computational biology (interval graph recognition).

[isPANN]

Renamed from IntersectionGraphBasis to MinimumIntersectionGraphBasis. Converted from decision framing (with bound K) to optimization framing: the objective now minimizes the universe size for an intersection representation. Removed the universe_size field from the schema. Removed Useless and PoorWritten labels.

[isPANN]

Fix-issue changelog

• Associated rules: Linked [Rule] COVERING BY CLIQUES to MinimumIntersectionGraphBasis #848 (MinimumCoveringByCliques → MinimumIntersectionGraphBasis).
• Complexity: Added concrete expression "num_edges^num_edges".
• Schema notes: Added Value = Min<usize> and getter methods.
• ILP: Added companion rule note.
• Example: Added optimality justification and Python validation script.

Applied by /fix-issue.