Encontre um violador de Hall de cardinalidade mínima

Dado um gráfico bipartido $(X,Y，E)$, em que não há uma correspondência perfeita, quero encontrar um menor subconjunto que viole a condição de Hall, ou seja, um conjunto de cardinalidade mínima $S \subseteq X$ para qual $|N(S)|<|S|$.

Esse problema é a versão de otimização de uma pergunta anterior. Encontrar um subconjunto no gráfico bipartido que viola a condição de Hall , da qual eu sei que existe um algoritmo de tempo polinomial para encontrar tais$S \subseteq X$. Existe um algoritmo polinomial para o problema de otimização?

Esta não é uma resposta - apenas uma nota longa.

A questão está relacionada ao problema da cobertura mínima de vértices com sobreposição mínima de um lado . Suponha que tenhamos uma cobertura mínima de vértices$C$ de tamanho $m$. Pelo teorema de Konig,$m$ também é igual ao tamanho da correspondência máxima, então $m < n$.

Desde a $C$ é uma cobertura de vértice, qualquer vértice que não esteja $C$ deve ter todos os seus vizinhos em $C$. assim$N(X\setminus C)\subseteq Y\cap C$. Conseqüentemente:

No entanto, não tenho certeza de que encontrar um $C$ o que maximiza $X\cap C$ também produz o menor violador de Hall.

tl; dr : Encontrei uma lacuna fatal nessa prova que não consegui fechar. Deixarei essa resposta no caso de: a) descobrir como corrigi-lo; b) inspirar alguém a descobrir como corrigi-lo.

Deixei $G = (X \cup Y, E)$seja um gráfico bipartido sem uma correspondência perfeita. Diremos que um subconjunto$S$é deficiente se$|N(S)| \lt |S|$. Estamos procurando um subconjunto mínimo e deficiente de$X$. A abordagem geral será identificar mínimo potencial, conjuntos deficientes caracterizando (e encontrar) todos os mini mal , conjuntos deficientes, ou seja: conjuntos deficientes$S\subset X$que não contém subconjuntos deficientes. Vamos fazer algumas observações sobre as propriedades desses conjuntos mínimos e deficientes.

Observação 1 : Um subconjunto$S$ é um subconjunto deficiente mínimo de $X$ iff para todos $s \in S$, o conjunto $S\setminus \{s\}$ tem uma combinação perfeita em $G$. Este é apenas o Teorema de Hall.

Observação 2 : se$S$ é um subconjunto deficiente mínimo de $X$, então para todos $s_1, s_2 \in S$, existe um caminho em $G$ de $s_1$ para $s_2$. Caso contrário, poderíamos decompor$S$ em dois (ou mais) componentes, pelo menos um dos quais teria que ser deficiente, contradizendo assim a minimalidade.

Agora, vamos consertar $M$, alguma correspondência máxima em $G$. Deixei$X' \subset X$ e $Y' \subset Y$ sejam os vértices que são correspondidos por $M$ e deixar $U = X\setminus X'$ ser o subconjunto de vértices incomparáveis ​​em $X$. Para qualquer subconjunto$S$ do $X$, também indicaremos $m(S)$ como o conjunto de vértices em $G$ acessível a partir de $S$ através da $M$caminhos alternativos.

Em uma resposta à pergunta vinculada no OP, vemos uma prova de que, se tomarmos$S = U \cup (m(U) \cap X)$ então $S$é deficiente. Uma leitura cuidadosa dessa prova revela que ela funciona não apenas para$U$ mas qualquer subconjunto de $U$. Ou seja, se pegarmos qualquer subconjunto$U_1 \subseteq U$, então $U_1 \cup (m(U_1) \cap X)$ é um subconjunto deficiente de $X$. Em particular, podemos tomar$U_1$para ser um conjunto singleton. Para qualquer$u \in U$, vamos definir $D_u = \{u\} \cup (m(\{u\}) \cap X)$.

Lema 1 :$D_u$ é um conjunto mínimo e deficiente para todos $u \in U$.

Prova : tomaremos como certo que$D_u$é deficiente por meio de prova fornecida na resposta mencionada anteriormente. Para mostrar isso$D_u$ é uma deficiência mínima de wrt, observamos que $D_u \setminus \{u\}$ é simplesmente um subconjunto de $X'$, portanto, existe uma combinação perfeita para ele dentro de $G$ (apenas tome a restrição de $M$ para $D_u\setminus \{u\}$) Para qualquer outro$y \in D_u$, seguimos o $M$caminho alternativo de $y$ para $u$, vire todas as bordas ao longo desse caminho e obtenha uma combinação perfeita de $D_u \setminus \{y\}$ no $G$. Então, pela observação 1,$D_u$ é um conjunto mínimo e deficiente. $\square$

Ok, agora que identificamos uma coleção de subconjuntos mínimos e deficientes de $X$, precisamos perguntar: e os outros?

Para adicionar um pouco de estrutura, vamos considerar qualquer conjunto $S \subseteq X$ estar na forma $S = U_1 \cup Z_1 \cup Z_2$ Onde $U_1 \subseteq U$, $Z_1 \subseteq m(U_1)$ e $Z_2 \subseteq X' \setminus m(U_1)$. Em outras palavras, nós quebramos$S$ na parte que é incomparável $M$ ($U_1$), a parte acessível a partir de $U_1$ através da $M$caminhos alternativos ($Z_1$) e a parte que não pode ser acessada $U_1$ através da $M$caminhos alternativos ($Z_2$) É trivial observar que, se$S$ é um conjunto deficiente, então $U_1$ deve estar não vazio.

Via Lema 1, abordamos o caso em que $Z_1 = m(U_1)$ e $Z_2$está vazia. Isso deixa três casos para examinar:

1. $Z_2$ está vazio
2. $|U_1| > 1$ e $Z_1 \subsetneq m(U_1)$
3. $Z_1$ e estão ambos vazios (por exemplo: ).$Z_2$$S \subseteq U$

Lema 2 : Se é tal que , então não é um subconjunto mínimo, deficiente de .$S = U_1 \cup Z_1 \cup Z_2 \subseteq X$$Z_2 \neq \emptyset$$S$$X$

Prova : Let ser os elementos de que são emparelhados com em . Por definição, não pode haver arestas de nem a pois isso implicaria um caminho alternativo de de para vértices em .$M(Z_2)$$Y$$Z_2$$M$$U_1$$Z_1$$M(Z_2)$$M$$U_1$$Z_2$

Se é um conjunto mínimo e deficiente, todos os subconjuntos de têm uma correspondência completa. Em particular, tem uma correspondência completa, digamos . Pela observação anterior, observamos que essa correspondência completa não usa nenhum dos vértices em . Portanto, a correspondência formada usando para corresponder a e para corresponder a é uma correspondência completa para , contradizendo a suposição de que era deficiente. $S$$S$$U_1 \cup Z_1$$M_1$$M_1$$M(Z_2)$$M_1$$U_1 \cup Z_1$$M$$Z_2$$S$$S$$\square$

Em uma versão anterior desta resposta, negligenciei o caso 2), assumindo que, de alguma forma, foi coberto durante a prova do Lema 1. No entanto, esse não é o caso. Pode haver conjuntos mínimos e deficientes que não se parecem com . O diagrama a seguir mostra um exemplo. Tomando as arestas em negrito como correspondente , podemos ver que é um conjunto mínimo e deficiente e não tem a forma . Ainda não consegui encontrar uma caracterização eficaz de conjuntos deficientes mínimos que se enquadram no caso 2, por isso, atualmente, não consigo concluir esta prova.$D_u$$M$$S = \{A, B, C\}$$D_u$