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

problemreductions/models/graph/
maximum_independent_set.rs
