NLC-Weite
# NLC-Weite

Die NLC-Weite ist ein Begriff aus der Graphentheorie und weist jedem ungerichteten Graphen eine natürliche Zahl zu. Auf Graphen mit beschränkter NLC-Weite lassen sich bestimmte schwere Probleme wie zum Beispiel MAX-CUT oder das Hamiltonkreisproblem in polynomieller Zeit lösen.

## Definition

Der Begriff der NLC-Weite wurde von 1994 von Wanke eingeführt. Für die Definition der NLC-Weite ist der Begriff des k-markierten Graphen wichtig:

### 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

### Definition

Die NLC-Weite eines k-markierten Graphen $G$ ist die kleinste natürliche Zahl $k,$ sodass $G$ in der Graphklasse $NLC_{k}$ liegt.

Dabei ist $NLC_{k}$ wie folgt rekursiv definiert:

* Der $k$-markierte Graph $\bullet _{i}$ ist für ein $i\in \lbrack k\rbrack$ in $NLC_{k}$
* Seien $G=(V_{G},E_{G},lab_{G})$ und $J=(V_{J},E_{J},lab_{J})$ in $NLC_{k}$. Weiterhin seien $G$ und $J$ knotendisjunkt und $S\subseteq \lbrack k\rbrack ^{2}$ eine Relation. Dann ist auch der $k$-markierte Graph

    $G\times _{S}J=(V',E',lab')$
    in $NLC_{k}$, mit
    $V'=V_{G}\cup V_{J}$,
    $E'=E_{G}\cup E_{J}\cup \lbrace \lbrace u,v\rbrace |u\in V_{G},v\in V_{J},(lab_{G}(u),lab_{J}(v))\in S\rbrace$ und
    $lab'(u)={\begin{cases}lab_{G}(u),&{\text{falls }}u\in V_{G}\\lab_{J}(u),&{\text{falls }}u\in V_{J}\end{cases}}$
    für alle $u\in V'$.
* Seien $G=(V_{G},E_{G},lab_{G})\in NLC_{k}$ ein $k$-markierter Graph und $R:\lbrack k\rbrack \rightarrow \lbrack k\rbrack$ eine totale Funktion. Dann ist auch der $k$-markierte Graph

    $\circ _{R}(G)=(V_{G},E_{G},lab')$
    in $NLC_{k}$ mit $lab'(u)=R(lab(u))\qquad \forall u\in V_{G}$.

## Beispiel

Die nachfolgende Tabelle demonstriert die Konstruktion des "Haus vom Nikolaus"-Graphen mithilfe der oben definierten Operationen:

* NLC-Operation
* $G_{1}=\bullet _{1}\times _{\lbrace (1,2)\rbrace }\bullet _{2}$
* $G_{2}=\bullet _{3}\times _{\lbrace (3,4)\rbrace }\bullet _{4}$
* $G_{3}=G_{1}\times _{\lbrace (1,3),(1,4),(2,3),(2,4)\rbrace }G_{2}$
* $G_{4}=\circ _{\lbrace (1,1),(2,1),(3,3),(4,3)\rbrace }(G_{3})$
* $G_{Nikolaus}=G_{4}\times _{\lbrace (3,2)\rbrace }\bullet _{2}$

Es gilt somit $G_{Nikolaus}\in NLC_{4}$. $G_{Nikolaus}$ hat weiterhin eine NLC-Weite von 1, da $G_{Nikolaus}$ ein Co-Graph ist.

## NLC-Weite spezieller Graphklassen

Die NLC-Weiten der folgenden Graphklassen lassen sich wie folgt nach oben abschätzen:

* Jeder Co-Graph hat eine NLC-Weite von 1
* Bäume haben eine NLC-Weite von höchstens 3
* Kreise haben eine NLC-Weite von höchstens 4

## Zusammenhang zur Cliquenweite

Für jeden ungerichteten Graphen $G$ mit NLC-Weite $nlcw(G)$ und Cliquenweite $cw(G)$ gilt:

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