4
$\begingroup$

Consider the following problem. Given a $m \times n$ integer matrix $A$ and a $p \times q$ integer matrix $B$, do there exist one-to-one functions $$r:\{1,2,...,m\} \rightarrow \{1,2,...,p\}$$ $$c:\{1,2,...,n\} \rightarrow \{1,2,...,q\}$$ where for all $1 \leq i \leq m$ and $1 \leq j \leq n$, $A[i,j] \leq B[r(i),c(j)]$?

What is the best way to show this problem is NP-complete? I am currently considering reducing the clique problem to this problem.

$\endgroup$
6
$\begingroup$

As you mentioned, we can reduce maximum clique problem to this. In fact we can reduce the more general subgraph isomorphism problem to this one easily. Given graphs $G$ and $H$, define $A$ and $B$ as their (undirected) incidence matrices. Then we can see that solving the matrix correspondence tells whether $G$ is isomorphic to some subgraph of $H$, which is an NP-complete problem.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.