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 ?
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 | .)
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.
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.
Obrigado.
Respostas:
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.
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.
fonte
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.
fonte