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

11

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 2M , existe uma aresta u 1 w 2 ou borda u 2 w 1 (ou ambos) em G ?G(V,E){U,W}MGu1w1,u2w2Mu1w2u2w1G

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 | .)MG[M]2K2|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.MGM

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.kNMGG[M]2K2|M|>kk=|U|

Obrigado.

Cyriac Antony
fonte
a correspondência perfeita pode não ser a palavra correta. Estamos basicamente perguntando se existe uma correspondência máxima com tamanho com a propriedade mencionada. |U|
Cyriac Antony
Em certo sentido, estamos pedindo algo oposto ao que é chamado de correspondência forte. Um forte correspondente em um gráfico G é um emparelhamento M de tal modo que não há nenhuma vantagem em L de conectar os dois bordos de HMGMGM
Cyriac Antony
Desculpe, por , eu quis dizer o subgrafo de G induzido por vértices 'em' MG[M]GM
Cyriac Antony

Respostas:

5

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.

n1ϵ

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.

Cyriac Antony
fonte
1

MGMG
eeee

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.

Cyriac Antony
fonte
editado para corrigir um erro; Eu pensei que gráficos de linha de gráficos bipartidos são bipartidos. :)
Cyriac Antony
Eu acho que deveria haver um +1 na sua definição de distância entre as arestas (pela definição atual, as arestas de M estariam na distância 1, pois existe uma aresta - um caminho de comprimento 1 - conectando cada par de arestas de M, mas você quer dizer a distância 2).
Florent Foucaud
corrigido como "arestas ... estão à distância 1 uma da outra". Obrigado @Florent Foucaud
Cyriac Antony
Isso funciona, mas agora, infelizmente, sua "distância das arestas" não corresponde à distância do vértice dos vértices correspondentes no gráfico de linhas.
Florent Foucaud
11
Para tornar a modelagem mais próxima do seu problema, lembre-se de que uma correspondência máxima em um gráfico corresponde a um conjunto independente máximo em seu gráfico de linhas. Portanto, no gráfico de linhas, você está procurando um conjunto forte que também seja um conjunto independente máximo (em particular, também deve ser um conjunto dominante).
Florent Foucaud