problemreductions/rules/

threedimensionalmatching_minimumweightdecoding.rs

//! Reduction from ThreeDimensionalMatching to MinimumWeightDecoding.
//!
//! This is the classical Berlekamp–McEliece–van Tilborg (1978) construction
//! (Garey & Johnson MS7) that establishes NP-hardness of the minimum-weight
//! codeword problem. Each triple `t_j = (a_j, b_j, c_j)` becomes a column of
//! a `3q × m` parity-check matrix `H` with exactly three 1s (one per row
//! block `W`, `X`, `Y`), and the syndrome is the all-ones vector `1^{3q}`.
//!
//! **Bridge.** This is a *witness* reduction from `ThreeDimensionalMatching`
//! (`Value = Or`) to `MinimumWeightDecoding` (`Value = Min<usize>`):
//!
//! `source.evaluate(S) == Or(true)` ⇔ `target.evaluate(x) == Min(Some(q))`,
//!
//! where `S = { t_j ∈ T : x_j = 1 }`. The completed optimum maps to YES/NO
//! by comparison with `q`; only a weight-`q` target witness is decoded.
//!
//! **Sentinel branch.** `MinimumWeightDecoding::new` panics on zero-row or
//! zero-column matrices, so degenerate inputs (`q = 0` or `T = []`) emit a
//! fixed `1×1` sentinel `H = [[1]]` with syndrome `s = [0]`. The unique
//! feasible codeword `x = (0)` has weight zero, so the aggregate mapping returns
//! YES iff `q = 0`. Only that YES case decodes to the empty subset.

use crate::models::algebraic::MinimumWeightDecoding;
use crate::models::set::ThreeDimensionalMatching;
use crate::reduction;
use crate::rules::traits::{ReduceTo, ReductionResult};

/// Result of reducing ThreeDimensionalMatching to MinimumWeightDecoding.
#[derive(Debug, Clone)]
pub struct ReductionThreeDimensionalMatchingToMinimumWeightDecoding {
    target: MinimumWeightDecoding,
    /// Number of triples in the original 3DM instance.
    /// Used to return a correctly-sized witness when the sentinel path is
    /// taken (i.e. `q == 0` or `num_triples == 0`).
    source_num_triples: usize,
    source_universe_size: usize,
}

impl ReductionResult for ReductionThreeDimensionalMatchingToMinimumWeightDecoding {
    type Source = ThreeDimensionalMatching;
    type Target = MinimumWeightDecoding;

    fn target_problem(&self) -> &Self::Target {
        &self.target
    }

    /// The target codeword prefix is the source subset indicator over the same
    /// triple index set. The sentinel target appends one synthetic column, so
    /// an empty source maps back to the empty prefix.
    fn extract_solution(
        &self,
        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
        crate::rules::traits::validate_target_witness(
            self.target_problem(),
            target_solution,
            |value| crate::rules::AggregateReductionResult::extract_value(self, value).0,
            "target witness does not certify a YES answer for the source",
        )?;
        if target_solution.len() != self.target.num_cols() {
            return Err(crate::rules::ExtractionError::invalid(format!(
                "expected {} target codeword bits, got {}",
                self.target.num_cols(),
                target_solution.len()
            )));
        }

        Ok(target_solution[..self.source_num_triples].to_vec())
    }
}

#[crate::aggregate_reduction]
impl crate::rules::AggregateReductionResult
    for ReductionThreeDimensionalMatchingToMinimumWeightDecoding
{
    type Source = ThreeDimensionalMatching;
    type Target = MinimumWeightDecoding;

    fn target_problem(&self) -> &Self::Target {
        &self.target
    }

    fn extract_value(&self, value: crate::types::Min<i64>) -> crate::types::Or {
        crate::types::Or(
            value
                .0
                .is_some_and(|count| i128::from(count) == self.source_universe_size as i128),
        )
    }
}

#[reduction(
    transform = exact {
        num_rows = "3 * universe_size",
        num_cols = "num_triples",
    })]
impl ReduceTo<MinimumWeightDecoding> for ThreeDimensionalMatching {
    type Result = ReductionThreeDimensionalMatchingToMinimumWeightDecoding;

    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
        let q = self.universe_size();
        let m = self.num_triples();

        if q == 0 || m == 0 {
            // Sentinel: MinimumWeightDecoding::new panics on empty matrices
            // or zero-column matrices. Build a fixed 1×1 instance whose only
            // feasible codeword is x = (0), decoding to S = ∅. The source's
            // own evaluate on the empty set gives the correct answer:
            //   q = 0 → Or(true)  (empty matching of empty universe)
            //   q ≥ 1 → Or(false) (no triples cannot cover non-empty universe).
            return Ok(ReductionThreeDimensionalMatchingToMinimumWeightDecoding {
                source_universe_size: q,
                target: MinimumWeightDecoding::new(vec![vec![true]], vec![false]),
                source_num_triples: m,
            });
        }

        // Main branch: build H ∈ {0,1}^{3q × m} with row blocks W, X, Y and
        // one 1 per row block per column at the triple's coordinate.
        let num_rows = 3 * q;
        let mut matrix = vec![vec![false; m]; num_rows];
        for (j, &(a, b, c)) in self.triples().iter().enumerate() {
            matrix[a][j] = true;
            matrix[q + b][j] = true;
            matrix[2 * q + c][j] = true;
        }
        let syndrome = vec![true; num_rows];

        Ok(ReductionThreeDimensionalMatchingToMinimumWeightDecoding {
            source_universe_size: q,
            target: MinimumWeightDecoding::new(matrix, syndrome),
            source_num_triples: m,
        })
    }
}

#[cfg(feature = "example-db")]
pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
    use crate::export::SolutionPair;

    vec![crate::example_db::specs::RuleExampleSpec {
        id: "threedimensionalmatching_to_minimumweightdecoding",
        build: || {
            // q = 2, T = [(0,0,0), (1,1,1), (0,1,0), (1,0,1)].
            // Perfect matchings: {t_0, t_1} and {t_2, t_3} -- both attain
            // target minimum weight = q = 2.
            crate::example_db::specs::rule_example_with_witness::<_, MinimumWeightDecoding>(
                ThreeDimensionalMatching::new(2, vec![(0, 0, 0), (1, 1, 1), (0, 1, 0), (1, 0, 1)]),
                SolutionPair {
                    source_config: serde_json::json!(vec![true, true, false, false]),
                    target_config: serde_json::json!(vec![true, true, false, false]),
                },
            )
        },
    }]
}

#[cfg(test)]
#[path = "../unit_tests/rules/threedimensionalmatching_minimumweightdecoding.rs"]
mod tests;