Das am schwersten induzierte Subgraph-Problem

Ich interessiere mich für ein solches kombinatorisches Problem: ein Graph und eine Gewichtsfunktion und sind, fragen wir nach einem solchen induzierten Teilgraphen von , das die Summe maximiert: . $G=(V, E)$ $w_v: V \mapsto R$ $w_e: E \mapsto R$ $G' = (V', E')$ $G$ $\sum_{e \in E'} w_e(e) + \sum_{v \in V'} w_v(v)$

Das Problem ist NP-H ard (durch die Reduktion vom Maximum-Clique-Problem), daher wären Vorschläge für Approximationslösungen (auch gierig) und Links zur Literatur willkommen.

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

@Juho Zunächst möchte ich wissen, ob ein solches Problem in Betracht gezogen wurde. Jede Studie, einschließlich einer Arbeit mit experimentellen Ergebnissen, ist willkommen.

Łukasz Kuszner

Ja, es wurde sehr detailliert untersucht. en.wikipedia.org/wiki/Clique_problem#Hardness_of_approximation

Pål GD

Suche auch nach Weighted Clique.

Pål GD

In der Literatur die schwersten

k

$k$ -subgraph Problem ist Ihr Problem, wo alle Eckpunkte Gewicht 1 haben.

Juho

@ Juho Zum Beispiel hier am schwersten

k

$k$ -subgraph Problem wird diskutiert, es ist jedoch nicht das gleiche (aber ziemlich ähnlich), das Sie nehmen dürfen, sondern angegeben

k

$k$ verschiedene Eckpunkte. In dem Fall, nach dem ich frage, können Sie eine beliebige Anzahl von Knoten nehmen. Wenn Sie also etwas näheres als das oben erwähnte Papier von Alain Billionnet gefunden haben, weisen Sie bitte darauf hin - es wäre für mich von Bedeutung.

Łukasz Kuszner

Antworten:

$\newcommand{\R}{\mathbb{R}}$ Betrachten wir einen Sonderfall des Problems, bei dem der Scheitelpunkt ein negatives Gewicht und die Kanten ein positives Gewicht haben. Also und . $w_v: V\to \R^-$ $w_e: E\to \R^+$

Das schwerste Untergraphen zu finden , ist gleichbedeutend mit einer Min- -Schnitt Berechnung auf einem geeigneten Graphen. Wir werden uns in dieser Präsentation auf die Folien zum dichtesten Untergraphen beziehen . $st$

In der Tat entspricht das Minimieren von dem Minimieren von . (Beachten Sie, dass der Grad hier gewichteter Grad ist, ) Die Ableitung der obigen Tatsache ist ähnlich wie bei Folie 21. Dann kann dies gelöst werden leicht durch sie als minera Modellierung -Schnitt in anderer graph (siehe Schlitten 22). Es ist wichtig, negative Scheitelpunktgewichte und positive Kantengewichte zu haben, damit die Reduzierung funktioniert. $w_e(E(V'))+w_v(V')$ $(-w_v(V')) + \frac{1}{2} w_e(E(V',\bar{V'})) + \frac{1}{2} \sum_{v\in \bar{V'}} \deg(v)$ $\deg(v) =\sum_{e:v\in e} w_e(e)$ $st$

Chao Xu
quelle