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

Dado um gráfico , o problema clássico de correspondência máxima é escolher o subconjunto máximo de arestas st, para cada aresta , . $G(V,E)$ $M$ $(u,v) \in M$ $d(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. $(u,v) \in M$ $\left( \left(d(u) < c\right) \lor \left(d(v) < c\right) \right)$

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 de $c=2$ $NP-complete$ $G$ $c=3$ $x$ $x$ $x$ $2*x+(x-2)*(x-1)$ $x-2$ $x-2$ estrelas externas e 2 estrelas externas completas. O valor produzido pelo algoritmo greeedy é , selecionando a estrela interna e uma aresta de cada estrela externa. $x+1*x$

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. $2\sqrt{n-1}$ $n=|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. :-)

cc.complexity-theory ds.algorithms graph-theory co.combinatorics Peng Zhang
fonte

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)?

c = 1

$c = 1$

K_{n, n}

$K_{n,n}$

2 n - 2

$2n-2$

Jukka Suomela

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 = 1

$c=1$

n

$n$

n - k

$n-k$

k

$k$

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 = 1

$c=1$

c = 2

$c=2$

c = 3

$c=3$

Peng Zhang

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

$c$

Jukka Suomela

É 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:

(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 tamanho máximo, de modo que a seguinte restrição seja atendida: para cada , é incidente com no máximo borda em ou é incidente com no máximo borda em , ou ambos. $G = (V,E)$ $M \subseteq E$ $\{u,v\} \in M$ $u$ $1$ $M$ $v$ $1$ $M$

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 é exatamente : existem nós de folhas que estão conectados a um centro de estrelas. Portanto, maximizar o número de arestas em é equivalente a minimizar o número de estrelas. $k$ $M$ $n-k$ $n-k$ $M$

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

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

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 . Em particular, o problema é NP-difícil, mesmo no caso de gráficos bipartidos. $F$ $F$

(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|$ $\max n-|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 é

. Reduziremos

c = 3

$c=3$

N P - c o m p l e t e

$NP-complete$

(G (V, E), c = 2)

$( G(V,E),c=2)$

(G^{'} (V \cup {v}, E \cup {(u, v)}, u \in V), c = 3)

$( G'(V \cup \{v\} , E \cup \{(u,v)\}, u \in V), c=3)$ .

tem uma solução

G

$G$

K

$K$

G^{'}

$G'$

K

$K$

Peng Zhang