Independent Set on Adjacency Matrices
Lax496464.WH_F1_IndependentSetMatrix · concepts/Lax496464/WH_F1_IndependentSetMatrix.lean · lax-496464
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Definition
-Independent-Set. Instance: a graph on vertices and . Parameter: . Question: does have an independent set of at least vertices? [FG06, Section 1.2]
This is the source problem of the reduction to Multicoloured Clique in part F.
Concept map
Lean source view on GitHub
| 1 | import Lax762056.GraphProblems |
| 2 | import Lax888481.ParameterizedComplexity |
| 3 | |
| 4 | /-! |
| 5 | --- |
| 6 | title: Independent Set on Adjacency Matrices |
| 7 | type: definition |
| 8 | --- |
| 9 | **-Independent-Set.** *Instance:* a graph on vertices and . |
| 10 | *Parameter:* . *Question:* does have an independent set of at least vertices? |
| 11 | [FG06, Section 1.2] |
| 12 | |
| 13 | This is the source problem of the reduction to Multicoloured Clique in part F. |
| 14 | |
| 15 | # Formalization Notes |
| 16 | |
| 17 | **Instances and question** are those of the archive's Independent Set (`Lax762056.GraphProblems`), |
| 18 | whose NP-hardness is proved there. An instance is written as the bit string |
| 19 | : the order in unary, the entries of the adjacency matrix in row |
| 20 | order, and in unary. |
| 21 | |
| 22 | **Words.** The word of an instance is this bit string with each bit written as the number or |
| 23 | , and the instances are exactly the words of this form. The parameter of a word is the length of |
| 24 | the run of ones that ends just before its last entry; on the word of an instance it is , since |
| 25 | the last matrix entry is a diagonal entry and hence . |
| 26 | |
| 27 | **Relation to `WH_C1_GraphProblems.IndependentSet`.** That problem asks the same question for an |
| 28 | exact solution size, on compressed sparse row words. The two problems differ only in the encoding. |
| 29 | -/ |
| 30 | |
| 31 | namespace Lax496464.WH_F1_IndependentSetMatrix |
| 32 | |
| 33 | open Lax762056.GraphEncoding Lax888481.ParameterizedComplexity |
| 34 | |
| 35 | /-- A bit as a number. -/ |
| 36 | def bitNat (b : Bool) : ℕ := if b then 1 else 0 |
| 37 | |
| 38 | /-- The word of an instance: its adjacency-matrix encoding, one number `0` or `1` per bit. -/ |
| 39 | noncomputable def word (I : Instance) : List ℕ := (encode I).map bitNat |
| 40 | |
| 41 | /-- The words that present an instance. -/ |
| 42 | def Instances : Set (List ℕ) := Set.range word |
| 43 | |
| 44 | /-- The parameter `k` of a word: the run of ones ending just before its last entry. -/ |
| 45 | def threshold (x : List ℕ) : ℕ := (x.dropLast.reverse.takeWhile fun v => v == 1).length |
| 46 | |
| 47 | /-- **`p-Independent-Set`** on adjacency-matrix words. -/ |
| 48 | def problem : Problem where |
| 49 | Domain := Instances |
| 50 | Yes x := ∃ I, x = word I ∧ Lax762056.GraphProblems.IndependentSet I |
| 51 | param := threshold |
| 52 | |
| 53 | end Lax496464.WH_F1_IndependentSetMatrix |
| 54 |
Formalization Notes
Instances and question are those of the archive's Independent Set (), whose NP-hardness is proved there. An instance is written as the bit string : the order in unary, the entries of the adjacency matrix in row order, and in unary.
Words. The word of an instance is this bit string with each bit written as the number or , and the instances are exactly the words of this form. The parameter of a word is the length of the run of ones that ends just before its last entry; on the word of an instance it is , since the last matrix entry is a diagonal entry and hence .
Relation to . That problem asks the same question for an exact solution size, on compressed sparse row words. The two problems differ only in the encoding.
From Mathlib
none
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments