Skip to content

[Rule] EXACT COVER BY 3-SETS to MINIMUM EDGE-COST FLOW #362

@isPANN

Description

@isPANN

Source: EXACT COVER BY 3-SETS
Target: MINIMUM EDGE-COST FLOW
Motivation: Skipped — source problem X3C is a specialization of Set Covering (each set has exactly 3 elements, exact cover required). Implement the general Set Covering reductions first.
Reference: Garey & Johnson, Computers and Intractability, ND32, p.214

Specialization Note

  • X3C (Exact Cover by 3-Sets) is a restriction of Set Covering where each set has exactly 3 elements and an exact cover is required.
  • MinimumSetCovering exists in codebase at src/models/set/minimum_set_covering.rs.
  • X3C itself does not yet have a dedicated model. It could be modeled as a MinimumSetCovering instance with constraints, or as a separate type.
  • Blocked on: X3C model implementation (P129).

Metadata

Metadata

Assignees

No one assigned

    Labels

    ruleA new reduction rule to be added.

    Type

    No type

    Projects

    Status

    Backlog

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions