O maior problema de subgráfico induzido

Estou interessado em um problema tão combinatório: dado um gráfico $G=(V, E)$ e funções de peso $w_v: V \mapsto R$ e $w_e: E \mapsto R$ estamos perguntando sobre um subgráfico induzido $G' = (V', E')$ do $G$ que maximiza a soma: $\sum_{e \in E'} w_e(e) + \sum_{v \in V'} w_v(v)$ .

O problema é NP- Ard (pela redução do problema máximo de clique), para que sejam apreciadas quaisquer sugestões de soluções de aproximação (até gananciosas) e links para a literatura.

graph-theory optimization approximation greedy-algorithms Łukasz Kuszner
fonte

@ Juho Antes de mais nada, gostaria de saber se esse problema foi considerado. Qualquer estudo, incluindo um artigo com resultados experimentais, é bem-vindo.

Łukasz Kuszner

Sim, foi estudado em grandes detalhes. pt.wikipedia.org/wiki/Clique_problem#Hardness_of_approximation

Pål GD

Pesquise também por Clique Ponderado.

Na literatura, os mais pesados

k

$k$ -subgraph problem é seu problema em que todos os vértices têm peso 1. #

Juho

@ Juho Por exemplo, aqui mais pesado

k

$k$ O problema do sub-gráfico é discutido, no entanto, não é o mesmo (mas bastante semelhante) que você pode usar, mas especificado

k

$k$ vértices diferentes. No caso, eu estou perguntando sobre você pode ter qualquer quantidade de nós. Portanto, se você encontrou algo mais próximo do que o artigo de Alain Billionnet mencionado acima, por favor, indique-o - seria significativo para mim.

Łukasz Kuszner

Respostas:

$\newcommand{\R}{\mathbb{R}}$ Vamos considerar um caso especial do problema em que o vértice tem peso negativo e as arestas têm peso positivo. assim $w_v: V\to \R^-$ e $w_e: E\to \R^+$ .

Encontrar o subgráfico induzido mais pesado é equivalente a um $st$ corte a computação em um gráfico adequado. Iremos nos referir aos slides sobre o subgráfico mais denso nesta apresentação .

De fato, minimizar $w_e(E(V'))+w_v(V')$ é equivalente a minimizar $(-w_v(V')) + \frac{1}{2} w_e(E(V',\bar{V'})) + \frac{1}{2} \sum_{v\in \bar{V'}} \deg(v)$ . (Observe que o grau aqui é grau ponderado, ou seja, $\deg(v) =\sum_{e:v\in e} w_e(e)$ ) A derivação do fato acima é semelhante ao slide 21. Em seguida, isso pode ser resolvido facilmente modelando-o como um $st$ -corte em algum outro gráfico (veja o slide 22). É crucial ter pesos de vértice negativos e pesos de borda positivos para que a redução funcione.

Chao Xu
fonte