problemreductions/rules/
maximumindependentset_gridgraph.rs

1//! Reduction from unweighted MaximumIndependentSet on SimpleGraph to KingsSubgraph
2//! using the King's Subgraph (KSG) unit disk mapping.
3//!
4//! Maps an arbitrary graph's MIS problem to an equivalent MIS on a grid graph.
5
6use crate::models::graph::MaximumIndependentSet;
7use crate::reduction;
8use crate::rules::traits::{ReduceTo, ReductionResult};
9use crate::rules::unitdiskmapping::ksg;
10use crate::topology::{Graph, KingsSubgraph, SimpleGraph};
11use crate::types::One;
12
13/// Result of reducing MIS<SimpleGraph, One> to MIS<KingsSubgraph, One>.
14#[derive(Debug, Clone)]
15pub struct ReductionISSimpleOneToGridOne {
16    target: MaximumIndependentSet<KingsSubgraph, One>,
17    mapping_result: ksg::MappingResult<ksg::KsgTapeEntry>,
18}
19
20impl ReductionResult for ReductionISSimpleOneToGridOne {
21    type Source = MaximumIndependentSet<SimpleGraph, One>;
22    type Target = MaximumIndependentSet<KingsSubgraph, One>;
23
24    fn target_problem(&self) -> &Self::Target {
25        &self.target
26    }
27
28    fn extract_solution(
29        &self,
30        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
31    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
32        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
33
34        let encoded = crate::config::bits_to_config(target_solution);
35        let mapped = self.mapping_result.map_config_back(&encoded)?;
36        Ok(crate::config::config_to_bits(&mapped))
37    }
38}
39
40#[reduction(
41    transform = upper_bound {
42        num_vertices = "16 * num_vertices^2 + 32 * num_vertices + 12",
43        num_edges = "64 * num_vertices^2 + 128 * num_vertices + 48",
44    }
45)]
46impl ReduceTo<MaximumIndependentSet<KingsSubgraph, One>>
47    for MaximumIndependentSet<SimpleGraph, One>
48{
49    type Result = ReductionISSimpleOneToGridOne;
50
51    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
52        let n = self.graph().num_vertices();
53        let edges = self.graph().edges();
54        let result = ksg::map_unweighted(n, &edges).map_err(|error| {
55            error.for_reduction::<Self, MaximumIndependentSet<KingsSubgraph, One>>()
56        })?;
57        let grid = result.to_kings_subgraph();
58        let weights = vec![One; grid.num_vertices()];
59        let target = MaximumIndependentSet::new(grid, weights);
60        Ok(ReductionISSimpleOneToGridOne {
61            target,
62            mapping_result: result,
63        })
64    }
65}
66
67#[cfg(test)]
68#[path = "../unit_tests/rules/maximumindependentset_gridgraph.rs"]
69mod tests;
problemreductions/rules/maximumindependentset_gridgraph.rs

problemreductions/rules/
maximumindependentset_gridgraph.rs
