problemreductions/rules/

decisionminimumvertexcover_hamiltoniancircuit.rs

//! Reduction from Decision Minimum Vertex Cover to Hamiltonian Circuit.
//!
//! This implements the gadget construction from Garey & Johnson, Theorem 3.4,
//! on the unit-weight `Decision<MinimumVertexCover<SimpleGraph, One>>` model.

use crate::models::decision::Decision;
use crate::models::graph::{HamiltonianCircuit, MinimumVertexCover};
use crate::reduction;
use crate::rules::traits::{ReduceTo, ReductionResult};
use crate::topology::{Graph, SimpleGraph};
use crate::types::One;
use std::collections::BTreeSet;

#[derive(Debug, Clone)]
enum ConstructionKind {
    FixedYes { source_cover: Vec<bool> },
    FixedNo,
    Theorem(TheoremConstruction),
}

#[derive(Debug, Clone)]
struct TheoremConstruction {
    forced_cover: Vec<bool>,
    selector_count: usize,
    edges: Vec<(usize, usize)>,
    incident_edges: Vec<Vec<usize>>,
}

impl TheoremConstruction {
    fn active_vertices(&self) -> impl Iterator<Item = usize> + '_ {
        self.incident_edges
            .iter()
            .enumerate()
            .filter(|(_, edges)| !edges.is_empty())
            .map(|(v, _)| v)
    }

    fn gadget_base(&self, edge_idx: usize) -> usize {
        self.selector_count + 12 * edge_idx
    }

    fn gadget_vertex(&self, edge_idx: usize, vertex: usize, position: usize) -> usize {
        let (u, v) = self.edges[edge_idx];
        let side = if vertex == u {
            0
        } else if vertex == v {
            1
        } else {
            panic!(
                "vertex {vertex} is not incident on edge {:?}",
                self.edges[edge_idx]
            );
        };

        self.gadget_base(edge_idx) + side * 6 + (position - 1)
    }

    fn path_endpoints(&self, vertex: usize) -> Option<(usize, usize)> {
        let incident = self.incident_edges.get(vertex)?;
        let first = *incident.first()?;
        let last = *incident.last()?;
        Some((
            self.gadget_vertex(first, vertex, 1),
            self.gadget_vertex(last, vertex, 6),
        ))
    }

    fn covers_all_edges(&self, selected: &[bool]) -> bool {
        self.edges
            .iter()
            .all(|&(u, v)| selected.get(u) == Some(&true) || selected.get(v) == Some(&true))
    }

    #[cfg(any(test, feature = "example-db"))]
    fn exact_selected_vertices(&self, source_cover: &[bool]) -> Option<Vec<usize>> {
        if source_cover.len() != self.forced_cover.len() || !self.covers_all_edges(source_cover) {
            return None;
        }

        let mut selected: Vec<usize> = self
            .active_vertices()
            .filter(|&v| source_cover[v])
            .collect();

        if selected.len() > self.selector_count {
            return None;
        }

        for v in self.active_vertices() {
            if selected.len() == self.selector_count {
                break;
            }
            if !source_cover[v] {
                selected.push(v);
            }
        }

        (selected.len() == self.selector_count).then_some(selected)
    }

    #[cfg(any(test, feature = "example-db"))]
    fn gadget_segment(
        &self,
        edge_idx: usize,
        vertex: usize,
        selected_exact: &BTreeSet<usize>,
    ) -> Vec<usize> {
        let (u, v) = self.edges[edge_idx];
        let other = if vertex == u {
            v
        } else if vertex == v {
            u
        } else {
            panic!(
                "vertex {vertex} is not incident on edge {:?}",
                self.edges[edge_idx]
            );
        };

        if selected_exact.contains(&other) {
            return (1..=6)
                .map(|position| self.gadget_vertex(edge_idx, vertex, position))
                .collect();
        }

        if vertex == u {
            vec![
                self.gadget_vertex(edge_idx, u, 1),
                self.gadget_vertex(edge_idx, u, 2),
                self.gadget_vertex(edge_idx, u, 3),
                self.gadget_vertex(edge_idx, v, 1),
                self.gadget_vertex(edge_idx, v, 2),
                self.gadget_vertex(edge_idx, v, 3),
                self.gadget_vertex(edge_idx, v, 4),
                self.gadget_vertex(edge_idx, v, 5),
                self.gadget_vertex(edge_idx, v, 6),
                self.gadget_vertex(edge_idx, u, 4),
                self.gadget_vertex(edge_idx, u, 5),
                self.gadget_vertex(edge_idx, u, 6),
            ]
        } else {
            vec![
                self.gadget_vertex(edge_idx, v, 1),
                self.gadget_vertex(edge_idx, v, 2),
                self.gadget_vertex(edge_idx, v, 3),
                self.gadget_vertex(edge_idx, u, 1),
                self.gadget_vertex(edge_idx, u, 2),
                self.gadget_vertex(edge_idx, u, 3),
                self.gadget_vertex(edge_idx, u, 4),
                self.gadget_vertex(edge_idx, u, 5),
                self.gadget_vertex(edge_idx, u, 6),
                self.gadget_vertex(edge_idx, v, 4),
                self.gadget_vertex(edge_idx, v, 5),
                self.gadget_vertex(edge_idx, v, 6),
            ]
        }
    }

    #[cfg(any(test, feature = "example-db"))]
    fn vertex_path(&self, vertex: usize, selected_exact: &BTreeSet<usize>) -> Vec<usize> {
        let mut path = Vec::new();
        for &edge_idx in &self.incident_edges[vertex] {
            path.extend(self.gadget_segment(edge_idx, vertex, selected_exact));
        }
        path
    }

    #[cfg(any(test, feature = "example-db"))]
    fn build_target_witness(&self, source_cover: &[bool]) -> Vec<usize> {
        let Some(selected_vertices) = self.exact_selected_vertices(source_cover) else {
            return Vec::new();
        };

        let selected_exact: BTreeSet<usize> = selected_vertices.iter().copied().collect();
        let mut witness = Vec::with_capacity(self.selector_count + 12 * self.edges.len());

        for (selector, &vertex) in selected_vertices.iter().enumerate() {
            witness.push(selector);
            witness.extend(self.vertex_path(vertex, &selected_exact));
        }

        witness
    }

    fn decode_solution(
        &self,
        target_solution: &[usize],
    ) -> crate::rules::ExtractionResult<Vec<bool>> {
        Ok({
            let mut source_cover = self.forced_cover.clone();

            let mut positions = vec![usize::MAX; target_solution.len()];
            for (idx, &vertex) in target_solution.iter().enumerate() {
                positions[vertex] = idx;
            }

            let len = target_solution.len();
            let touches_selector = |vertex: usize| {
                let idx = positions[vertex];
                let prev = target_solution[(idx + len - 1) % len];
                let next = target_solution[(idx + 1) % len];
                prev < self.selector_count || next < self.selector_count
            };

            for vertex in self.active_vertices() {
                let Some((start, end)) = self.path_endpoints(vertex) else {
                    continue;
                };
                if touches_selector(start) && touches_selector(end) {
                    source_cover[vertex] = true;
                }
            }

            let selected_count = self.active_vertices().filter(|&v| source_cover[v]).count();
            if selected_count != self.selector_count || !self.covers_all_edges(&source_cover) {
                return Err(crate::rules::ExtractionError::invalid(
                    "target circuit does not encode a source vertex cover of the required size",
                ));
            }

            source_cover
        })
    }
}

/// Result of reducing Decision<MinimumVertexCover<SimpleGraph, One>> to
/// HamiltonianCircuit<SimpleGraph>.
#[derive(Debug, Clone)]
pub struct ReductionDecisionMinimumVertexCoverToHamiltonianCircuit {
    target: HamiltonianCircuit<SimpleGraph>,
    construction: ConstructionKind,
}

impl ReductionDecisionMinimumVertexCoverToHamiltonianCircuit {
    #[cfg(any(test, feature = "example-db"))]
    fn build_target_witness(&self, source_cover: &[bool]) -> Vec<usize> {
        match &self.construction {
            ConstructionKind::FixedYes { .. } => vec![0, 1, 2],
            ConstructionKind::FixedNo => Vec::new(),
            ConstructionKind::Theorem(construction) => {
                construction.build_target_witness(source_cover)
            }
        }
    }
}

impl ReductionResult for ReductionDecisionMinimumVertexCoverToHamiltonianCircuit {
    type Source = Decision<MinimumVertexCover<SimpleGraph, One>>;
    type Target = HamiltonianCircuit<SimpleGraph>;

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

    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| value.0,
            "target configuration is not a Hamiltonian circuit",
        )?;

        Ok({
            match &self.construction {
                ConstructionKind::FixedYes { source_cover } => source_cover.clone(),
                ConstructionKind::FixedNo => {
                    return Err(crate::rules::ExtractionError::invalid(
                        "the fixed negative target instance has no extractable witness",
                    ))
                }
                ConstructionKind::Theorem(construction) => {
                    construction.decode_solution(target_solution)?
                }
            }
        })
    }
}

fn normalize_edges(edges: Vec<(usize, usize)>) -> Vec<(usize, usize)> {
    let mut normalized: Vec<_> = edges
        .into_iter()
        .map(|(u, v)| if u < v { (u, v) } else { (v, u) })
        .collect();
    normalized.sort_unstable();
    normalized.dedup();
    normalized
}

fn insert_edge(edges: &mut BTreeSet<(usize, usize)>, a: usize, b: usize) {
    let edge = if a < b { (a, b) } else { (b, a) };
    edges.insert(edge);
}

#[crate::aggregate_reduction(identity)]
impl crate::rules::AggregateReductionResult
    for ReductionDecisionMinimumVertexCoverToHamiltonianCircuit
{
}

// Normalized surviving edges m'<=m contribute 14m' gadget edges;
// incident chains add <=2m', selectors <=2n^2. Set deduplication only
// decreases these counts; fixed YES/NO targets have at most three edges.
#[reduction(transform = upper_bound {
    num_vertices = "num_vertices + 12 * num_edges + 3",
    num_edges = "16 * num_edges + 2 * num_vertices^2 + 3",
})]
impl ReduceTo<HamiltonianCircuit<SimpleGraph>> for Decision<MinimumVertexCover<SimpleGraph, One>> {
    type Result = ReductionDecisionMinimumVertexCoverToHamiltonianCircuit;

    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
        let num_source_vertices = self.inner().graph().num_vertices();
        // A loop forces its vertex into every cover. Reduce the remaining
        // loopless graph with the budget left after selecting those vertices.
        let mut forced_cover = vec![false; num_source_vertices];
        let mut edges = normalize_edges(self.inner().graph().edges());
        for &(u, v) in &edges {
            if u == v {
                forced_cover[u] = true;
            }
        }
        let raw_bound = i128::from(*self.bound())
            - forced_cover.iter().filter(|&&selected| selected).count() as i128;
        edges.retain(|&(u, v)| !forced_cover[u] && !forced_cover[v]);
        if raw_bound < 0 {
            return Ok(ReductionDecisionMinimumVertexCoverToHamiltonianCircuit {
                target: HamiltonianCircuit::new(SimpleGraph::path(3)),
                construction: ConstructionKind::FixedNo,
            });
        }

        let mut incident_edges = vec![Vec::new(); num_source_vertices];
        for (edge_idx, &(u, v)) in edges.iter().enumerate() {
            incident_edges[u].push(edge_idx);
            incident_edges[v].push(edge_idx);
        }

        let active_vertices: Vec<_> = incident_edges
            .iter()
            .enumerate()
            .filter(|(_, incident)| !incident.is_empty())
            .map(|(vertex, _)| vertex)
            .collect();
        let active_count = active_vertices.len();

        if raw_bound >= active_count as i128 {
            let mut source_cover = forced_cover;
            for vertex in active_vertices {
                source_cover[vertex] = true;
            }
            return Ok(ReductionDecisionMinimumVertexCoverToHamiltonianCircuit {
                target: HamiltonianCircuit::new(SimpleGraph::cycle(3)),
                construction: ConstructionKind::FixedYes { source_cover },
            });
        }

        if raw_bound == 0 {
            return Ok(ReductionDecisionMinimumVertexCoverToHamiltonianCircuit {
                target: HamiltonianCircuit::new(SimpleGraph::path(3)),
                construction: ConstructionKind::FixedNo,
            });
        }

        let construction = TheoremConstruction {
            forced_cover,
            selector_count: usize::try_from(raw_bound)
                .expect("nonnegative bound is smaller than the active vertex count"),
            edges,
            incident_edges,
        };

        let mut target_edges = BTreeSet::new();
        for (edge_idx, &(u, v)) in construction.edges.iter().enumerate() {
            for position in 1..6 {
                insert_edge(
                    &mut target_edges,
                    construction.gadget_vertex(edge_idx, u, position),
                    construction.gadget_vertex(edge_idx, u, position + 1),
                );
                insert_edge(
                    &mut target_edges,
                    construction.gadget_vertex(edge_idx, v, position),
                    construction.gadget_vertex(edge_idx, v, position + 1),
                );
            }

            insert_edge(
                &mut target_edges,
                construction.gadget_vertex(edge_idx, u, 3),
                construction.gadget_vertex(edge_idx, v, 1),
            );
            insert_edge(
                &mut target_edges,
                construction.gadget_vertex(edge_idx, v, 3),
                construction.gadget_vertex(edge_idx, u, 1),
            );
            insert_edge(
                &mut target_edges,
                construction.gadget_vertex(edge_idx, u, 6),
                construction.gadget_vertex(edge_idx, v, 4),
            );
            insert_edge(
                &mut target_edges,
                construction.gadget_vertex(edge_idx, v, 6),
                construction.gadget_vertex(edge_idx, u, 4),
            );
        }

        for vertex in construction.active_vertices() {
            let incident = &construction.incident_edges[vertex];
            for window in incident.windows(2) {
                insert_edge(
                    &mut target_edges,
                    construction.gadget_vertex(window[0], vertex, 6),
                    construction.gadget_vertex(window[1], vertex, 1),
                );
            }

            let (start, end) = construction.path_endpoints(vertex).ok_or_else(|| {
                crate::rules::ReductionError::invalid_target::<
                    Decision<MinimumVertexCover<SimpleGraph, One>>,
                    HamiltonianCircuit<SimpleGraph>,
                >("active source vertex has no Hamiltonian gadget path endpoints")
            })?;
            for selector in 0..construction.selector_count {
                insert_edge(&mut target_edges, selector, start);
                insert_edge(&mut target_edges, selector, end);
            }
        }

        let target = HamiltonianCircuit::new(SimpleGraph::new(
            construction.selector_count + 12 * construction.edges.len(),
            target_edges.into_iter().collect(),
        ));

        Ok(ReductionDecisionMinimumVertexCoverToHamiltonianCircuit {
            target,
            construction: ConstructionKind::Theorem(construction),
        })
    }
}

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

    vec![crate::example_db::specs::RuleExampleSpec {
        id: "decisionminimumvertexcover_to_hamiltoniancircuit",
        build: || {
            let source = Decision::new(
                MinimumVertexCover::new(SimpleGraph::new(3, vec![(0, 1), (1, 2)]), vec![One; 3]),
                1,
            );
            let source_config = vec![false, true, false];
            let reduction = ReduceTo::<HamiltonianCircuit<SimpleGraph>>::reduce_to(&source)
                .expect("reduction should succeed");
            let target_config = reduction.build_target_witness(&source_config);
            assemble_rule_example(
                &source,
                reduction.target_problem(),
                vec![SolutionPair {
                    source_config: serde_json::to_value(source_config)
                        .expect("solution serialization must succeed"),
                    target_config: serde_json::to_value(target_config)
                        .expect("solution serialization must succeed"),
                }],
            )
        },
    }]
}

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