Tomorrow's lecture

For tomorrow, could you brush up what you know Max $k$-ary Consistent Labeling(K,L) from HW1 problem #7 (also defined in the list of problems)? Thanks!

In particular, consider the $2$-ary (also called "binary" case): the constraint hyperedges now become normal edges, and the hypergraph becomes a normal graph. (Note that "strongly" and "weakly" satisfying mean the same thing now.)

Suppose such an instance is a bipartite graph $(U,V,E)$, with $\mid U\mid =\mid V\mid =n$; moreover, the instance is "regular" (i.e., the number of constraints involving each vertex is some $d$). Remind yourself that for such instances, it is NP-hard to infer whether the value is $1$ or less than .