[Design] Decision wrapper for converting optimization problems to decision problems

[GiggleLiu]

Motivation

Several classical NP-completeness reductions in Garey & Johnson operate between decision versions of problems, but the codebase models are optimization problems. This blocks at least 2 high-confidence reduction rules:

• [Rule] DOMINATING SET to MIN-MAX MULTICENTER #379 MinimumDominatingSet → MinMaxMulticenter: Min<W::Sum> → Or type mismatch. The classical reduction sets k=K (decision bound) and B=1, but MinimumDominatingSet has no K parameter.
• [Rule] DOMINATING SET to MIN-SUM MULTICENTER #380 MinimumDominatingSet → MinimumSumMulticenter: Min<W::Sum> → Min<W::Sum> types match, but the target's k parameter must come from the source's unknown optimal dominating set size.

Similar mismatches will arise for other GJ reductions where the source is an optimization problem but the classical reduction needs a decision bound (e.g., VertexCover→HamiltonianCircuit in PR #996).

Proposal

Add a generic Decision<P> wrapper that converts any optimization problem P with Value = Min<V> or Value = Max<V> into a decision problem with Value = Or and a bound parameter:

/// Decision version of an optimization problem.
/// Asks: "does there exist a config with value ≤ bound (for Min) or ≥ bound (for Max)?"
pub struct Decision<P: Problem> {
    inner: P,
    bound: P::Value,  // or the inner numeric type
}

impl<P: Problem> Problem for Decision<P>
where P::Value: PartialOrd {
    type Value = Or;
    fn evaluate(&self, config: &[usize]) -> Or {
        Or(self.inner.evaluate(config) <= self.bound)  // for Min
    }
}

This would allow:

• Decision<MinimumDominatingSet<G, W>> with bound K → feeds into MinMaxMulticenter reduction
• Decision<MinimumVertexCover<G, W>> with bound K → feeds into HamiltonianCircuit reduction
• Any future optimization→decision reduction

Design questions

1. Naming: Decision<P> vs Bounded<P> vs per-problem wrappers like DominatingSet?
2. Registry integration: Should Decision<P> auto-register variants, or require explicit declare_variants!?
3. Reduction trait: Should ReduceTo support Decision<Source> → Target, or should we create explicit decision-variant models?
4. Overhead expressions: The bound parameter doesn't come from a source getter — how to express overhead?
5. Min vs Max: Need both ≤ bound (for Min) and ≥ bound (for Max) semantics.

Blocked rules

Rule	Source	Target	Mismatch
#379	MinimumDominatingSet(Min)	MinMaxMulticenter(Or)	No K param on source
#380	MinimumDominatingSet(Min)	MinimumSumMulticenter(Min)	Target k from unknown optimum
#198	MinimumVertexCover(Min)	HamiltonianCircuit(Or)	Min→Or
#894	MinimumVertexCover(Min)	PartialFeedbackEdgeSet(Or)	Min→Or
#890	MaxCut(Max)	OptimalLinearArrangement(Min)	Max→Min

References

• PR docs: verify-reduction — 5 type-incompatible reductions (math verified, needs decision variants) #996 documents 5 type-incompatible reductions with math verification
• Garey & Johnson's reductions universally use decision versions