Uma variante interessante do problema de correspondência máxima

8

Dado um gráfico , o problema clássico de correspondência máxima é escolher o subconjunto máximo de arestas st, para cada aresta , .M ( u , v ) M d ( u ) = d ( v ) = 1G(V,E)M(u,v)Md(u)=d(v)=1

Alguém estudou a seguinte variante? Para cada aresta , , onde c é um constante. Chamamos essa restrição de restrição de grau.( ( d ( u ) < c )( d ( v ) < c ) )(u,v)M((d(u)<c)(d(v)<c))

A restrição clássica é uma conjunção em grau com constante 1. A nova variante é uma disjunção em grau com constante .c

O problema em já está como mostra Jukka Suomela. Estou interessado nos possíveis algoritmos de aproximação. Um algoritmo simples e ganancioso seleciona o subgrafo de estrela máximo iterativamente até que nenhum subgrafo de estrela (ou seja, nenhuma aresta (uma estrela especial)) possa ser selecionado. Mas esse algoritmo tem um desempenho ruim, mesmo quando é uma árvore quando . Existe uma estrela interna cujo centro possui o grau , e existem estrelas externas em que cada centro possui o grau e conectado ao centro da estrela interna. O valor ideal é selecionando arestas de cada um deN P - c o m p L e T e L c = 3 x x x 2 * x + ( X - 2 ) * ( x - 1 ) x - 2 x - 2c=2NPcompleteGc=3xxx2x+(x2)(x1)x2x2estrelas externas e 2 estrelas externas completas. O valor produzido pelo algoritmo greeedy é , selecionando a estrela interna e uma aresta de cada estrela externa.x+1x

O algoritmo guloso acima é de aproximação, onde. Eu quero encontrar um algoritmo de aproximação melhor desse algoritmo ou provar sua dureza de aproximação. n=| V|2n1n=|V|

Além disso, quero conhecer a classe de complexidade desse problema no quadro da complexidade parametrizada. Talvez ele possua um algoritmo de parâmetro fixo razoável.

Muito obrigado pelo seu comentário e resposta com antecedência. :-)

Peng Zhang
fonte
1
Então, se , você deseja encontrar um subgráfico que consiste em estrelas disjuntas? E, por exemplo, em a solução ideal consiste em exatamente duas estrelas ( arestas)? K n , n 2 n - 2c=1Kn,n2n2
Jukka Suomela
1
O caso de parece estar intimamente relacionado ao problema do conjunto dominante: em um gráfico com nós, é possível encontrar uma solução com arestas se você tiver um conjunto dominante de tamanho . c=1nnkk
Jukka Suomela
Sim. Não mas é sua instância. Muito obrigado. É exatamente o que eu quero perguntar. Alguém já estudou essa variante antes? Meu problema atual está no gráfico bipartido com . c=1c=2c=3
Peng Zhang
2
Bem, muitas pessoas estudaram conjuntos dominantes . :) Difícil de resolver, difícil de aproximar, mesmo em gráficos bipartidos. Eu diria que o caso de um maior não é nada fácil ...c
Jukka Suomela
2
É um pouco confuso ver uma recompensa anexada a uma pergunta com uma resposta aceita. Teria sido melhor emitir a nova pergunta separadamente. infelizmente, agora que você anexou uma recompensa, não acho que isso seja possível.
Suresh Venkat

Respostas:

8

(Como parece que a conexão não é completamente óbvia, escreverei uma versão estendida dos comentários acima como resposta.)

Vou me concentrar no caso de . Nesse caso, o problema pode ser reformulado da seguinte maneira:c=2

  • Seja um gráfico. A tarefa é encontrar um M E de tamanho máximo, de modo que a seguinte restrição seja atendida: para cada { u , v } M , u é incidente com no máximo 1 borda em M ou v é incidente com no máximo 1 borda em M , ou ambos.G=(V,E)ME{u,v}Mu1Mv1M

Equivalentemente:

  • O subgráfico induzido por deve ter a propriedade de que todos os vizinhos de um nó não foliar (grau> 1) são nós foliares (grau = 1).M

Equivalentemente:

  • O subgrafo induzido por consiste em estrelas disjuntas.M

A seguir, interpretarei os nós não correspondentes (nós não relacionados a nenhuma aresta em ) como estrelas com 0 arestas. Portanto, uma solução viável particiona o conjunto de nós em estrelas separadas por nós.M

Agora, se o número dessas estrelas for , então o número de arestas em M é exatamente n - k : existem n - k nós de folhas que estão conectados a um centro de estrelas. Portanto, maximizar o número de arestas em M é equivalente a minimizar o número de estrelas.kMnknkM

Agora é fácil ver que temos uma solução com tais estrelas se tivermos um conjunto dominante de tamanho k :kk

  1. Suponha que recebemos tais estrelas. Então, podemos encontrar um conjunto dominante de tamanho k : simplesmente pegue o centro das estrelas (em uma estrela com 1 borda, você pode escolher um nó arbitrariamente).kk
  2. Suponha que recebemos um conjunto dominante com | D | = k . Então podemos simplesmente conectar cada nó no V D em um nó D . Essas arestas formam uma família de k estrelas.D|D|=kVDDk

Portanto resolver o problema de forma otimizada em uma determinada família gráfico é exatamente tão difícil como encontrar um conjunto dominante mínimo na mesma família gráfico F . Em particular, o problema é NP-difícil, mesmo no caso de gráficos bipartidos.FF

(No entanto, os resultados de (in) aproximabilidade relacionados a conjuntos dominantes não podem ser diretamente aplicados aqui. Em essência, alteramos a função objetivo de para .)min|D|maxn|D|

Jukka Suomela
fonte
Ótimo. Os resultados de (in) aproximabilidade relacionados a conjuntos dominantes não podem ser aplicados diretamente aqui, assim como a inviabilidade de aplicar (in) aproximabilidade da cobertura de vértice a um conjunto independente.
Peng Zhang
Para , também é N P - c o m p l e t e . Reduziremos ( G ( V , E ) , c = 2 ) a ( G ( V { v } , E { ( u , v ) } , u V ) , c = 3 )c=3NP-compeuete(G(V,E),c=2)(G(V{v},E{(u,v)},uV),c=3). tem uma solução K se G ' tem uma solução K. GKGK
Peng Zhang