Joeの精進記録

旧：競プロ練習記録

mdj982ゼミまとめ

Quadratic Assignment Problem (NP-hard)

Given $C, D \in \mathbb{R}^{n\times n}$ , $\min (X^TCX)\cdot D$ ( $X \in \mathrm{Perm}_n \subset \mathbb{R}^{n \times n}$ )

ただし $A\cdot B$ は $A$ と $B$ の要素ごとの積の和

Graph Isomorphism

図は省略するが、同型なグラフ $G, H$ があったときに、頂点のラベル付けの置換行列を $X$ とすると、 $X^TA_GX = A_H$ はとなる。

同型なら $\max_X (X^TA_HX) \cdot A_G = 2|E|$ となる。

Subgraph Isomorphism

頂点の個数が違っていたとしてもdummyの頂点を用意していて頂点数を揃える。

$X^TA_HX$ と $A_G$ を比較したときに、1が0に対応するのだけ許さないことにする。

HがGのsubgraphなら $\max_X (X^T A_H X) \cdot A_G = 2|E_H|$ となる。

誘導部分グラフ同型

隣接行列を拡張。辺がない頂点間を $-\infty$ とする隣接行列を考える。対角成分は0で、dummyの頂点を含む $(i, j)$ も0

HがGの誘導部分グラフなら $\max_X (X^T A_H X) \cdot A_G = 2|E_H|$ となる。

縮約

縮約があるものだと難しい

QAPのソルバー

heuristicsで1e6オーダーまでできるらしい

APX-hardなのでheuristics強い。

Graph Edit Distance

erase edge
erase vertex
add edge
add vertex

ここまでで同型なグラフを作る。各頂点/辺に関してコストが違っていてもよい。QAPのように、事前にdummyの頂点 $\varepsilon$ を追加しておくと、頂点を消す操作は、 $\varepsilon$ へ投げる操作、頂点を加える操作は、 $\varepsilon$ から頂点をもってくる操作に対応する。

$\phi$ に関するコスト（mappingに関するコスト）

$(X^TCX)\cdot D = \sum_i \sum_j (\sum_k \sum_l C_{kl}X_{ki}X_{lj}D_{ij})$

と展開され、 $(k, l)$ を $(i, j)$ にマッピングするコストは $C_{kl}D_{ij}$ となる。

辺の属性が2値であるならば、 $1, -1$ をコストとして振り分けてやると、同じ属性ならば $1$ , 違う属性なら $-1$ になって便利

max-cutのformulationと似ていそう