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:

1. Der $k$-markierte Graph $\bullet _{i}$ ist für ein $i\in \lbrack k\rbrack$ in $NLC_{k}$
2. 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'$.

3. 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	Darstellung des Graphen
$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).$

Literatur

• 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