Cliquenweite
# Cliquenweite

Die Cliquenweite ist ein Begriff aus der Graphentheorie und ordnet jedem ungerichteten Graphen $G=(V,E)$ 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 $O(f(k)\cdot n)$ lösen, was für konstante $k$ 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

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

### k-markierter Graph

* Für ein $k\in \mathbb {N}$ sei $\lbrack k\rbrack :=\lbrace 1,\ldots ,k\rbrace$
* Ein k-markierter Graph $\ G=(V_{G},E_{G},lab_{G})\$ ist ein Graph $\ (V_{G},E_{G})\$, dessen Knoten mit einer Markierungsabbildung $lab_{G}:V_{G}\rightarrow \lbrack k\rbrack$ markiert werden
* Ein Graph mit genau einem mit $i\in \lbrack k\rbrack$ markierten Knoten wird mit $\bullet _{i}$ bezeichnet

### Cliquenweite

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

* Der $k$-markierte Graph $\bullet _{i}$ (ein Graph bestehend aus einem Knoten mit Markierung $i$) ist in $CW_{k}$ für alle $i=1..k$
* Seien $G=(V_{G},E_{G},lab_{G})$ und $J=(V_{J},E_{J},lab_{J})$ knotendisjunkte $k$-markierte Graphen. Dann ist ihre disjunkte Vereinigung $G\oplus J=(V',E',lab')$ in $CW_{k}$, mit
   * $V':=V_{G}\cup V_{J}$
   * $E':=E_{G}\cup E_{J}$
   * $lab'(u)={\begin{cases}lab_{G}(u),&{\text{falls }}u\in V_{G},\\lab_{J}(u),&{\text{falls }}u\in V_{J}\end{cases}}$ $\forall u\in V'$
* Seien $i,j\in \lbrack k\rbrack$ mit $i\neq j$ und $G=(V_{G},E_{G},lab_{G})$ ein $k$-markierter Graph. Es sind
   * der $k$-markierte Graph, der aus G entsteht, indem die Markierung aller mit $i$ markierten Knoten durch eine Markierung mit $j$ ersetzt wird $\rho _{i\rightarrow j}(G)=(V_{G},E_{G},lab')$ in $CW_{k}$ mit $lab'(u)={\begin{cases}lab_{G}(u),&{\text{falls }}lab_{G}(u)\neq i,\\j,&{\text{falls }}lab_{G}(u)=i\end{cases}}$ $\forall u\in V'$
   * der $k$-markierte Graph, der aus G entsteht, indem alle mit $i$ markierten Knoten verbunden werden mit allen Knoten, die mit $j$ markiert sind. $\eta _{i,j}(G)=(V_{G},E',lab_{G})$ in $CW_{k}$ mit $E'=E_{G}\cup \lbrace \lbrace u,v\rbrace |lab(u)=i,lab(v)=j\rbrace$

Die Cliquenweite eines markierten Graphen $G$ ist die kleinste natürliche Zahl $k$ mit $G\in CW_{k}$ und wird mit $cw(G)$ bezeichnet.

Ein Ausdruck $X$, der sich aus den Operationen $\bullet _{i}$, $\oplus$, $\rho _{i\rightarrow j}$ und $\eta _{i,j}$, wobei $i,j\in \lbrack k\rbrack$, zusammensetzt, wird als Cliquenweite-k-Ausdruck oder k-Ausdruck bezeichnet.

## Beispiel

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

* Cliquenweite-Operation
* $G_{1}=\bullet _{1}$
* $G_{2}=\bullet _{2}$
* $G_{3}=G_{1}\oplus G_{2}$
* $G_{4}=\eta _{1,2}(G_{3})$
* $G_{5}=G_{4}\oplus G_{4}$
* $G_{6}=G_{5}\oplus \bullet _{3}$
* $G_{7}=\eta _{1,3}(G_{6})$
* $G_{8}=\rho _{3\rightarrow 1}(G_{7})$
* $G_{9}=G_{8}\oplus \bullet _{3}$
* $C_{6}=\eta _{2,3}(G_{9})$

Der zugehörige $3$-Ausdruck ist

    $X=\eta _{2,3}(\rho _{3\rightarrow 1}(\eta _{1,3}(\eta (\bullet _{1}\oplus \bullet _{2})\oplus \eta (\bullet _{1}\oplus \bullet _{2})\oplus \bullet _{3}))\oplus \bullet _{3})$

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

## Cliquenweite spezieller Graphklassen

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:

* Jeder vollständige Graph hat eine Cliquenweite von höchstens 2
* Jeder Weg hat eine Cliquenweite von höchstens 3
* Auch Bäume und distanzerhaltende Graphen haben eine Cliquenweite von höchstens 3

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

Es existieren mehrere Zusammenhänge zwischen der Cliquenweite $cw(G)$ und der Baumweite $tw(G)$ eines ungerichteten Graphen $G$.

Die folgende Aussage zeigt, dass sich $cw(G)$ durch $tw(G)$ nach oben abschätzen lässt:

    $cw(G)\leq 3\cdot 2^{tw(G)-1}$

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 $K_{n}$ mit $n$ Knoten hat eine Baumweite von $n-1$ und eine Cliquenweite von höchstens 2. Somit gilt für alle $n$ mit $n\geq 4$:

    $cw(K_{n})<tw(K_{n})$.

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

Besitzt $G$ keinen vollständig bipartiten Graphen $K_{n,n}$ als Teilgraphen, so gilt die folgende Aussage:

    $tw(G)\leq 3\cdot (n-1)\cdot cw(G)-1$

## Zusammenhang zwischen Cliquenweite und NLC-Weite

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

    $nlcw(G)\leq cw(G)\leq 2\cdot nlcw(G)$
