K-Assignment Search to Decision

Question

Given a set of variables X, and a set of subsets of these variables, each set of size k (each subset includes exactly k variables), we would like to find an assignment 1...k to each variable such that no 2 variables in the same set have the same value assigned to them.

Suppose we are given a Decision Algorithm (as an oracle for a turing/cook reduction), that instantly ( in O(1) ) answers "Yes" whether a given X and a set of subsets of X has such an assignment, and "No" otherwise, can we find an assignment in polynomial time?

Thank you

Answer 1

Your problem is NP-hard since it has a natural reduction from the graph coloring problem. Consider any graph having a minimum degree of $k-1$. Map each vertex as a variable, and for each vertex and its neighbouring $k-1$ vertices, create a subset of variables of size $k$. You can work out the rest of the details.

Answer 2

I found a solution. If the oracle says "Yes" on the original problem, pick some set from the set of sets (call it MASTER). The assignment 1...k to each variable in MASTER works because any solution is an isomorphism to this assignment. Then, go over all the sets of size k, and for each variable in the picked set which is not in MASTER, replace each variable in MASTER with it and call the oracle with the new set of sets. At some point the oracle will answer yes. The assignment to this new variable is the same assignment to the replaced variable! Do this for all sets and we find an assignment. Complexity: O(KxKx(number of sets)).