Independent Set on Adjacency Matrices

Lax496464.WH_F1_IndependentSetMatrix · concepts/Lax496464/WH_F1_IndependentSetMatrix.lean · lax-496464

definition

Loading review…

Sign in with ORCID

Community review

Flags

Each flag is tied to a public ORCID identity and explains why this concept may be incorrect.

No flags have been submitted.

    Community review

    Flag this concept

    State precisely what appears incorrect. This explanation will be public under your ORCID name.

    No source line selected.

    Natural Language Statement

    Definition

    pp-Independent-Set. Instance: a graph GG on nn vertices and k∈Nk \in \mathbb N. Parameter: kk. Question: does GG have an independent set of at least kk vertices? [FG06, Section 1.2]

    This is the source problem of the reduction to Multicoloured Clique in part F.

    Concept map
    10 concepts; 3 descendants hidden
    100%
    Proven claimDefinitionThis conceptRelated conceptA → B: B builds on A

    Lean source view on GitHub

    1import Lax762056.GraphProblems
    2import Lax888481.ParameterizedComplexity
    3
    4/-!
    5---
    6title: Independent Set on Adjacency Matrices
    7type: definition
    8---
    9**pp-Independent-Set.** *Instance:* a graph GG on nn vertices and k∈Nk \in \mathbb N.
    10*Parameter:* kk. *Question:* does GG have an independent set of at least kk vertices?
    11[FG06, Section 1.2]
    12
    13This 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`),
    18whose NP-hardness is proved there. An instance is written as the bit string
    191n 0 A 1k 01^n\,0\,A\,1^k\,0: the order nn in unary, the n2n^2 entries of the adjacency matrix AA in row
    20order, and kk in unary.
    21
    22**Words.** The word of an instance is this bit string with each bit written as the number 00 or
    2311, and the instances are exactly the words of this form. The parameter of a word is the length of
    24the run of ones that ends just before its last entry; on the word of an instance it is kk, since
    25the last matrix entry is a diagonal entry and hence 00.
    26
    27**Relation to `WH_C1_GraphProblems.IndependentSet`.** That problem asks the same question for an
    28exact solution size, on compressed sparse row words. The two problems differ only in the encoding.
    29-/
    30
    31namespace Lax496464.WH_F1_IndependentSetMatrix
    32
    33open Lax762056.GraphEncoding Lax888481.ParameterizedComplexity
    34
    35/-- A bit as a number. -/
    36def 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. -/
    39noncomputable def word (I : Instance) : List ℕ := (encode I).map bitNat
    40
    41/-- The words that present an instance. -/
    42def Instances : Set (List ℕ) := Set.range word
    43
    44/-- The parameter `k` of a word: the run of ones ending just before its last entry. -/
    45def threshold (x : List ℕ) : ℕ := (x.dropLast.reverse.takeWhile fun v => v == 1).length
    46
    47/-- **`p-Independent-Set`** on adjacency-matrix words. -/
    48def problem : Problem where
    49 Domain := Instances
    50 Yes x := ∃ I, x = word I ∧ Lax762056.GraphProblems.IndependentSet I
    51 param := threshold
    52
    53end Lax496464.WH_F1_IndependentSetMatrix
    54
    Formalization Notes

    Instances and question are those of the archive's Independent Set (Lax762056.GraphProblemsLax762056.GraphProblems), whose NP-hardness is proved there. An instance is written as the bit string 1n 0 A 1k 01^n\,0\,A\,1^k\,0: the order nn in unary, the n2n^2 entries of the adjacency matrix AA in row order, and kk in unary.

    Words. The word of an instance is this bit string with each bit written as the number 00 or 11, 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 kk, since the last matrix entry is a diagonal entry and hence 00.

    Relation to WHC1GraphProblems.IndependentSetWH_C1_GraphProblems.IndependentSet. That problem asks the same question for an exact solution size, on compressed sparse row words. The two problems differ only in the encoding.

    Discussion

    Ask a question or add context. Endorsements and structured flags are kept in the review panel above.

    Loading discussion…