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^[1]. Für die Definition der NLC-Weite ist der Begriff des k-markierten Graphen wichtig:

k-markierter Graph

• Für ein  $\, k \in \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

Einzelnachweise

1. ↑ Egon Wanke: k-NLC Graphs and Polynomial Algorithms, Discrete Applied Mathematics, 54:251-266, 1994