problemreductions/models/graph/
kernel.rs

1//! Kernel problem implementation.
2//!
3//! The Kernel problem asks whether a directed graph contains a kernel, i.e.,
4//! a subset of vertices that is both independent (no arc between any two
5//! selected vertices) and absorbing (every unselected vertex has an arc to
6//! some selected vertex).
7
8use crate::registry::{FieldInfo, ProblemSchemaEntry, VariantDimension};
9use crate::topology::DirectedGraph;
10use crate::traits::Problem;
11use serde::{Deserialize, Serialize};
12
13inventory::submit! {
14    ProblemSchemaEntry {
15        name: "Kernel",
16        display_name: "Kernel",
17        aliases: &[],
18        dimensions: &[
19            VariantDimension::new("graph", "DirectedGraph", &["DirectedGraph"]),
20        ],
21        module_path: module_path!(),
22        description: "Does the directed graph contain a kernel (independent and absorbing vertex subset)?",
23        fields: &[
24            FieldInfo { name: "graph", type_name: "DirectedGraph", description: "The directed graph G=(V,A)" },
25        ],
26    }
27}
28
29/// The Kernel problem.
30///
31/// Given a directed graph G = (V, A), find a kernel V' ⊆ V such that:
32/// 1. **Independence:** no two vertices in V' are joined by an arc (neither
33///    (u,v) nor (v,u) is in A for any u,v ∈ V').
34/// 2. **Absorption:** every vertex u ∉ V' has an arc to some vertex v ∈ V'
35///    (i.e., (u,v) ∈ A).
36///
37/// # Representation
38///
39/// A configuration is a binary vector of length |V|, where `config[v] = 1`
40/// means vertex v is selected into V'.
41///
42/// # Example
43///
44/// ```
45/// use problemreductions::models::graph::Kernel;
46/// use problemreductions::topology::DirectedGraph;
47/// use problemreductions::{Problem, Solver, BruteForce};
48///
49/// let graph = DirectedGraph::new(5, vec![
50///     (0,1),(0,2),(1,3),(2,3),(3,4),(4,0),(4,1),
51/// ]);
52/// let problem = Kernel::new(graph);
53/// let solver = BruteForce::new();
54/// let solution = solver.find_witness(&problem);
55/// assert!(solution.is_some());
56/// ```
57#[derive(Debug, Clone, Serialize, Deserialize)]
58pub struct Kernel {
59    graph: DirectedGraph,
60}
61
62impl Kernel {
63    /// Create a new Kernel problem from a directed graph.
64    pub fn new(graph: DirectedGraph) -> Self {
65        Self { graph }
66    }
67
68    /// Get a reference to the underlying directed graph.
69    pub fn graph(&self) -> &DirectedGraph {
70        &self.graph
71    }
72
73    /// Get the number of vertices in the directed graph.
74    pub fn num_vertices(&self) -> usize {
75        self.graph.num_vertices()
76    }
77
78    /// Get the number of arcs in the directed graph.
79    pub fn num_arcs(&self) -> usize {
80        self.graph.num_arcs()
81    }
82}
83
84impl Problem for Kernel {
85    const NAME: &'static str = "Kernel";
86    type Value = crate::types::Or;
87
88    fn variant() -> Vec<(&'static str, &'static str)> {
89        crate::variant_params![]
90    }
91
92    fn dims(&self) -> Vec<usize> {
93        vec![2; self.graph.num_vertices()]
94    }
95
96    fn evaluate(&self, config: &[usize]) -> crate::types::Or {
97        let n = self.graph.num_vertices();
98
99        // Collect selected vertices
100        let selected: Vec<bool> = config.iter().map(|&c| c == 1).collect();
101
102        // Independence: no arc between any two selected vertices
103        for u in 0..n {
104            if !selected[u] {
105                continue;
106            }
107            // Check that no successor of u is also selected
108            for &v in &self.graph.successors(u) {
109                if selected[v] {
110                    return crate::types::Or(false);
111                }
112            }
113        }
114
115        // Absorption: every unselected vertex must have an arc to some selected vertex
116        for u in 0..n {
117            if selected[u] {
118                continue;
119            }
120            let has_arc_to_selected = self.graph.successors(u).iter().any(|&v| selected[v]);
121            if !has_arc_to_selected {
122                return crate::types::Or(false);
123            }
124        }
125
126        crate::types::Or(true)
127    }
128}
129
130#[cfg(feature = "example-db")]
131pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
132    // 5 vertices, arcs: (0,1),(0,2),(1,3),(2,3),(3,4),(4,0),(4,1)
133    // Kernel: V' = {0, 3} → config [1,0,0,1,0]
134    let graph = DirectedGraph::new(
135        5,
136        vec![(0, 1), (0, 2), (1, 3), (2, 3), (3, 4), (4, 0), (4, 1)],
137    );
138    let optimal_config = vec![1, 0, 0, 1, 0];
139    vec![crate::example_db::specs::ModelExampleSpec {
140        id: "kernel",
141        instance: Box::new(Kernel::new(graph)),
142        optimal_config,
143        optimal_value: serde_json::json!(true),
144    }]
145}
146
147crate::declare_variants! {
148    default Kernel => "2^num_vertices",
149}
150
151#[cfg(test)]
152#[path = "../../unit_tests/models/graph/kernel.rs"]
153mod tests;
problemreductions/models/graph/kernel.rs

problemreductions/models/graph/
kernel.rs
