# Search algorithms with mappings/functions/sets as variables

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.

• When you write, "Show if", do you mean, "Decide whether"? Aug 25, 2020 at 1:47
• Nice question. I have no idea... makes me think of de Morgan's law $\neg(x\land y)=\neg x\lor\neg y$. If $f_2=x\to y$ and $f_1=\vee$ it is possible, if $f_2=y\to x$ and $f_1=\vee$ it's not... but in general there won't be any monotonicity properties like these have. Aug 25, 2020 at 7:14
• @Gerry: Yes, it's edited now. Aug 25, 2020 at 12:09
• @A.Gharbi About tagging, your question chat.stackexchange.com/transcript/message/55678727#55678727 is discussed in the editor's lounge chat.stackexchange.com/transcript/message/55719448#55719448
– YCor
Oct 3, 2020 at 9:58
• If you have $|X_1|=|X_2|$, $|Y_1|=|Y_2|$ and $p,q$ have to be bijections, then this is a graph isomorphism problem. Probably it is isomorphism-complete. I'm not sure about the general case. Oct 3, 2020 at 15:05

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)$$

• What is the objective function here? and would this work even if I don't have the expressions for p and q? Jul 29, 2021 at 15:40
• This is a feasibility problem with no objective function. If your solver requires one, you can use a constant zero objective function. This formulation finds $p$ and $q$ if possible. Jul 29, 2021 at 16:03
• oh I see, ok I'll give it a try and get back to you. Thank you so much for your help Jul 29, 2021 at 16:08
• I am accepting your solution since it is mathematically sound and helped me find a direction. Thank you again :) Aug 5, 2021 at 17:28