A correspondência máxima M com a condição G [M] é 2K_2-free

Existe algo na literatura próximo ao seguinte problema:

Dado um gráfico bipartido com bipartição balanceada { U , W } , existe uma combinação M perfeita em G, de modo que para cada 2 arestas u 1 w 1 , u 2 w 2 ∈ M , existe uma aresta u 1 w 2 ou borda u 2 w 1 (ou ambos) em G ?$G(V,E)$$\{U,W\}$$M$$G$$u_1w_1, u_2w_2\in M$$u_1w_2$$u_2w_1$$G$

Em outras palavras, existe uma correspondência perfeita de tal modo que o subgráfico induzida L [ M ] é 2 K 2 -livre. (Com bipartição equilibrada, eu quis dizer | U | = | W | .)$M$$G[M]$$2K_2$$|U|=|W|$

A condição extra é algo como um extremo oposto ao usado no problema de correspondência induzida. Outro problema possivelmente relacionado é o problema de encontrar o tamanho máximo correspondente a no gráfico bipartido G, de modo que a contração das arestas em M minimize o número de arestas restantes no gráfico.$M$$G$$M$

Verifiquei a lista de problemas relacionados à correspondência fornecidos por Plummer em Correspondência e embalagem de vértices: quão "difíceis" são? sem sucesso.

PS: Esse problema é um caso especial desse problema de decisão: - Para um dado , existe um M máximo correspondente de um gráfico bipartido G, de modo que G [ M ] seja 2 K 2 livre e | M | > k . Se o gráfico de entrada estiver equilibrado bipartido e k = | U | , obtemos o problema acima.$k\in\mathbb{N}$$M$$G$$G[M]$$2K_2$$|M|>k$$k=|U|$

Obrigado.

Surpresa! (para mim).
Esse tipo de correspondência já é estudado na literatura. Eles são chamados de correspondências conectadas .

Eles foram apresentados por Plummer, Stiebitz e Toft em seu estudo sobre a conjectura de Hadwiger. Veja o capítulo "Correspondências conectadas" de Cameron no livro "Otimização combinatória - Eureka, você encolhe!"

O status das correspondências conectadas nos gráficos bipartidos (não necessário balanceado) está aberto para o melhor de meu conhecimento ( atualizarei ). A versão ponderada do problema é NP-complete para gráficos bipartidos. O problema é solucionável no tempo polinomial para gráficos bipartidos de acordes.

$n^{1-\epsilon}$

Notas adicionadas anteriormente (mantidas para as pessoas interessadas):
" Correspondências conectadas em gráficos bipartidos de acordes " por Jobson et al. (doi: https://doi.org/10.1016/j.disopt.2014.06.003 ) e " Correspondências conectadas em famílias especiais de gráficos " de Caragianis (tese) são duas referências notáveis.

$M$$G$$M$$G$
$e$$e’$$e$$e’$

$L(G)$$G$

Sabe-se que o problema de conjunto fixo é NP-completo em algumas classes de gráfico. Não sei seu status em gráficos de linha de gráficos bipartidos. O artigo diz que é NP-completo em gráficos bipartidos. Nosso interesse aqui será na classe de gráficos de linha de gráficos bipartidos.