problemreductions/models/graph/
maximum_independent_set.rs

1//! Independent Set problem implementation.
2//!
3//! The Independent Set problem asks for a maximum weight subset of vertices
4//! such that no two vertices in the subset are adjacent.
5
6use crate::registry::{
7    ConstructionError, CreateSpec, FieldInfo, ProblemSchemaEntry, VariantDimension,
8};
9use crate::topology::{Graph, KingsSubgraph, SimpleGraph, TriangularSubgraph, UnitDiskGraph};
10use crate::traits::Problem;
11use crate::types::{Max, One, WeightElement};
12use num_traits::Zero;
13use serde::{Deserialize, Serialize};
14
15inventory::submit! {
16    ProblemSchemaEntry {
17        name: "MaximumIndependentSet",
18        display_name: "Maximum Independent Set",
19        aliases: &["MIS"],
20        dimensions: &[
21            VariantDimension::new("graph", "SimpleGraph", &["SimpleGraph", "KingsSubgraph", "TriangularSubgraph", "UnitDiskGraph"]),
22            VariantDimension::new("weight", "One", &["One", "i64", "f64"]),
23        ],
24        category: crate::registry::ProblemCategory::Graph,
25        module_path: module_path!(),
26        description: "Find maximum weight independent set in a graph",
27        fields: MaximumIndependentSetSimpleI64CreateSpec::FIELDS,
28    }
29}
30
31/// The Independent Set problem.
32///
33/// Given a graph G = (V, E) and weights w_v for each vertex,
34/// find a subset S ⊆ V such that:
35/// - No two vertices in S are adjacent (independent set constraint)
36/// - The total weight Σ_{v ∈ S} w_v is maximized
37///
38/// # Type Parameters
39///
40/// * `G` - The graph type (e.g., `SimpleGraph`, `KingsSubgraph`, `UnitDiskGraph`)
41/// * `W` - The weight type (e.g., `i64`, `f64`, `One`)
42///
43/// # Example
44///
45/// ```
46/// use problemreductions::models::graph::MaximumIndependentSet;
47/// use problemreductions::topology::SimpleGraph;
48/// use problemreductions::{Problem, BruteForce};
49///
50/// // Create a triangle graph (3 vertices, 3 edges)
51/// let graph = SimpleGraph::new(3, vec![(0, 1), (1, 2), (0, 2)]);
52/// let problem = MaximumIndependentSet::new(graph, vec![1; 3]);
53///
54/// // Solve with brute force
55/// let solver = BruteForce::new();
56/// let solutions = solver.find_all_witnesses(&problem).unwrap();
57///
58/// // Maximum independent set in a triangle has size 1
59/// assert!(solutions.iter().all(|s| s.iter().filter(|&&selected| selected).count() == 1));
60/// ```
61#[derive(Debug, Clone, Serialize, Deserialize)]
62#[serde(try_from = "MaximumIndependentSetData<G, W>")]
63#[serde(bound(deserialize = "G: Graph + Deserialize<'de>, W: Clone + Default + Deserialize<'de>"))]
64pub struct MaximumIndependentSet<G, W> {
65    /// The underlying graph.
66    graph: G,
67    /// Weights for each vertex.
68    weights: Vec<W>,
69}
70
71#[derive(Deserialize)]
72struct MaximumIndependentSetData<G, W> {
73    graph: G,
74    weights: Vec<W>,
75}
76
77impl<G, W> TryFrom<MaximumIndependentSetData<G, W>> for MaximumIndependentSet<G, W>
78where
79    G: Graph,
80    W: Clone + Default,
81{
82    type Error = crate::registry::ConstructionError;
83
84    fn try_from(data: MaximumIndependentSetData<G, W>) -> Result<Self, Self::Error> {
85        Self::try_new(data.graph, data.weights)
86    }
87}
88
89macro_rules! simple_mis_spec {
90    ($name:ident,$weight:ty,$one:expr $(, $weights:ident)?) => {
91        #[derive(Debug, Deserialize, crate::CreateSpec)]
92        struct $name {
93            #[create(codec = "edge-list")]
94            graph: Vec<(usize, usize)>,
95            num_vertices: Option<usize>,
96            $(
97            #[create(codec = "comma-separated")]
98            $weights: Option<Vec<$weight>>,
99            )?
100        }
101        impl TryFrom<$name> for MaximumIndependentSet<SimpleGraph, $weight> {
102            type Error = crate::registry::ConstructionError;
103            fn try_from(spec: $name) -> Result<Self, crate::registry::ConstructionError> {
104                if spec.graph.is_empty() && spec.num_vertices.is_none() {
105                    return Err("num_vertices is required for an empty graph".into());
106                }
107                for &(u, v) in &spec.graph {
108                    if u == v {
109                        return Err("self-loops are not allowed".into());
110                    }
111                }
112                let inferred = spec
113                    .graph
114                    .iter()
115                    .flat_map(|&(u, v)| [u, v])
116                    .max()
117                    .map(|v| v.checked_add(1).ok_or("vertex count overflows usize"))
118                    .transpose()?
119                    .unwrap_or(0);
120                let count = spec.num_vertices.unwrap_or(inferred);
121                if count < inferred {
122                    return Err("num_vertices is too small".into());
123                }
124                let weights = { $(if let Some(value) = spec.$weights { value } else)? { vec![$one; count] } };
125                Self::try_new(SimpleGraph::new(count, spec.graph), weights)
126            }
127        }
128    };
129}
130simple_mis_spec!(MaximumIndependentSetSimpleOneCreateSpec, One, One);
131simple_mis_spec!(
132    MaximumIndependentSetSimpleI64CreateSpec,
133    i64,
134    1_i64,
135    weights
136);
137simple_mis_spec!(
138    MaximumIndependentSetSimpleF64CreateSpec,
139    f64,
140    1_f64,
141    weights
142);
143
144macro_rules! grid_mis_spec {
145    ($name:ident,$graph:ty,$weight:ty,$one:expr $(, $weights:ident)?) => {
146        #[derive(Debug, Deserialize, crate::CreateSpec)]
147        struct $name {
148            positions: Vec<(i64, i64)>,
149            $(
150            #[create(codec = "comma-separated")]
151            $weights: Option<Vec<$weight>>,
152            )?
153        }
154        impl TryFrom<$name> for MaximumIndependentSet<$graph, $weight> {
155            type Error = crate::registry::ConstructionError;
156            fn try_from(spec: $name) -> Result<Self, crate::registry::ConstructionError> {
157                let weights = { $(if let Some(value) = spec.$weights { value } else)? { vec![$one; spec.positions.len()] } };
158                Self::try_new(<$graph>::new(spec.positions), weights)
159            }
160        }
161    };
162}
163grid_mis_spec!(
164    MaximumIndependentSetKingsOneCreateSpec,
165    KingsSubgraph,
166    One,
167    One
168);
169grid_mis_spec!(
170    MaximumIndependentSetKingsI64CreateSpec,
171    KingsSubgraph,
172    i64,
173    1_i64,
174    weights
175);
176grid_mis_spec!(
177    MaximumIndependentSetTriangularI64CreateSpec,
178    TriangularSubgraph,
179    i64,
180    1_i64,
181    weights
182);
183
184macro_rules! unit_disk_mis_spec {
185    ($name:ident,$weight:ty,$one:expr $(, $weights:ident)?) => {
186        #[derive(Debug, Deserialize, crate::CreateSpec)]
187        struct $name {
188            positions: Vec<(f64, f64)>,
189            radius: Option<f64>,
190            $(
191            #[create(codec = "comma-separated")]
192            $weights: Option<Vec<$weight>>,
193            )?
194        }
195        impl TryFrom<$name> for MaximumIndependentSet<UnitDiskGraph, $weight> {
196            type Error = ConstructionError;
197            fn try_from(spec: $name) -> Result<Self, ConstructionError> {
198                let radius = spec.radius.unwrap_or(1.0);
199                let weights = { $(if let Some(value) = spec.$weights { value } else)? { vec![$one; spec.positions.len()] } };
200                Self::try_new(UnitDiskGraph::new(spec.positions, radius)?, weights)
201            }
202        }
203    };
204}
205unit_disk_mis_spec!(MaximumIndependentSetUnitDiskOneCreateSpec, One, One);
206unit_disk_mis_spec!(
207    MaximumIndependentSetUnitDiskI64CreateSpec,
208    i64,
209    1_i64,
210    weights
211);
212
213impl<G: Graph, W: Clone + Default> MaximumIndependentSet<G, W> {
214    /// Create an Independent Set problem from a graph with given weights.
215    pub fn new(graph: G, weights: Vec<W>) -> Self {
216        Self::try_new(graph, weights).unwrap_or_else(|error| panic!("{error}"))
217    }
218
219    fn try_new(graph: G, weights: Vec<W>) -> Result<Self, crate::registry::ConstructionError> {
220        if weights.len() != graph.num_vertices() {
221            return Err(crate::registry::ConstructionError::length_mismatch(
222                "weights",
223                weights.len(),
224                graph.num_vertices(),
225            ));
226        }
227        Ok(Self { graph, weights })
228    }
229
230    /// Get a reference to the underlying graph.
231    pub fn graph(&self) -> &G {
232        &self.graph
233    }
234
235    /// Get a reference to the weights.
236    pub fn weights(&self) -> &[W] {
237        &self.weights
238    }
239
240    /// Check if the problem uses a non-unit weight type.
241    pub fn is_weighted(&self) -> bool
242    where
243        W: WeightElement,
244    {
245        !W::IS_UNIT
246    }
247
248    /// Check if a configuration is a valid independent set.
249    pub fn is_valid_solution(&self, config: &[bool]) -> bool {
250        is_independent_set_config(&self.graph, config)
251    }
252}
253
254impl<G: Graph, W: WeightElement> MaximumIndependentSet<G, W> {
255    /// Get the number of vertices in the underlying graph.
256    pub fn num_vertices(&self) -> usize {
257        self.graph().num_vertices()
258    }
259
260    /// Get the number of edges in the underlying graph.
261    pub fn num_edges(&self) -> usize {
262        self.graph().num_edges()
263    }
264}
265
266impl<G, W> Problem for MaximumIndependentSet<G, W>
267where
268    G: Graph + crate::variant::VariantParam,
269    W: WeightElement + crate::variant::VariantParam,
270{
271    const NAME: &'static str = "MaximumIndependentSet";
272    type Solution = Vec<bool>;
273    type Value = Max<W::Sum>;
274
275    crate::problem_parameters![("num_edges", num_edges), ("num_vertices", num_vertices),];
276
277    fn variant() -> Vec<(&'static str, &'static str)> {
278        crate::variant_params![G, W]
279    }
280
281    fn evaluate(
282        &self,
283        solution: &Self::Solution,
284    ) -> Result<Max<W::Sum>, crate::traits::EvaluationError> {
285        Ok({
286            if solution.len() != self.graph.num_vertices() {
287                return Err(crate::traits::EvaluationError::InvalidConfiguration(
288                    format!(
289                        "solution has {} variables, expected {}",
290                        solution.len(),
291                        self.graph.num_vertices()
292                    ),
293                ));
294            }
295            if !is_independent_set_config(&self.graph, solution) {
296                return Ok(Max(None));
297            }
298            let mut total = W::Sum::zero();
299            for (i, &selected) in solution.iter().enumerate() {
300                if selected {
301                    total = W::checked_add_to_sum(
302                        total,
303                        self.weights[i].to_sum(),
304                        "summing selected independent-set weights",
305                    )?;
306                }
307            }
308            Max(Some(total))
309        })
310    }
311}
312
313impl<G, W> crate::solvers::BruteForceProblem for MaximumIndependentSet<G, W>
314where
315    G: Graph + crate::variant::VariantParam,
316    W: WeightElement + crate::variant::VariantParam,
317{
318    fn dimensions(&self) -> Vec<usize> {
319        vec![2; self.graph.num_vertices()]
320    }
321}
322
323/// Check if a configuration forms a valid independent set.
324fn is_independent_set_config<G: Graph>(graph: &G, config: &[bool]) -> bool {
325    for (u, v) in graph.edges() {
326        if config.get(u).copied().unwrap_or(false) && config.get(v).copied().unwrap_or(false) {
327            return false;
328        }
329    }
330    true
331}
332
333crate::impl_random_generate!(MaximumIndependentSet<SimpleGraph, i64>, crate::random::SimpleGraphRandomSpec, |spec| {
334    Ok(MaximumIndependentSet::new(spec.graph()?, vec![1; spec.num_vertices]))
335});
336crate::impl_random_generate!(MaximumIndependentSet<SimpleGraph, One>, crate::random::SimpleGraphRandomSpec, |spec| {
337    Ok(MaximumIndependentSet::new(spec.graph()?, vec![One; spec.num_vertices]))
338});
339crate::impl_random_generate!(MaximumIndependentSet<KingsSubgraph, i64>, crate::random::IntegerGeometryRandomSpec, |spec| {
340    let seed = crate::random::seed_to_u64(spec.seed)?;
341    Ok(MaximumIndependentSet::new(KingsSubgraph::new(crate::random::create_random_int_positions(spec.num_vertices, seed)), vec![1; spec.num_vertices]))
342});
343crate::impl_random_generate!(MaximumIndependentSet<KingsSubgraph, One>, crate::random::IntegerGeometryRandomSpec, |spec| {
344    let seed = crate::random::seed_to_u64(spec.seed)?;
345    Ok(MaximumIndependentSet::new(KingsSubgraph::new(crate::random::create_random_int_positions(spec.num_vertices, seed)), vec![One; spec.num_vertices]))
346});
347crate::impl_random_generate!(MaximumIndependentSet<TriangularSubgraph, i64>, crate::random::IntegerGeometryRandomSpec, |spec| {
348    let seed = crate::random::seed_to_u64(spec.seed)?;
349    Ok(MaximumIndependentSet::new(TriangularSubgraph::new(crate::random::create_random_int_positions(spec.num_vertices, seed)), vec![1; spec.num_vertices]))
350});
351crate::impl_random_generate!(MaximumIndependentSet<UnitDiskGraph, i64>, crate::random::UnitDiskRandomSpec, |spec| {
352    let seed = crate::random::seed_to_u64(spec.seed)?;
353    Ok(MaximumIndependentSet::new(UnitDiskGraph::new(crate::random::create_random_float_positions(spec.num_vertices, seed), spec.radius.unwrap_or(1.0))?, vec![1; spec.num_vertices]))
354});
355crate::impl_random_generate!(MaximumIndependentSet<UnitDiskGraph, One>, crate::random::UnitDiskRandomSpec, |spec| {
356    let seed = crate::random::seed_to_u64(spec.seed)?;
357    Ok(MaximumIndependentSet::new(UnitDiskGraph::new(crate::random::create_random_float_positions(spec.num_vertices, seed), spec.radius.unwrap_or(1.0))?, vec![One; spec.num_vertices]))
358});
359
360crate::declare_variants! {
361    MaximumIndependentSet<SimpleGraph, i64> => "1.1996^num_vertices" create MaximumIndependentSetSimpleI64CreateSpec random,
362    default MaximumIndependentSet<SimpleGraph, One> => "1.1996^num_vertices" create MaximumIndependentSetSimpleOneCreateSpec random,
363    MaximumIndependentSet<KingsSubgraph, i64> => "2^sqrt(num_vertices)" create MaximumIndependentSetKingsI64CreateSpec random,
364    MaximumIndependentSet<KingsSubgraph, One> => "2^sqrt(num_vertices)" create MaximumIndependentSetKingsOneCreateSpec random,
365    MaximumIndependentSet<TriangularSubgraph, i64> => "2^sqrt(num_vertices)" create MaximumIndependentSetTriangularI64CreateSpec random,
366    MaximumIndependentSet<UnitDiskGraph, i64> => "2^sqrt(num_vertices)" create MaximumIndependentSetUnitDiskI64CreateSpec random,
367    MaximumIndependentSet<UnitDiskGraph, One> => "2^sqrt(num_vertices)" create MaximumIndependentSetUnitDiskOneCreateSpec random,
368    MaximumIndependentSet<SimpleGraph, f64> => "2^num_vertices" create MaximumIndependentSetSimpleF64CreateSpec,
369}
370
371crate::register_brute_force! {
372    MaximumIndependentSet<SimpleGraph, i64> decode |_, indices: Vec<usize>| crate::config::config_to_bits(&indices),
373    MaximumIndependentSet<SimpleGraph, One> decode |_, indices: Vec<usize>| crate::config::config_to_bits(&indices),
374    MaximumIndependentSet<KingsSubgraph, i64> decode |_, indices: Vec<usize>| crate::config::config_to_bits(&indices),
375    MaximumIndependentSet<KingsSubgraph, One> decode |_, indices: Vec<usize>| crate::config::config_to_bits(&indices),
376    MaximumIndependentSet<TriangularSubgraph, i64> decode |_, indices: Vec<usize>| crate::config::config_to_bits(&indices),
377    MaximumIndependentSet<UnitDiskGraph, i64> decode |_, indices: Vec<usize>| crate::config::config_to_bits(&indices),
378    MaximumIndependentSet<UnitDiskGraph, One> decode |_, indices: Vec<usize>| crate::config::config_to_bits(&indices),
379    MaximumIndependentSet<SimpleGraph, f64> decode |_, indices: Vec<usize>| crate::config::config_to_bits(&indices),
380}
381
382impl<G, W> crate::models::decision::DecisionProblemMeta for MaximumIndependentSet<G, W>
383where
384    G: Graph + crate::variant::VariantParam,
385    W: WeightElement + crate::variant::VariantParam,
386    W::Sum: std::fmt::Debug + serde::Serialize + serde::de::DeserializeOwned,
387{
388    const DECISION_NAME: &'static str = "DecisionMaximumIndependentSet";
389}
390
391impl<W> crate::models::decision::Decision<MaximumIndependentSet<SimpleGraph, W>>
392where
393    W: WeightElement + crate::variant::VariantParam,
394    W::Sum: std::fmt::Debug + serde::Serialize + serde::de::DeserializeOwned,
395{
396    pub fn num_vertices(&self) -> usize {
397        self.inner().num_vertices()
398    }
399
400    pub fn num_edges(&self) -> usize {
401        self.inner().num_edges()
402    }
403}
404
405crate::register_decision_variant!(
406    MaximumIndependentSet<SimpleGraph, i64>,
407    "DecisionMaximumIndependentSet",
408    "1.1996^num_vertices",
409    &["DMIS", "IndependentSet"],
410    "Decision version: does an independent set of weight at least the bound exist?",
411    category: crate::registry::ProblemCategory::Graph,
412    dims: [
413        VariantDimension::new("graph", "SimpleGraph", &["SimpleGraph"]),
414        VariantDimension::new("weight", "i64", &["i64", "One"]),
415    ],
416    fields: [
417        FieldInfo { name: "graph", type_name: "G", description: "The underlying graph G=(V,E)" },
418        FieldInfo { name: "weights", type_name: "Vec<W>", description: "Vertex weights w: V -> R" },
419        FieldInfo { name: "bound", type_name: "W::Sum", description: "Decision bound (minimum required independent-set weight)" },
420    ],
421    additional: [MaximumIndependentSet<SimpleGraph, One> => "1.1996^num_vertices"],
422    decode: |_, indices: Vec<usize>| crate::config::config_to_bits(&indices)
423);
424
425#[cfg(feature = "example-db")]
426pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
427    vec![
428        crate::example_db::specs::ModelExampleSpec {
429            id: "maximum_independent_set_petersen_graph",
430            instance: Box::new(MaximumIndependentSet::new(
431                SimpleGraph::new(
432                    10,
433                    vec![
434                        (0, 1),
435                        (1, 2),
436                        (2, 3),
437                        (3, 4),
438                        (4, 0),
439                        (5, 7),
440                        (7, 9),
441                        (9, 6),
442                        (6, 8),
443                        (8, 5),
444                        (0, 5),
445                        (1, 6),
446                        (2, 7),
447                        (3, 8),
448                        (4, 9),
449                    ],
450                ),
451                vec![One; 10],
452            )),
453            optimal_config: serde_json::json!(vec![
454                true, false, true, false, false, false, false, false, true, true
455            ]),
456            optimal_value: serde_json::json!(4),
457        },
458        crate::example_db::specs::ModelExampleSpec {
459            id: "maximum_independent_set_simplegraph",
460            instance: Box::new(MaximumIndependentSet::new(
461                SimpleGraph::new(
462                    10,
463                    vec![
464                        (0, 1),
465                        (1, 2),
466                        (2, 3),
467                        (3, 4),
468                        (4, 0),
469                        (5, 7),
470                        (7, 9),
471                        (9, 6),
472                        (6, 8),
473                        (8, 5),
474                        (0, 5),
475                        (1, 6),
476                        (2, 7),
477                        (3, 8),
478                        (4, 9),
479                    ],
480                ),
481                vec![5, 1, 1, 1, 1, 3, 1, 1, 1, 3],
482            )),
483            optimal_config: serde_json::json!(vec![
484                true, false, true, false, false, false, false, false, true, true
485            ]),
486            optimal_value: serde_json::json!(10),
487        },
488    ]
489}
490
491#[cfg(feature = "example-db")]
492pub(crate) fn decision_canonical_model_example_specs(
493) -> Vec<crate::example_db::specs::ModelExampleSpec> {
494    vec![
495        crate::example_db::specs::ModelExampleSpec {
496            id: "decision_maximum_independent_set_simplegraph",
497            instance: Box::new(crate::models::decision::Decision::new(
498                MaximumIndependentSet::new(SimpleGraph::path(4), vec![1i64; 4]),
499                2,
500            )),
501            optimal_config: serde_json::json!(vec![true, false, true, false]),
502            optimal_value: serde_json::json!(true),
503        },
504        crate::example_db::specs::ModelExampleSpec {
505            id: "decision_maximum_independent_set_unit",
506            instance: Box::new(crate::models::decision::Decision::new(
507                MaximumIndependentSet::new(SimpleGraph::path(3), vec![One; 3]),
508                2,
509            )),
510            optimal_config: serde_json::json!(vec![true, false, true]),
511            optimal_value: serde_json::json!(true),
512        },
513    ]
514}
515
516#[cfg(feature = "example-db")]
517pub(crate) fn decision_canonical_rule_example_specs(
518) -> Vec<crate::example_db::specs::RuleExampleSpec> {
519    use crate::example_db::specs::{rule_example_with_witness, RuleExampleSpec};
520    use crate::export::SolutionPair;
521    use crate::models::decision::Decision;
522    vec![
523        RuleExampleSpec {
524            id: "decision_maximum_independent_set_to_maximum_independent_set",
525            build: || {
526                let source = Decision::new(
527                    MaximumIndependentSet::new(SimpleGraph::path(4), vec![1i64; 4]),
528                    2,
529                );
530                rule_example_with_witness::<_, MaximumIndependentSet<SimpleGraph, i64>>(
531                    source,
532                    SolutionPair {
533                        source_config: serde_json::json!([true, false, true, false]),
534                        target_config: serde_json::json!([true, false, true, false]),
535                    },
536                )
537            },
538        },
539        RuleExampleSpec {
540            id: "decision_maximum_independent_set_unit_to_maximum_independent_set",
541            build: || {
542                let source = Decision::new(
543                    MaximumIndependentSet::new(SimpleGraph::path(3), vec![One; 3]),
544                    2,
545                );
546                rule_example_with_witness::<_, MaximumIndependentSet<SimpleGraph, One>>(
547                    source,
548                    SolutionPair {
549                        source_config: serde_json::json!([true, false, true]),
550                        target_config: serde_json::json!([true, false, true]),
551                    },
552                )
553            },
554        },
555    ]
556}
557
558/// Check if a set of vertices forms an independent set.
559///
560/// # Arguments
561/// * `graph` - The graph
562/// * `selected` - Boolean slice indicating which vertices are selected
563///
564/// # Panics
565/// Panics if `selected.len() != graph.num_vertices()`.
566#[cfg(test)]
567pub(crate) fn is_independent_set<G: Graph>(graph: &G, selected: &[bool]) -> bool {
568    assert_eq!(
569        selected.len(),
570        graph.num_vertices(),
571        "selected length must match num_vertices"
572    );
573    for (u, v) in graph.edges() {
574        if selected[u] && selected[v] {
575            return false;
576        }
577    }
578    true
579}
580
581#[cfg(test)]
582#[path = "../../unit_tests/models/graph/maximum_independent_set.rs"]
583mod tests;
problemreductions/models/graph/maximum_independent_set.rs

problemreductions/models/graph/
maximum_independent_set.rs
