Max-Clique im Liniendiagramm des Hypergraphen

Angenommen, wir haben einen Multigraph (später einen Multihypergraphen). Eine Kantenclique ist eine Reihe von Kanten, die sich alle paarweise schneiden (mindestens einen gemeinsamen Scheitelpunkt haben). Dann fällt jede Kantenclique in einem Multigraph immer in eine von zwei Kategorien:$C$

• Ein Stern : Es gibt einen Scheitelpunkt, so dass jede Kante von enthält$C$
• Ein Dreieck : Es gibt drei Eckpunkte, so dass jede Kante von zwischen zwei von ihnen verläuft$C$

Dies führt zu einem einfachen -Zeitalgorithmus zur Berechnung der größten Kantenclique.$O(n^3)$

Ich bin mir ziemlich sicher, dass man allgemeiner zeigen kann, dass man für jedes in Multihypergraphen mit maximaler Kantengröße r einen bestimmten Struktursatz für Hyperedge-Cliquen beweisen und einen Polynomzeitalgorithmus erhalten kann, um die maximale Clique zu finden.$r$$r$

Ist etwas zu diesem Ergebnis bekannt? Außerdem ist der Algorithmus, an den ich denke, ein Polynom mit extrem hohem Grad. Es wäre schön, etwas mit Laufzeit oder besser zu bekommen.$n^{\mathrm{poly}(r)}$

Ich fand das interessant, da die maximale Kantenclique eine Untergrenze der kantenchromatischen Zahl (auch bekannt als chromatischer Index) ist.

Bearbeiten: Im Cross-Post führt die Referenz über Kernel zu einem -Zeitalgorithmus: Erraten Sie den Kernel und erraten Sie die Beschränkung der Clique auf den Kernel.$2^{2^{\mathrm{exp}(r)}}n^{\mathrm{exp}(r)}$

Jeder Graph G ist ein Liniendiagramm eines Hypergraphen, zum Beispiel derjenige, dessen Scheitelpunkte die Kanten von G als Eckpunkte und die jedem Scheitelpunkt von G benachbarten Kantenmengen als Hyperkanten haben. Daher kann das Auffinden von Cliquen in Liniendiagrammen von Hypergraphen nicht einfacher sein als das Auffinden von Cliquen in beliebigen Diagrammen.

$r$$G$$r$$n^{poly(r)}$