min_vertex_cover

std.linalg.min_vertex_cover · Level L4

The size τ(G) of a minimum vertex cover (a set of vertices touching every edge), one such cover, and the number of minimum covers: the complements of the maximum independent sets, so τ(G) = n − α(G), and the minimizers correspond one to one. A smaller cover than a given one is a witness that the given one is not minimum. An inclusion-minimal cover, from which no vertex can be dropped, need not be minimum.

τ(G) = n − α(G)

Signature

min_vertex_cover(A: f64[n, n]) → f64[], f64[n], f64[]

Structure

The function as NOVA stores it: one box per input, operation and output, and arrows that carry values. A double border marks another library function this one runs — called once, or by Scan once per element; select it to open that function.

input
operation
constant
call
output

Verification

Signature proven by NOVA’s shape solver, for every size.
Equal to the reference n − α(G); the complements of the maximum independent sets in exact rational arithmetic, on all 40 test cases.
All 241 float64 results are exact: the error is zero.
Interpreter and NumPy backend return bit-identical results.
At float32 too: the 40 test cases rounded to float32, and 40 of them exact, with zero error.

Accuracy in detail

correctly rounded (the float64 nearest the exact value): 100%
bit-equal to the NumPy formula in float64: 100%
largest error, in units in the last place: 0

Identity

Calls

max_independent_set

Called by

—

sha256:3e1bb98ce1ad608ddda70a29c8b0a738d2130666c81454907869e8c340f9cda8

The semantic hash of the graph. It changes when the program changes, and never when only its documentation does.

Control handle

Symbol: Ω:std.linalg.min_vertex_cover · Ω:min_vertex_cover
Pins: sha256:f13f52c98b2a4552ce56f5dbd0bba1d340e710ac3eca99f8a973ce737aa97747this graph and the 7 it reaches through calls
Evidence: sha256:adb946a6414d75ad03a8c6afbbda406f7a9b1d763452dce568cc66eb718a3043the hash of its verification record
Needs: no capability: a pure function

Through NOVA’s control layer, the symbol launches this function only while the program still matches what it pins: a change to this graph, or to any graph it reaches, needs a migration first.