PROBLEM LINKS
DIFFICULTY
MEDIUM
EXPLANATION
This is the standard 3SAT problem where each clause depends on precisely three different variables and each variable appears in at most 3 clauses. Such instances can be solved efficiently. Form a bipartite graph with a node for each clause on one side and a node for each variable on the other. For each clause C, add an edge from the node for C to each of the three nodes corresponding to variables that appear in C. I claim there is a matching in this graph that involves each clause node. Before arguing this, we see that we can then satisfy the instance by assigning, to each matched variable, the value that will satisfy the clause it is matched to. Variables that are unmatched can be assigned anything.
Recall that Hall’s matching theorem states that a bipartite graph with bipartitions X and Y has a matching involving every node in X if and only if each subset X’ of X has at least |X’| neighbors in Y. This is true in our case. Consider a subset C’ of clauses. The number of edges with one endpoint in C’ is precisely 3|C’|. On the other hand, let V’ be the subset of variables that are adjacent to some clause node in C’. Since each variable appears in at most 3 clauses, then the number of edges with one endpoint in V’ is at most 3|V’|. We counted the same set of edges in two different ways which shows |C’| <= |V’|, so by Hall’s theorem there is a matching involving every clause node.
Rajiv, this months tester, has a nice alternative linear-time solution. It solves the slightly more general problem when each group can contain a repeated number, but the total times a number appears is still at most three (e.g. it can appear in at most two groups if it is used twice in some group). It does not generalize as neatly to instances where each group has at least K distinct numbers and each number appears in at most K groups when K is some given number whereas the matching approach does. I’ll sketch the details. Consider a number Z:
i) If Z appears with the same sign in all groups, then assign it the value that will satisfy all of these groups
ii) If Z appears in two different groups with opposite sign, then place it on a “dependency stack” which will be implicitly described in the following. Remove these two groups and form a new group that is the union of the original groups (without Z). This new group will contain at least three numbers. Now, if the resulting instance is solved then using the same assignment will satisfy at least one of the two original groups. Now, fix Z to have the value that will satisfy the other group.
iv) A similar, but messier, rule is used if Z appears in three groups with both Z and -Z appearing in at least one of these groups. I’ll leave the details as an exercise.
A careful implementation of these ideas leads to a linear-time solution.
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.