6
$\begingroup$

I am trying to solve a problem on graphs, which I have reduced to the following optimization problem in matrix $X \in \{0,1\}^{n \times n}$

$$\begin{array}{ll} \text{minimize} & \| X - A \|_F^2\\ \text{subject to} & X 1_n = m 1_n\\ & X=X^\top\end{array}$$

where matrix $A \in \{0,1\}^{n \times n}$ is given. Matrix $X$ is the adjacency matrix of a non-directed $m$-regular graph, while matrix $A$ is the adjacency matrix of a directed graph.

I am quite clueless on how to go on solving this problem and would be happy to get a direction.

$\endgroup$
  • $\begingroup$ Are all those conditions saying that $X$ is adjacency matrix or am I missing some subtlety there? $\endgroup$ – Radost Jun 4 at 9:59
  • 2
    $\begingroup$ X is an adjacency matrix for a non directed graph, where each vertex is of rank m. While the input A is an adjacency matrix of a directed graph. $\endgroup$ – Jonathan Jun 4 at 10:08
  • $\begingroup$ Thanks, that's much clearer! $\endgroup$ – Radost Jun 4 at 10:08
  • $\begingroup$ I'm guessing $||.||_F$ is Frobenius norm. And the min has to be taken along the undirected graph otherwise the obvious solution would be $X=A$. $\endgroup$ – Radost Jun 4 at 10:11
  • $\begingroup$ The norm is Frobenius. As for the second observation, $X=A$ would also not hold the constraint of the row sums, as we have no information about them in A. $\endgroup$ – Jonathan Jun 4 at 10:15
4
$\begingroup$

We have the following optimization problem in matrix $\mathrm X \in \{0,1\}^{n \times n}$

$$\begin{array}{ll} \text{minimize} & \| \mathrm X - \mathrm A \|_{\text{F}}^2\\ \text{subject to} & \mathrm X 1_n = m 1_n\\ & \mathrm X = \mathrm X^\top\\ & \mathrm X \in \{0,1\}^{n \times n}\end{array}$$

where matrix $\mathrm A \in \{0,1\}^{n \times n}$ is given. Note that

$$\| \mathrm X - \mathrm A \|_{\text{F}}^2 = \| \mathrm X \|_{\text{F}}^2 - 2 \langle \mathrm A, \mathrm X \rangle + \| \mathrm A \|_{\text{F}}^2$$

and that $\| \mathrm X \|_{\text{F}}^2 = m n$, due to the constraints. Hence, we have the following integer program (IP)

$$\begin{array}{ll} \text{maximize} & \langle \mathrm A, \mathrm X \rangle\\ \text{subject to} & \mathrm X 1_n = m 1_n\\ & \mathrm X = \mathrm X^\top\\ & \mathrm X \in \{0,1\}^{n \times n}\end{array}$$

which appears to be a generalization of the assignment problem. Perhaps there is a generalization of the Hungarian algorithm, too.

$\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.