minimum_violation_problem (489B)
1 # Minimum violation problem 2 3 Having fixed a template graph H, given a [weighted_graph] G, the *minimum violation problem* asks us to find a vertex map from G to H which is [surjective] and minimizes the weight of edges whose image is not an edge of H (i.e., which witness that the map is not a homomorphism) 4 - can be studied with fixed edges, i.e., which cannot be removed 5 6 Studied in [kawarabayashi2020minimum] 7 8 Connections to [max_csp] 9 10 Up: [computational_problem], [graph_homomorphism]