[Model] MinimumMatrixDomination

[isPANN]

Motivation

MATRIX DOMINATION (P324) from Garey & Johnson, A12 MS12. Find the minimum number of non-zero entries in a binary matrix needed to dominate all other non-zero entries. NP-complete (Yannakakis and Gavril, 1980; G&J cites 1978 preprint). Related to edge dominating set in bipartite graphs: viewing M as a biadjacency matrix, dominating entries correspond to dominating edges.

Associated rules:

• [Rule] MINIMUM MAXIMAL MATCHING to MinimumMatrixDomination #847: MinimumMaximalMatching → MinimumMatrixDomination (NP-completeness proof)

Definition

Name: MinimumMatrixDomination
Reference: Garey & Johnson, Computers and Intractability, A12 MS12

Mathematical definition:

INSTANCE: An n×n matrix M with entries from {0,1}.
OBJECTIVE: Find a subset C of non-zero entries of M with minimum |C| such that for every non-zero entry (i,j) of M, either (i,j) ∈ C or there exists an entry (i',j') ∈ C sharing a row (i = i') or column (j = j') with (i,j).

Variables

• Count: s (one per non-zero entry; only 1-entries are candidates)
• Per-variable domain: {0, 1}
• Meaning: Whether each non-zero entry (i,j) is selected into the dominating set C. The objective minimizes |C| while ensuring every 1-entry not in C shares a row or column with some entry in C.

Schema (data type)

Type name: MinimumMatrixDomination
Variants: none

Field	Type	Description
matrix	Vec<Vec<bool>>	The n×n binary matrix M

Notes:

• This is an optimization problem: Value = Min<usize>.
• Key getter methods: num_rows() (= n), num_cols() (= n), num_ones() (= number of 1-entries).

Complexity

• Decision complexity: NP-complete (Yannakakis and Gavril, 1980; transformation from MINIMUM MAXIMAL MATCHING). NP-complete even when M is upper triangular.
• Best known exact algorithm: O*(2^s) by brute-force enumeration of subsets of 1-entries, where s = number of non-zero entries.
• Concrete complexity expression: "2^num_ones" (for declare_variants!)
• References:
  • M. Yannakakis, F. Gavril (1980). "Edge Dominating Sets in Graphs." SIAM J. Appl. Math. 38(3), pp. 364-372.

Extra Remark

Full book text:

INSTANCE: An n×n matrix M with entries from {0,1}, and a positive integer K.
QUESTION: Is there a set of K or fewer non-zero entries in M that dominate all others, i.e., a subset C ⊆ {1,2,...,n}×{1,2,...,n} with |C| ≤ K such that M_ij = 1 for all (i,j) ∈ C and such that, whenever M_ij = 1, there exists an (i',j') ∈ C for which either i = i' or j = j'?
Reference: [Yannakakis and Gavril, 1978]. Transformation from MINIMUM MAXIMAL MATCHING.
Comment: Remains NP-complete even if M is upper triangular.

How to solve

• It can be solved by (existing) bruteforce. (Enumerate all subsets of 1-entries; return the smallest dominating set.)
• It can be solved by reducing to integer programming. (Binary variables x_{ij} for each 1-entry; for each 1-entry (i,j): x_{ij} + Σ_{(i,j') in C} x_{i,j'} + Σ_{(i',j) in C} x_{i',j} ≥ 1; minimize Σ x_{ij}. Companion rule issue to be filed separately.)
• Other:

Example Instance

Input: 6×6 binary matrix M (adjacency matrix of path graph P_6):

     0  1  2  3  4  5
0  [ 0  1  0  0  0  0 ]
1  [ 1  0  1  0  0  0 ]
2  [ 0  1  0  1  0  0 ]
3  [ 0  0  1  0  1  0 ]
4  [ 0  0  0  1  0  1 ]
5  [ 0  0  0  0  1  0 ]

Non-zero entries (10 total): (0,1), (1,0), (1,2), (2,1), (2,3), (3,2), (3,4), (4,3), (4,5), (5,4).

Optimal dominating set: C = {(0,1), (1,0), (3,4), (4,3)}, |C| = 4.

• (1,2): shares row 1 with (1,0) ∈ C ✓
• (2,1): shares column 1 with (0,1) ∈ C ✓
• (2,3): shares row 2 with... no. Shares column 3 with (4,3) ∈ C ✓
• (3,2): shares row 3 with (3,4) ∈ C ✓
• (4,5): shares row 4 with (4,3) ∈ C ✓
• (5,4): shares column 4 with (3,4) ∈ C ✓

Optimal value: Min(4). No 3-entry dominating set exists (verified exhaustively).

Python validation script

from itertools import combinations

ones = [(0,1),(1,0),(1,2),(2,1),(2,3),(3,2),(3,4),(4,3),(4,5),(5,4)]

def dominates(C, ones):
    C_set = set(C)
    for (i,j) in ones:
        if (i,j) in C_set: continue
        if any(ci == i or cj == j for ci,cj in C_set): continue
        return False
    return True

# Find minimum
for k in range(1, 11):
    found = [c for c in combinations(ones, k) if dominates(c, ones)]
    if found:
        assert k == 4
        print(f"Minimum dominating set size: {k} ({len(found)} solutions)")
        break

# Verify specific solution
C = [(0,1),(1,0),(3,4),(4,3)]
assert dominates(C, ones)
print("Specific solution verified")

[isPANN]

Issue Quality Check — Model

Check	Result	Details
Usefulness	⚠️ Warn	Problem is novel but no planned reductions are mentioned
Non-trivial	✅ Pass	Distinct feasibility constraints from all existing problems
Correctness	⚠️ Warn	Minor reference date discrepancy; parenthetical K=2 claim in example is wrong
Well-written	❌ Fail	Missing expected outcome section; ILP claimed without companion issue; example has an incorrect claim

Overall: 1 passed, 2 warnings, 1 failed

---

Usefulness

Problem existence: MatrixDomination does not exist in the codebase — novel problem. ✅

Planned reductions: The issue body does not mention any concrete reduction rule connecting MatrixDomination to/from an existing problem in the reduction graph. The Motivation section says only "A classical NP-complete problem useful for reductions" without naming a specific source or target. For the problem to have value in the reduction graph, at least one planned reduction (e.g., from MinimumMaximalMatching, or to ILP) should be stated explicitly. ⚠️

How to solve: Brute-force and ILP are both checked, which is good.

Non-trivial

MatrixDomination asks whether K or fewer non-zero entries of a binary matrix can "dominate" all other non-zero entries via shared rows or columns. This is a genuinely distinct problem — while it is closely related to Edge Dominating Set (viewing the matrix as a biadjacency matrix), it operates on a matrix representation rather than a graph, and no existing problem in the codebase captures this formulation. ✅

Correctness

Reference verification:

• The issue cites "Yannakakis and Gavril, 1978" for NP-completeness via reduction from Minimum Maximal Matching. The actual published paper is: M. Yannakakis and F. Gavril, "Edge Dominating Sets in Graphs," SIAM Journal on Applied Mathematics, Vol. 38, No. 3, pp. 364–372, 1980. The 1978 date likely refers to the technical report version that Garey & Johnson cited, so this is acceptable when following G&J's citation style, but a note would improve clarity. ⚠️

• The G&J numbering is given as "A12 MS12." The standard Garey & Johnson notation for this problem is MS12 (Miscellaneous section). The "A12" prefix is non-standard and unclear — it may be a numbering artifact from whatever tool generated this issue. Minor. ⚠️

Complexity claim: The issue claims O*(2^s) brute-force where s is the number of non-zero entries. This is correct as a naive bound (enumerate all subsets of 1-entries of size at most K). However, no dedicated faster exact algorithm is cited. This is honest but means the complexity string is just brute-force, not a best-known specialized algorithm. Acceptable for now.

Example correctness (K=4 solution): The main worked example with K=4 and C = {(1,2), (2,1), (3,4), (4,3)} is correct — I verified all 6 non-selected 1-entries are dominated via shared row or column. ✅

Example correctness (K=2 parenthetical claim): The issue ends with: "In fact K = 2 suffices with C = {(1,2), (3,4)} since this corresponds to the minimum edge dominating set of the path." This is wrong. With C = {(1,2), (3,4)}, entry (0,1) at row 0, column 1 is not dominated: no member of C is in row 0, and no member of C is in column 1 ((1,2) is at column 2, (3,4) is at column 4). The analogy to edge dominating set is also imprecise — matrix domination on an adjacency matrix is not identical to edge domination on the underlying graph because the adjacency matrix has two directed entries per undirected edge, and domination in matrix terms requires shared row OR column, not shared endpoint. ❌

Well-written

4a — Information Completeness:

Section	Status
Motivation	⚠️ Present but vague — no specific use case or graph connectivity plan
Name	✅ MatrixDomination — valid name for a feasibility/decision problem
Reference	✅ Garey & Johnson + Yannakakis/Gavril cited
Definition	✅ Formal INSTANCE/QUESTION format from G&J
Variables	✅ Count, domain, meaning all specified
Schema	✅ Field table with types
Complexity	⚠️ Only brute-force bound given; no concrete complexity expression in the required format
How to solve	❌ ILP is checked but no companion [Rule] MatrixDomination to ILP issue is linked. Per template requirements, direct ILP solvability requires a linked companion issue.
Example Instance	✅ Present and mostly correct (but see K=2 error below)
Expected Outcome	❌ Missing. The issue shows the example but does not have a separate "Expected Outcome" section stating the answer (YES/NO) with justification. The K=4 verification is inline but not structured as required.

4b — Definition Completeness: The definition is a direct copy from G&J and is precise. ✅

4c — Symbol and Notation Consistency: Symbols (M, n, K, C, i, j) are consistent between the definition and example. ✅

4d — Example Quality:

• Non-trivial: 6x6 matrix with 10 non-zero entries — adequate size. ✅
• Exercises core structure: Uses row/column domination — appropriate. ✅
• Round-trip testable: The K=4 solution has multiple feasible configurations (e.g., different sets of 4 entries could work), satisfying the "at least 2 suboptimal feasible solutions" criterion for a decision problem. ✅
• Incorrect parenthetical claim: The final sentence claiming K=2 suffices is wrong (see Correctness above) and must be removed or corrected. ❌

Recommendations

• Add a concrete planned reduction connecting MatrixDomination to an existing problem (e.g., MatrixDomination -> ILP, or a reduction from/to an edge-related graph problem like MinimumEdgeDominatingSet if that is added).
• File a companion [Rule] MatrixDomination to ILP issue and link it, since direct ILP solvability is claimed.
• Add an explicit "Expected Outcome" section: for the K=4 instance, state "Answer: YES" with the witness solution.
• Remove or correct the K=2 claim at the end of the example — it is mathematically incorrect for matrix domination.
• Consider noting that the Yannakakis-Gavril paper was published in 1980 (SIAM J. Applied Math.), not 1978, though Garey & Johnson cite the 1978 technical report.
• Consider searching for a dedicated exact algorithm that improves on brute-force O*(2^s) — the problem's connection to edge dominating set may yield better bounds from that literature.

[isPANN]

Converted from decision framing (MatrixDomination with bound K) to optimization framing (MinimumMatrixDomination — minimize dominating entries). Removed PoorWritten label. Companion rule issue: #937 (MinimumMaximalMatching → MinimumMatrixDomination). Note: MinimumMaximalMatching is not yet in the codebase.

[isPANN]

Fix-issue changelog

• Associated rules: Linked [Rule] MINIMUM MAXIMAL MATCHING to MinimumMatrixDomination #847 (MinimumMaximalMatching → MinimumMatrixDomination).
• Example: Cleaned up messy false-start attempts; single clean solution C={(0,1),(1,0),(3,4),(4,3)} with step-by-step verification. Removed incorrect K=2 claim.
• Complexity: Fixed Yannakakis-Gavril year (1978→1980). Added concrete expression "2^num_ones".
• Schema notes: Added Value = Min<usize> and getter methods.
• ILP: Added companion rule note with ILP formulation.
• Added Python validation script confirming Min(4).

Applied by /fix-issue.