Máxima correspondência de peso e funções submodulares

Dado um gráfico bipartido com pesos positivos, deixe com igual ao peso máximo correspondente no gráfico . $G = (U \cup V, E)$ $f: 2^U \rightarrow \mathbb{R}$ $f(S)$ $G[S\cup V]$

É verdade que é uma função submodular? $f$

matching submodularity George Octavian Rabanca
fonte

O que você acha? Você já tentou provar / refutar?

Yuval Filmus

Intuitivamente, parece que deveria ser verdade, mas não pude provar. Também acho que, se for verdade, deve ser um resultado bem conhecido, mas não consegui encontrar uma referência.

George Octavian Rabanca

Isso vale para caixas não ponderadas, pois podem ser reduzidas a min-cortes. Não é óbvio como provar a versão ponderada ...

Chao Xu

Considere com pesos de borda 1,1,1,2.

K_{2, 2}

$K_{2,2}$

András Salamon

@ AndrásSalamon Parece que no último passo você assume que é aditivo, o que não é verdade. A correspondência máximo de pode usar vértices que já foram usados por ambos correspondência de e . Eu tenho uma prova disso agora, mas é definitivamente mais envolvido do que isso.

f

$f$

S \cap T

$S\cap T$

S ∖ T

$S \setminus T$

T ∖ S

$T \setminus S$

George Octavian Rabanca

Definição . Para um dado conjunto finito , uma função de conjunto é submodular se, para qualquer ele sustenta que: $A$ $f:2^A \rightarrow \mathbb{R}$ $X, Y \subseteq A$

f (X) + f (Y) \geq f (X \cup Y) + f (X \cap Y) .

$f(X) + f(Y) \geq f(X \cup Y) + f(X \cap Y).$

Lema Dado um gráfico bipartido com pesos de borda positivos, seja a função que mapeia para o valor máximo correspondência de peso em . Então é submodular. $G = (A \cup B, E)$ $f: 2^A \rightarrow \mathbb{R}^+$ $S\subseteq A$ $G[S \cup B]$ $f$

Prova. Corrija dois conjuntos e permita que e sejam duas correspondências para os gráficos e respectivamente . Para provar o lema, basta mostrar que é possível particionar as arestas em e em duas correspondências e para os gráficos e respectivamente. . $X, Y \subseteq A$ $M_\cap$ $M_\cup$ $G[(X\cap Y) \cup B]$ $G[(X \cup Y) \cup B]$ $M_\cap$ $M_\cup$ $M_X$ $M_Y$ $G[X\cup B]$ $G[Y\cup B]$

As arestas de e formam uma coleção de caminhos e ciclos alternados. Vamos denotar esta recolha e observar que nenhum ciclo de contém vértices de ou . Isso ocorre porque não corresponde a esses vértices. $M_\cap$ $M_\cup$ $\mathcal{C}$ $\mathcal{C}$ $X\setminus Y$ $Y\setminus X$ $M_\cap$

Vamos ser o conjunto de caminhos de com pelo menos um vértice em e deixá- ser o conjunto de caminhos de com pelo menos um vértice em . Dois desses caminhos são representados na figura abaixo. $\mathcal{P}_X$ $\mathcal{C}$ $X \setminus Y$ $\mathcal{P}_Y$ $\mathcal{C}$ $Y \setminus X$

Reivindicação 1. . $\mathcal{P}_X \cap \mathcal{P}_Y = \emptyset$

Suponha por contradição que existe um caminho . Vamos ser um vértice em no trajecto e semelhante deixar ser um vértice em no caminho . Observa-se que uma vez que nem nem pertencem que não pertencem ao correspondente , por definição, e, por conseguinte, eles são os pontos de extremidade do caminho . Além disso, como e estão em $P \in \mathcal{P}_X \cap \mathcal{P}_Y$ $x$ $X\setminus Y$ $P$ $y$ $Y \setminus X$ $P$ $x$ $y$ $X \cap Y$ $M_\cap$ $P$ $x$ $y$ $A$ , o caminho tem comprimento uniforme e, como é um caminho alternativo, a primeira ou a última aresta pertencem a . Portanto, corresponde a ou , o que contradiz a definição e comprova a afirmação. $P$ $M_\cap$ $M_\cap$ $x$ $y$

Seja e É claro que

M_{X} = (P_{X} \cap M_{\cup}) \cup ((C ∖ P_{X}) \cap M_{\cap})

$M_X = (\mathcal{P}_X \cap M_\cup) \cup ( (\mathcal{C} \setminus \mathcal{P}_X) \cap M_\cap)$

M_{Y} = (P_{X} \cap M_{\cap}) \cup ((C ∖ P_{X}) \cap M_{\cup}) .

$M_Y = (\mathcal{P}_X \cap M_\cap) \cup ( (\mathcal{C} \setminus \mathcal{P}_X) \cap M_\cup).$

M_{X} \cup M_{Y} = M_{\cap} \cup M_{\cup}

$M_X \cup M_Y = M_\cap\cup M_\cup$ e

. Para provar o teorema, resta mostrar que

são correspondências válidas para

respectivamente. Para ver que

é uma combinação válida para

observe primeiro que nenhum vértice de

é correspondido por

M_{X} \cap M_{Y} = M_{\cap} \cap M_{\cup}

$M_X \cap M_Y = M_\cap \cap M_\cup$

M_{X}

$M_X$

M_{Y}

$M_Y$

G [X \cup B]

$G[X\cup B]$

G [Y \cup B]

$G[Y\cup B]$

M_{X}

$M_X$

G [X \cup B]

$G[X\cup B]$

Y ∖ X

$Y \setminus X$

desde

não intersecta

na Reivindicação 1, e

não intersecta

, por definição. Portanto,

utiliza apenas vértices de

. Segundo, observe que todo vértice

corresponde a no máximo uma aresta de

pois, caso contrário,

pertence a duas arestas de

ou a duas arestas de

, contradizendo a definição. Isso prova que

M_{X}

$M_X$

P_{X}

$\mathcal{P}_X$

Y ∖ X

$Y \setminus X$

M_{\cap}

$M_\cap$

Y ∖ X

$Y \setminus X$

M_{X}

$M_X$

X \cup B

$X \cup B$

x \in X

$x\in X$

M_{X}

$M_X$

x

$x$

M_{\cup}

$M_\cup$

M_{\cap}

$M_\cap$

M_{X}

$M_X$ é uma correspondência válida para

; mostrando que

é um emparelhamentos válidos para

é semelhante.

G [X \cup B]

$G[X\cup B]$

M_{Y}

$M_Y$

G [Y \cup B]

$G[Y\cup B]$

George Octavian Rabanca
fonte

Isso parece ótimo! Como sugestão secundária: as definições de

não são simétricas, portanto, sua afirmação final de que "

... é semelhante" não é imediata. É mais claro (eu acho) se você deixar

denotar os componentes conectados que não tocam em nenhum vértice em

e definir

M_{X}

$M_X$

M_{Y}

$M_Y$

M_{Y}

$M_Y$

C^{'} ≐ C ∖ P_{X} ∖ P_{Y}

$\mathcal{C'} \doteq \mathcal{C} \setminus \mathcal{P}_X \setminus \mathcal{P}_Y$

X Δ Y

$X \Delta Y$

ser o mesmo com

permutado e, em seguida, o último

alterado para

M_{X} = (P_{X} \cap M_{\cup}) \cup (P_{Y} \cap M_{\cap}) \cup (C^{'} \cap M_{\cap})

$M_X = (\mathcal{P}_X \cap M_\cup) \cup (\mathcal{P}_Y \cap M_\cap) \cup (\mathcal{C'} \cap M_\cap)$

M_{Y}

$M_Y$

X

$X$

Y

$Y$

M_{\cap}

$M_\cap$

M_{\cup}

$M_\cup$

Andrew Morgan

Máxima correspondência de peso e funções submodulares

Respostas: