Die Cliquenweite ist ein Begriff aus der Graphentheorie und ordnet jedem ungerichteten Graphen eine natürliche Zahl zu. Sie ist daher ein Graphparameter. Mit Hilfe eines k-Ausdrucks (s. u.) lassen sich viele NP-vollständige Probleme wie zum Beispiel HAMILTONKREIS oder CLIQUE und das damit eng verwandte UNABHÄNGIGE MENGE in Zeit lösen, was für konstante eine lineare Laufzeit ist. Da jedoch nicht bekannt ist, ob ein k-Ausdruck hinreichend schnell berechnet werden kann, ist es zur Zeit unklar, ob man hieraus folgern kann, dass diese Probleme auf Graphen mit beschränkter Cliquenweite effizient zu lösen sind.

Definition

Bearbeiten

Der Begriff der Cliquenweite eines Graphen wurde erstmals von Bruno Courcelle und Stephan Olariu eingeführt[1]. Für die Definition der Cliquenweite muss zunächst der Begriff des k-markierten Graphen eingeführt werden:

k-markierter Graph

Bearbeiten
  • Für ein   sei  
  • Ein k-markierter Graph   ist ein Graph  , dessen Knoten mit einer Markierungsabbildung   markiert werden
  • Ein Graph mit genau einem mit   markierten Knoten wird mit   bezeichnet

Cliquenweite

Bearbeiten

Ein  -markierter Graph   hat eine Cliquenweite von höchstens  , wenn   in der Graphklasse   enthalten ist. Dabei ist   induktiv wie folgt definiert:

  1. Der  -markierte Graph   (ein Graph bestehend aus einem Knoten mit Markierung  ) ist in   für alle  
  2. Seien   und   knotendisjunkte  -markierte Graphen. Dann ist ihre disjunkte Vereinigung   in  , mit
    1.  
    2.  
    3.       
  3. Seien   mit   und   ein  -markierter Graph. Es sind
    1. der  -markierte Graph, der aus G entsteht, indem die Markierung aller mit   markierten Knoten durch eine Markierung mit   ersetzt wird   in   mit       
    2. der  -markierte Graph, der aus G entsteht, indem alle mit   markierten Knoten verbunden werden mit allen Knoten, die mit   markiert sind.   in   mit  

Die Cliquenweite eines markierten Graphen   ist die kleinste natürliche Zahl   mit   und wird mit   bezeichnet.

Ein Ausdruck  , der sich aus den Operationen  ,  ,   und  , wobei  , zusammensetzt, wird als Cliquenweite-k-Ausdruck oder k-Ausdruck bezeichnet.

Beispiel

Bearbeiten

Der ungerichtete Graph mit 6 Knoten   hat eine Cliquenweite von 3, da er sich mit den folgenden Operationen erzeugen lässt:

 
3-Ausdrucksbaum für die Konstruktion des 
Cliquenweite-Operation Visualisierung des Graphen
   
   
   
   
   
   
   
   
   
   

Der zugehörige  -Ausdruck ist

 

Rechts ist der entsprechende 3-Ausdrucksbaum für   abgebildet.

Cliquenweite spezieller Graphklassen

Bearbeiten

Obwohl das Bestimmen der Cliquenweite eines Graphen im Allgemeinen NP-vollständig ist, lässt sich die Cliquenweite von gewissen Graphen mit speziellen Eigenschaften zumindest nach oben abschätzen. Es existieren die folgenden Zusammenhänge:

Weiterhin ist bekannt, dass Co-Graphen eine Cliquenweite von höchstens 2 haben und dass jeder Graph mit einer Cliquenweite von höchstens 2 ein Co-Graph ist.

Zusammenhang zwischen Cliquenweite und Baumweite

Bearbeiten

Es existieren mehrere Zusammenhänge zwischen der Cliquenweite   und der Baumweite   eines ungerichteten Graphen  .

Die folgende Aussage zeigt, dass sich   durch   nach oben abschätzen lässt[2]:

 

Umgekehrt hingegen lässt sich die Baumweite eines Graphen im Allgemeinen nicht durch seine Cliquenweite beschränken, wie man sich leicht am Beispiel vollständiger Graphen überlegen kann:

Der vollständige Graph   mit   Knoten hat eine Baumweite von   und eine Cliquenweite von höchstens 2. Somit gilt für alle   mit  :

 .

Allerdings lässt sich unter gewissen Umständen auch die Baumweite durch die Cliquenweite nach oben abschätzen.

Besitzt   keinen vollständig bipartiten Graphen   als Teilgraphen, so gilt die folgende Aussage[3]:

 

Zusammenhang zwischen Cliquenweite und NLC-Weite

Bearbeiten

Die Cliquenweite lässt sich sowohl nach unten als auch nach oben durch die NLC-Weite   abschätzen:

 

Einzelnachweise

Bearbeiten
  1. Bruno Courcelle, Stephan Olariu: Upper bounds to the clique width of graphs, Discrete Applied Mathematics 101 (1–3): 77–144, 2000, doi:10.1016/S0166-218X(99)00184-5
  2. Derek Corneil, Udi Rotics: On the Relationship between Clique-Width and Treewidth, Lecture Notes in Computer Science, 2001, Volume 2204/2001, 78–90, doi:10.1007/3-540-45477-2_9
  3. Frank Gurski, Egon Wanke: The Tree-Width of Clique-Width Bounded Graphs without  , Lecture Notes in Computer Science, 2000, Volume 1928/2000, 221–232, doi:10.1007/3-540-40064-8_19

Literatur

Bearbeiten
  • Bruno Courcelle, Stephan Olariu: Upper bounds to the clique width of graphs, Discrete Applied Mathematics 101 (1–3): 77–144, 2000, doi:10.1016/S0166-218X(99)00184-5
  • Frank Gurski, Irene Rothe, Jörg Rothe, Egon Wanke: Exakte Algorithmen für schwere Graphenprobleme, Springer-Verlag, Berlin Heidelberg, 2010, ISBN 978-3-642-04499-1
  • Jörg Rothe: Komplexitätstheorie und Kryptologie, Springer-Verlag, Berlin Heidelberg, 2008, ISBN 978-3-540-79744-9