Weighted independent sets
Lax263307.WeightedIndependentSet · concepts/Lax263307/WeightedIndependentSet.lean · lax-263307
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Definition
An instance consists of a finite simple graph and rational vertex weights. A solution is a vertex set together with its ambient number of vertices. The ambient number allows solutions for graphs of different orders to share one type; feasibility requires it to agree with the instance.
An -approximation has weight at least for every independent set . Weights may be negative, and the empty set is always feasible. All definitions here concern mathematical objects, independently of their machine representations.
Concept map
Lean source view on GitHub
| 1 | import Mathlib.Combinatorics.SimpleGraph.Clique |
| 2 | import Mathlib.Data.Rat.Floor |
| 3 | |
| 4 | /-! |
| 5 | --- |
| 6 | title: Weighted independent sets |
| 7 | type: definition |
| 8 | --- |
| 9 | An instance consists of a finite simple graph and rational vertex weights. |
| 10 | A solution is a vertex set together with its ambient number of vertices. |
| 11 | The ambient number allows solutions for graphs of different orders to share |
| 12 | one type; feasibility requires it to agree with the instance. |
| 13 | |
| 14 | An -approximation has weight at least |
| 15 | for every independent set . |
| 16 | Weights may be negative, and the empty set is always feasible. |
| 17 | All definitions here concern mathematical objects, independently of their |
| 18 | machine representations. |
| 19 | -/ |
| 20 | |
| 21 | namespace Lax263307.WeightedIndependentSet |
| 22 | |
| 23 | /-- A finite graph with rational vertex weights. -/ |
| 24 | structure Instance where |
| 25 | order : ℕ |
| 26 | graph : SimpleGraph (Fin order) |
| 27 | weights : Fin order → ℚ |
| 28 | |
| 29 | /-- A vertex set in an explicitly specified finite ambient set. -/ |
| 30 | abbrev Solution := (n : ℕ) × Finset (Fin n) |
| 31 | |
| 32 | /-- Total weight of a vertex set. -/ |
| 33 | def weight {n : ℕ} (w : Fin n → ℚ) (I : Finset (Fin n)) : ℚ := |
| 34 | ∑ v ∈ I, w v |
| 35 | |
| 36 | /-- An independent set that achieves the requested multiplicative guarantee. -/ |
| 37 | def IsApproximation {n : ℕ} (G : SimpleGraph (Fin n)) (w : Fin n → ℚ) |
| 38 | (ε : ℚ) (I : Finset (Fin n)) : Prop := |
| 39 | G.IsIndepSet (I : Set (Fin n)) ∧ |
| 40 | ∀ J : Finset (Fin n), G.IsIndepSet (J : Set (Fin n)) → |
| 41 | (1 - ε) * weight w J ≤ weight w I |
| 42 | |
| 43 | end Lax263307.WeightedIndependentSet |
| 44 |
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments