wiki_research

personal research wiki
git clone https://a3nm.net/git/wiki_research/
Log | Files | Refs

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]