Was ist die Komplexität dieses Randfärbungsproblems?

17

Vor kurzem bin ich auf die folgende Variante der Kantenfärbung gestoßen.

Suchen Sie bei einem zusammenhängenden ungerichteten Graphen eine Färbung der Kanten, die die maximale Anzahl von Farben verwendet, und erfüllen Sie gleichzeitig die Bedingung, dass für jeden Scheitelpunkt die Kanten, die auf v einfallen, höchstens zwei Farben verwenden.vv

Meine erste Vermutung ist, dass das Problem NP-schwer ist. Klassische NP-Hardproofs für Grafikfarbprobleme werden meist durch Reduktion von 3SAT erstellt. Aber meiner Meinung nach sind diese Beweise für dieses Problem nicht nützlich, da Kanten, die auf einen Scheitelpunkt fallen, mit derselben Farbe gefärbt werden können, sodass wir keine logischen Komponenten im Diagramm konstruieren können.

Könnte dieses Problem NP-schwer sein? Wenn ja, was ist ein Beweis? Wenn wir keinen Beweis erbringen können, gibt es eine Methode, um die Komplexität dieses Problems zu bestimmen?

Vielen Dank!

cc.complexity-theory np-hardness complexity-classes graph-colouring RIC_Eien
quelle
Vielleicht ist Mixed oder Color-bounded Hypergraph Coloring der Anfang? Zum Beispiel, dx.doi.org/10.1016/j.disc.2008.04.019
András Salamon
Es scheint, dass Ihr Problem in P in zwei Schritten vorliegt: (1) Ihr Problem ist äquivalent zum Finden einer Teilmenge maximaler Größe der Kanten, so dass jeder Scheitelpunkt höchstens zwei Grad hat, und (2) das letztere Problem scheint darin zu liegen P etwa durch Reduktion auf Matching. In Bezug auf (1) ist zu beachten, dass jede Lösung für Ihr Problem mit k Farben einen Teilgraphen mit Grad 2 der Größe k ergibt (behalten Sie nur eine Kante von jeder Farbe bei), und umgekehrt liefert jeder Teilgraphen mit Grad 2 der Größe k eine Lösung mit k Farben (färben Sie einfach jede Kante im Untergraphen in ihrer eigenen Farbe, färben Sie den Rest der Kanten mit einer der Farben). Was vermisse ich?
Neal Young
Es tut mir leid, dass Ihre Antwort mehrere Fehler enthält. Zunächst ist das Problem, "eine Teilmenge der Kanten mit maximaler Größe zu finden, so dass jeder Scheitelpunkt höchstens zwei Grad hat", NP-schwer, Reduktion auf 3SAT (ich weiß nicht wirklich, wie es Reduktion auf Matching haben könnte). Darüber hinaus gibt "ein Teilgraph 2. Grades der Größe k" keine "Lösung mit k Farben", z. B. "Vollständiger Graph". Trotzdem danke.
RIC_Eien
Ja, du hast Recht. Über (2) kann der Schritt "Färben der restlichen Kanten mit einer der Farben" einige Scheitelpunktkanten mit drei Farben ergeben. Separat schlug mir Marek Chrobak den folgenden Algorithmus vor. Ich denke, es gibt eine 3-Annäherung: (i) finde ein Maximum, das zu M passt; (ii) färbe jede Kante in M ​​ihre eigene einzigartige Farbe; (iii) färbe die restlichen Ränder weiß.
Neal Young
@RIC_Eien: Es besteht die Gefahr einer weiteren Verlegenheit. Sind Sie sicher, dass "das Problem, eine Teilmenge der Kanten mit maximaler Größe zu finden, so dass jeder Scheitelpunkt einen Grad von höchstens zwei hat, NP-hart ist"? Wenn G = (V, E) gegeben ist, wird zweigeteiltes G2 = (U, W, E2) erzeugt, wobei für jeden Scheitelpunkt v in V v 'in U und v' 'in W ist und E2 = {(u', w ''): (u, w) in E}. Dann entsprechen die Übereinstimmungen in G2 den Kantenmengen des Grades 2 in G, und die Entsprechung erhält die Größe? (Da jeder k-Zyklus C in G in G2 entweder einem 2-k-Zyklus (wenn k ungerade) oder zwei k-Zyklen (wenn k gerade) entspricht.) Die maximale Anpassung in G2 löst es also. Was vermisse ich dieses Mal?
Neal Young

Antworten:

15

q

Die parametrisierten Komplexitätsaspekte dieses Problems werden in diesem kürzlich erschienenen Artikel angesprochen .

vb le
quelle
Ich habe lange über dieses nette Problem nachgedacht ... Können Sie bitte die Reduzierung beschreiben? Ich habe keinen Zugang zu dem Papier. Vielen Dank!
user13667
5
@ user13667 Sie können die Autoren bitten, Ihnen eine Kopie ihrer Arbeit zuzusenden. Ich denke, sie würden das gerne tun.
VB Le
5
Die damit verbundene Frage, eine Färbung zu finden, die die Anzahl der Farben maximiert und gleichzeitig die Größe der größten Farbgruppe minimiert, wurde ebenfalls untersucht. Zum Beispiel hat diese Masterarbeit mehrere detaillierte Ergebnisse.
Neeldhara