problemreductions/models/set/
mod.rs

1//! Set-based problems.
2//!
3//! This module contains NP-hard problems based on set operations:
4//! - [`ConsecutiveSets`]: Consecutive arrangement of subset elements in a string
5//! - [`ExactCoverBy3Sets`]: Exact cover by 3-element subsets (X3C)
6//! - [`ComparativeContainment`]: Compare containment-weight sums for two set families
7//! - [`IntegerKnapsack`]: Maximize value with integer multiplicities subject to capacity
8//! - [`MaximumSetPacking`]: Maximum weight set packing
9//! - [`MinimumHittingSet`]: Minimum-size universe subset hitting every set
10//! - [`MinimumSetCovering`]: Minimum weight set cover
11//! - [`PrimeAttributeName`]: Determine if an attribute belongs to any candidate key
12//! - [`RootedTreeStorageAssignment`]: Extend subsets to directed tree paths within a total-cost bound
13//! - [`SetBasis`]: Minimum-cardinality basis generating all sets by union
14//! - [`SetSplitting`]: 2-color universe so every specified subset is non-monochromatic
15//! - [`ThreeDimensionalMatching`]: Perfect matching in a tripartite 3-uniform hypergraph
16//! - [`ThreeMatroidIntersection`]: Common independent set of size K in three partition matroids
17//! - [`TwoDimensionalConsecutiveSets`]: 2D consecutive arrangement of subset elements
18//! - [`MinimumCardinalityKey`]: Smallest attribute set that uniquely identifies tuples
19
20pub(crate) mod comparative_containment;
21pub(crate) mod consecutive_sets;
22pub(crate) mod exact_cover_by_3_sets;
23pub(crate) mod integer_knapsack;
24pub(crate) mod maximum_set_packing;
25pub(crate) mod minimum_cardinality_key;
26pub(crate) mod minimum_hitting_set;
27pub(crate) mod minimum_set_covering;
28pub(crate) mod prime_attribute_name;
29pub(crate) mod rooted_tree_storage_assignment;
30pub(crate) mod set_basis;
31pub(crate) mod set_splitting;
32pub(crate) mod three_dimensional_matching;
33pub(crate) mod three_matroid_intersection;
34pub(crate) mod two_dimensional_consecutive_sets;
35
36pub use comparative_containment::ComparativeContainment;
37pub use consecutive_sets::ConsecutiveSets;
38pub use exact_cover_by_3_sets::ExactCoverBy3Sets;
39pub use integer_knapsack::IntegerKnapsack;
40pub use maximum_set_packing::MaximumSetPacking;
41pub use minimum_cardinality_key::MinimumCardinalityKey;
42pub use minimum_hitting_set::MinimumHittingSet;
43pub use minimum_set_covering::MinimumSetCovering;
44pub use prime_attribute_name::PrimeAttributeName;
45pub use rooted_tree_storage_assignment::RootedTreeStorageAssignment;
46pub use set_basis::SetBasis;
47pub use set_splitting::SetSplitting;
48pub use three_dimensional_matching::ThreeDimensionalMatching;
49pub use three_matroid_intersection::ThreeMatroidIntersection;
50pub use two_dimensional_consecutive_sets::TwoDimensionalConsecutiveSets;
51
52#[cfg(feature = "example-db")]
53pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
54    let mut specs = Vec::new();
55    specs.extend(comparative_containment::canonical_model_example_specs());
56    specs.extend(consecutive_sets::canonical_model_example_specs());
57    specs.extend(exact_cover_by_3_sets::canonical_model_example_specs());
58    specs.extend(integer_knapsack::canonical_model_example_specs());
59    specs.extend(maximum_set_packing::canonical_model_example_specs());
60    specs.extend(minimum_cardinality_key::canonical_model_example_specs());
61    specs.extend(minimum_hitting_set::canonical_model_example_specs());
62    specs.extend(minimum_set_covering::canonical_model_example_specs());
63    specs.extend(prime_attribute_name::canonical_model_example_specs());
64    specs.extend(rooted_tree_storage_assignment::canonical_model_example_specs());
65    specs.extend(set_basis::canonical_model_example_specs());
66    specs.extend(set_splitting::canonical_model_example_specs());
67    specs.extend(three_dimensional_matching::canonical_model_example_specs());
68    specs.extend(three_matroid_intersection::canonical_model_example_specs());
69    specs.extend(two_dimensional_consecutive_sets::canonical_model_example_specs());
70    specs
71}
problemreductions/models/set/mod.rs

problemreductions/models/set/
mod.rs
