Eine interessante Variante des Maximum-Matching-Problems

Bei gegebenem Graphen $G(V,E)$ besteht das klassische Problem der maximalen Übereinstimmung darin, die maximale Teilmenge der Kanten st für jede Kante wählen , . $M$ $(u,v) \in M$ $d(u)=d(v)=1$

Hat jemand die folgende Variante studiert? Für jede Kante gilt , wobei c a ist Konstante. Wir nennen diese Einschränkung eine Gradbeschränkung. $(u,v) \in M$ $\left( \left(d(u) < c\right) \lor \left(d(v) < c\right) \right)$

Die klassische Bedingung ist eine Konjunktion des Grades mit der Konstanten 1. Die neue Variante ist eine Disjunktion des Grades mit der Konstanten . $c$

Das Problem auf ist bereits wie Jukka Suomela zeigt. Ich interessiere mich für die möglichen Approximationsalgorithmen. Ein einfacher Greedy-Algorithmus wählt iterativ den maximalen Stern-Teilgraphen aus, bis kein Stern-Teilgraph (dh keine Kante (ein spezieller Stern)) ausgewählt werden kann. Aber dieser Algorithmus arbeitet schlecht, selbst wenn ein Baum ist, wenn . Es gibt einen inneren Stern, dessen Zentrum den Grad , und es gibt äußere Sterne, jedes Zentrum hat den Grad und ist mit dem Zentrum des inneren Sterns verbunden. Der optimale Wert ist durch Auswahl von Kanten aus jedem von $c=2$ $NP-complete$ $G$ $c=3$ $x$ $x$ $x$ $2*x+(x-2)*(x-1)$ $x-2$ $x-2$ äußere Sterne und 2 vollständige äußere Sterne. Der vom greeedy-Algorithmus erzeugte Wert ist $x+1*x$ indem der innere Stern und eine Kante von jedem äußeren Stern ausgewählt werden.

Der obige gierige Algorithmus ist $2\sqrt{n-1}$ Näherung, wobei $n=|V|$ . Ich möchte einen besseren Approximationsalgorithmus für diesen Algorithmus finden oder seine Approximationshärte beweisen.

Darüber hinaus möchte ich die Komplexitätsklasse dieses Problems im Rahmen der parametrisierten Komplexität kennen. Vielleicht trägt es einen vernünftigen Algorithmus mit festen Parametern.

Vielen Dank für Ihren Kommentar und Ihre Antwort im Voraus. :-)

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

Wenn also

, möchten Sie einen Untergraphen finden, der aus disjunkten Sternen besteht? Und zum Beispiel besteht in

die optimale Lösung dann aus genau zwei Sternen (

Kanten)?

c = 1

$c = 1$

K_{n, n}

$K_{n,n}$

2 n - 2

$2n-2$

Jukka Suomela

Der Fall von

scheint eng mit dem Problem der dominierenden Menge verbunden zu sein: In einem Graphen mit

Knoten können Sie eine Lösung mit

Kanten finden, wenn Sie eine dominierende Menge der Größe

c = 1

$c=1$

n

$n$

n - k

$n-k$

k

$k$

Jukka Suomela

Ja. Nicht

sondern

ist Ihre Instanz. Vielen Dank. Es ist genau das, worüber ich fragen möchte. Hat jemand diese Variante schon einmal studiert? Mein aktuelles Problem ist ein zweigeteilter Graph mit

c = 1

$c=1$

c = 2

$c=2$

c = 3

$c=3$

Peng Zhang

Nun, viele Leute haben dominierende Sets studiert . :) Schwer zu lösen, schwer zu approximieren, selbst auf zweigeteilten Graphen. Ich würde annehmen, dass der Fall eines größeren

nicht einfacher ist ...

c

$c$

Jukka Suomela

Es ist etwas verwirrend zu sehen, dass einer Frage ein Kopfgeld mit einer akzeptierten Antwort beigefügt ist. Es wäre besser gewesen, die neue Frage separat zu stellen. Leider halte ich das jetzt, da Sie ein Kopfgeld beigefügt haben, nicht für möglich.

Suresh Venkat

Antworten:

(Da der Zusammenhang anscheinend nicht ganz offensichtlich ist, werde ich als Antwort eine erweiterte Version der obigen Kommentare schreiben.)

Ich werde mich auf den Fall von . In diesem Fall kann das Problem wie folgt umformuliert werden: $c = 2$

Sei ein Graph. Die Aufgabe besteht darin, eine maximale Größe so dass die folgende Bedingung erfüllt ist: Für jedes fällt entweder auf höchstens Kante in oder auf höchstens Kante in oder beides. $G = (V,E)$ $M \subseteq E$ $\{u,v\} \in M$ $u$ $1$ $M$ $v$ $1$ $M$

Gleichwertig:

Der durch induzierte Teilgraph muss die Eigenschaft haben, dass alle Nachbarn eines Nicht-Blattknotens (Grad> 1) Blattknoten sind (Grad = 1). $M$

Gleichwertig:

Der durch induzierte Teilgraph besteht aus knotendisjunkten Sternen. $M$

Im Folgenden werde ich nicht übereinstimmende Knoten (Knoten, die auf keine Kante in ) als Sterne mit 0 Kanten interpretieren . Daher ist eine machbare Lösung partitioniert den Satz von Knoten in knotendisjunkt Sternen. $M$

Wenn nun die Anzahl solcher Sterne , dann ist die Anzahl der Kanten in genau : Es gibt Blattknoten, die mit einem Sternzentrum verbunden sind. Daher entspricht das Maximieren der Anzahl der Kanten in dem Minimieren der Anzahl der Sterne. $k$ $M$ $n-k$ $n-k$ $M$

Nun ist es einfach zu sehen, dass wir eine Lösung mit solchen Sternen haben, wenn wir eine dominierende Menge der Größe : $k$ $k$

Angenommen, wir erhalten solche Sterne. Dann können wir eine dominierende Menge der Größe : Nehmen Sie einfach die Zentren der Sterne (in einem Stern mit 1 Kante können Sie einen Knoten beliebig auswählen). $k$ $k$
Angenommen, wir erhalten eine dominierende Menge mit . Dann können wir einfach jeden Knoten in mit einem Knoten in . Diese Kanten bilden eine Familie von Sternen. $D$ $|D| = k$ $V \setminus D$ $D$ $k$

Daher ist es genauso schwierig , das Problem in einer bestimmten Graphenfamilie optimal zu lösen, wie eine minimale dominierende Menge in derselben Graphenfamilie . Insbesondere ist das Problem selbst bei zweigeteilten Graphen NP-schwer. $F$ $F$

((In-) Approximierbarkeitsergebnisse in Bezug auf dominierende Mengen können hier jedoch nicht direkt angewendet werden. Im Wesentlichen haben wir die Zielfunktion von auf geändert .) $\min |D|$ $\max n-|D|$

Jukka Suomela
quelle

Großartig. (in) Approximierbarkeitsergebnisse in Bezug auf dominierende Mengen können hier nicht direkt angewendet werden, ebenso wie die Unmöglichkeit, (in) Approximierbarkeit der Scheitelpunktabdeckung auf unabhängige Mengen anzuwenden.

Peng Zhang

Für

ist es auch

. Wir werden

auf

reduzieren.

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)$ .

hat eine

Lösung, wenn

eine

Lösung hat.

G

$G$

K

$K$

G^{'}

$G'$

K

$K$

Peng Zhang