Search algorithms with mappings/functions/sets as variables

Question

I apologize in advance if this sounds vague but I am trying to find directions as to what to look for.

All the sets in this problem are finite. Suppose we have two functions $f_1\colon X_1\times Y_1\to X_1$ and $f_2\colon X_2\times Y_2\to X_2$.

Problem. Decide whether there exist two surjective mappings $p\colon X_2\to X_1$ and $q\colon Y_2\to Y_1$ satisfying the condition $$ \forall x\in X_2, y\in Y_2 : p(f_2(x,y))= f_1(p(x), q(y)) $$

I looked into set-valued optimization and combinatorial set theory but it all seemed too complex for my problem. I have just started reading Kuratowski and Aubin's books. It looks like most optimization problems are formulated using differential inclusion one way or the other and that doesn't seem to be feasible in my case. To me it looks like a typical search problem, I am just not sure how to properly pose it using sets/mappings as variables. Any advice would be super helpful. I am looking into developing an algorithm that proves the existence of the mappings in polynomial time.

Answer 1

You can solve the problem via integer linear programming as follows. Let binary decision variables $P(x_2,x_1)$ and $Q(y_2,y_1)$ indicate whether $p(x_2)=x_1$ and $q(y_2)=y_1$, respectively. The constraints are: \begin{align} \sum_{x_1 \in X_1} P(x_2,x_1) &= 1 &&\text{for $x_2 \in X_2$} \tag1 \\ \sum_{y_1 \in Y_1} Q(y_2,y_1) &= 1 &&\text{for $y_2 \in Y_2$} \tag2 \\ \sum_{x_2 \in X_2} P(x_2,x_1) &\ge 1 &&\text{for $x_1 \in X_1$} \tag3 \\ \sum_{y_2 \in Y_2} Q(y_2,y_1) &\ge 1 &&\text{for $y_1 \in Y_1$} \tag4 \\ P(x,x_1) + Q(y,y_1) - 1 &\le P(f_2(x,y),f_1(x_1, y_1)) &&\text{for $x\in X_2, x_1\in X_1, y\in Y_2, y_1\in Y_1$} \tag5 \end{align} Constraints $(1)$ and $(2)$ enforce that $p$ and $q$ are functions. Constraints $(3)$ and $(4)$ enforce that $p$ and $q$ are surjective. Constraint $(5)$ enforces $$(p(x)=x_1 \land q(y)=y_1) \implies p(f_2(x,y)) = f_1(x_1, y_1)$$