problemreductions/models/graph/
minimum_covering_by_cliques.rs

1//! Minimum Covering by Cliques problem implementation.
2//!
3//! Given a graph G = (V, E), find a minimum number of cliques whose union
4//! covers every edge in E.
5
6use crate::registry::{FieldInfo, ProblemSchemaEntry, VariantDimension};
7use crate::topology::{Graph, SimpleGraph};
8use crate::traits::Problem;
9use crate::types::Min;
10use serde::{Deserialize, Serialize};
11use std::collections::HashSet;
12
13inventory::submit! {
14    ProblemSchemaEntry {
15        name: "MinimumCoveringByCliques",
16        display_name: "Minimum Covering by Cliques",
17        aliases: &[],
18        dimensions: &[
19            VariantDimension::new("graph", "SimpleGraph", &["SimpleGraph"]),
20        ],
21        category: crate::registry::ProblemCategory::Graph,
22        module_path: module_path!(),
23        description: "Find minimum number of cliques covering all edges",
24        fields: &[
25            FieldInfo { name: "graph", type_name: "G", description: "The underlying graph G=(V,E)" },
26        ],
27    }
28}
29
30/// The Minimum Covering by Cliques problem.
31///
32/// Given a graph G = (V, E), find a collection of cliques C_1, ..., C_k
33/// in G such that every edge is contained in at least one clique,
34/// and k is minimized.
35///
36/// Variables: one per edge, each selecting which clique group covers it.
37/// Each edge can be assigned to one of at most |E| groups (upper bound).
38///
39/// # Type Parameters
40///
41/// * `G` - The graph type (e.g., `SimpleGraph`)
42///
43/// # Example
44///
45/// ```
46/// use problemreductions::models::graph::MinimumCoveringByCliques;
47/// use problemreductions::topology::SimpleGraph;
48/// use problemreductions::{Problem, BruteForce};
49///
50/// // Triangle: 3 edges can be covered by 1 clique
51/// let graph = SimpleGraph::new(3, vec![(0, 1), (1, 2), (0, 2)]);
52/// let problem = MinimumCoveringByCliques::new(graph);
53///
54/// let solver = BruteForce::new();
55/// let solution = solver.solve(&problem).unwrap().unwrap();
56/// let value = problem.evaluate(&solution).unwrap();
57/// assert_eq!(value, problemreductions::types::Min(Some(1)));
58/// ```
59#[derive(Debug, Clone, Serialize, Deserialize)]
60pub struct MinimumCoveringByCliques<G> {
61    /// The underlying graph.
62    graph: G,
63}
64
65impl<G: Graph> MinimumCoveringByCliques<G> {
66    /// Create a MinimumCoveringByCliques problem from a graph.
67    pub fn new(graph: G) -> Self {
68        Self { graph }
69    }
70
71    /// Get a reference to the underlying graph.
72    pub fn graph(&self) -> &G {
73        &self.graph
74    }
75
76    /// Get the number of vertices in the underlying graph.
77    pub fn num_vertices(&self) -> usize {
78        self.graph.num_vertices()
79    }
80
81    /// Get the number of edges in the underlying graph.
82    pub fn num_edges(&self) -> usize {
83        self.graph.num_edges()
84    }
85
86    /// Check whether a configuration is a valid edge clique cover.
87    ///
88    /// For each group index used, the edges assigned to it must form a clique:
89    /// all vertices touched by those edges must be pairwise adjacent.
90    pub fn is_valid_cover(&self, config: &[usize]) -> bool {
91        let edges = self.graph.edges();
92        let num_edges = edges.len();
93
94        if config.len() != num_edges {
95            return false;
96        }
97
98        // Group edges by their assigned clique in a single pass.
99        let max_group = match config.iter().max() {
100            Some(&m) => m,
101            None => return true, // no edges → trivially valid
102        };
103
104        let mut groups: Vec<HashSet<usize>> = vec![HashSet::new(); max_group + 1];
105        for (idx, &group) in config.iter().enumerate() {
106            let (u, v) = edges[idx];
107            groups[group].insert(u);
108            groups[group].insert(v);
109        }
110
111        // Check that each group's vertices form a clique.
112        for vertices in &groups {
113            let verts: Vec<usize> = vertices.iter().copied().collect();
114            for i in 0..verts.len() {
115                for j in (i + 1)..verts.len() {
116                    if !self.graph.has_edge(verts[i], verts[j]) {
117                        return false;
118                    }
119                }
120            }
121        }
122
123        true
124    }
125}
126
127impl<G> Problem for MinimumCoveringByCliques<G>
128where
129    G: Graph + crate::variant::VariantParam,
130{
131    const NAME: &'static str = "MinimumCoveringByCliques";
132    type Solution = Vec<usize>;
133    type Value = Min<i64>;
134
135    crate::problem_parameters![("num_edges", num_edges), ("num_vertices", num_vertices),];
136
137    fn variant() -> Vec<(&'static str, &'static str)> {
138        crate::variant_params![G]
139    }
140
141    fn evaluate(
142        &self,
143        config: &Self::Solution,
144    ) -> Result<Min<i64>, crate::traits::EvaluationError> {
145        Ok({
146            if config.len() != self.graph.num_edges() {
147                return Err(crate::traits::EvaluationError::InvalidConfiguration(
148                    "edge-group assignment length does not match the graph edges".into(),
149                ));
150            }
151            if self.graph.num_edges() == 0 {
152                return Ok(Min(Some(0)));
153            }
154            if !self.is_valid_cover(config) {
155                return Ok(Min(None));
156            }
157            let distinct_groups: HashSet<usize> = config.iter().copied().collect();
158            Min(Some(i64::try_from(distinct_groups.len()).map_err(
159                |_| {
160                    crate::traits::EvaluationError::IntegerOverflow(
161                        "converting clique-cover size to i64".into(),
162                    )
163                },
164            )?))
165        })
166    }
167}
168
169impl<G> crate::solvers::BruteForceProblem for MinimumCoveringByCliques<G>
170where
171    G: Graph + crate::variant::VariantParam,
172{
173    fn dimensions(&self) -> Vec<usize> {
174        vec![self.graph.num_edges(); self.graph.num_edges()]
175    }
176}
177
178crate::impl_random_generate!(
179    MinimumCoveringByCliques<SimpleGraph>,
180    crate::random::SimpleGraphRandomSpec,
181    |spec| { Ok(MinimumCoveringByCliques::new(spec.graph()?)) }
182);
183
184crate::declare_variants! {
185    default MinimumCoveringByCliques<SimpleGraph> => "2^num_edges" random,
186}
187
188crate::register_brute_force! {
189    MinimumCoveringByCliques<SimpleGraph>,
190}
191
192#[cfg(feature = "example-db")]
193pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
194    // 6 vertices, 9 edges:
195    // (0,1),(1,2),(2,3),(3,0),(0,2),(4,0),(4,1),(5,2),(5,3)
196    // Optimal: 4 cliques
197    // edges 0,1,4 -> group 0 (clique {0,1,2})
198    // edges 2,3 -> group 1 (clique {0,2,3}... wait, (2,3) and (3,0) -> vertices {0,2,3})
199    // edges 5,6 -> group 2 (clique {0,1,4})
200    // edges 7,8 -> group 3 (clique {2,3,5})
201    // Config: [0, 0, 1, 1, 0, 2, 2, 3, 3]
202    vec![crate::example_db::specs::ModelExampleSpec {
203        id: "minimum_covering_by_cliques_simplegraph",
204        instance: Box::new(MinimumCoveringByCliques::new(SimpleGraph::new(
205            6,
206            vec![
207                (0, 1),
208                (1, 2),
209                (2, 3),
210                (3, 0),
211                (0, 2),
212                (4, 0),
213                (4, 1),
214                (5, 2),
215                (5, 3),
216            ],
217        ))),
218        optimal_config: serde_json::json!(vec![0, 0, 1, 1, 0, 2, 2, 3, 3]),
219        optimal_value: serde_json::json!(4),
220    }]
221}
222
223#[cfg(test)]
224#[path = "../../unit_tests/models/graph/minimum_covering_by_cliques.rs"]
225mod tests;
problemreductions/models/graph/minimum_covering_by_cliques.rs

problemreductions/models/graph/
minimum_covering_by_cliques.rs
