NLC width

The NLC width is a term from graph theory and assigns a natural number to each undirected graph . Certain difficult problems such as MAX-CUT or the Hamilton cycle problem can be solved in polynomial time on graphs with a limited NLC width .

definition

The concept of the NLC width was introduced by Wanke in 1994. The term k-marked graph is important for the definition of the NLC width :

k-marked graph

• For one   be ${\displaystyle \,k\in \mathbb {N} }$ ${\displaystyle \lbrack k\rbrack \,:=\lbrace 1,\ldots ,k\rbrace }$
• A k-marked graph is a graph whose nodes are marked with a marker image ${\displaystyle \ G=(V_{G},E_{G},lab_{G})\ }$ ${\displaystyle \ (V_{G},E_{G})\ }$ ${\displaystyle \,lab_{G}:V_{G}\rightarrow \lbrack k\rbrack }$
• A graph with exactly one node marked with is denoted by ${\displaystyle i\in \lbrack k\rbrack }$ ${\displaystyle \bullet _{i}}$

definition

The NLC width of a k-marked graph is the smallest natural number so that it belongs to the graph class . ${\displaystyle G}$ ${\displaystyle k,}$ ${\displaystyle G}$ ${\displaystyle NLC_{k}}$

It is defined recursively as follows: ${\displaystyle NLC_{k}}$

1. The -marked graph is for an in ${\displaystyle k}$ ${\displaystyle \bullet _{i}}$ ${\displaystyle i\in \lbrack k\rbrack }$ ${\displaystyle NLC_{k}}$
2. Be and in . Furthermore, let and be vertically disjoint and a relation. Then there is also the -marked graph ${\displaystyle G=(V_{G},E_{G},lab_{G})}$ ${\displaystyle J=(V_{J},E_{J},lab_{J})}$ ${\displaystyle NLC_{k}}$ ${\displaystyle G}$ ${\displaystyle J}$ ${\displaystyle S\subseteq \lbrack k\rbrack ^{2}}$ ${\displaystyle k}$

   ${\displaystyle G\times _{S}J=(V',E',lab')}$

   in , with ${\displaystyle NLC_{k}}$

   ${\displaystyle V'=V_{G}\cup V_{J}}$,

   ${\displaystyle 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 }$ and

   ${\displaystyle lab'(u)={\begin{cases}lab_{G}(u),&{\text{falls }}u\in V_{G}\\lab_{J}(u),&{\text{falls }}u\in V_{J}\end{cases}}}$

   for everyone . ${\displaystyle u\in V'}$

3. Let be a -marked graph and a total function. Then there is also the -marked graph ${\displaystyle G=(V_{G},E_{G},lab_{G})\in NLC_{k}}$ ${\displaystyle k}$ ${\displaystyle R:\lbrack k\rbrack \rightarrow \lbrack k\rbrack }$ ${\displaystyle k}$

   ${\displaystyle \circ _{R}(G)=(V_{G},E_{G},lab')}$

   in with . ${\displaystyle NLC_{k}}$ ${\displaystyle lab'(u)=R(lab(u))\qquad \forall u\in V_{G}}$

example

The following table demonstrates the construction of the "House of Nicholas" graph using the operations defined above:

NLC operation	Representation of the graph
${\displaystyle G_{1}=\bullet _{1}\times _{\lbrace (1,2)\rbrace }\bullet _{2}}$
${\displaystyle G_{2}=\bullet _{3}\times _{\lbrace (3,4)\rbrace }\bullet _{4}}$
${\displaystyle G_{3}=G_{1}\times _{\lbrace (1,3),(1,4),(2,3),(2,4)\rbrace }G_{2}}$
${\displaystyle G_{4}=\circ _{\lbrace (1,1),(2,1),(3,3),(4,3)\rbrace }(G_{3})}$
${\displaystyle G_{Nikolaus}=G_{4}\times _{\lbrace (3,2)\rbrace }\bullet _{2}}$

It is therefore true . still has an NLC expanse of 1 because is a co-graph . ${\displaystyle G_{Nikolaus}\in NLC_{4}}$ ${\displaystyle G_{Nikolaus}}$ ${\displaystyle G_{Nikolaus}}$

NLC range of special graph classes

The NLC widths of the following graph classes can be estimated upwards as follows:

• Each co-graph has an NLC width of 1
• Trees have an NLC width of 3 or less
• Circles have an NLC width of 4 or less

Relation to the size of the clique

For every undirected graph with NLC-width and clique-width the following applies: ${\displaystyle G}$ ${\displaystyle nlcw(G)}$ ${\displaystyle cw(G)}$

${\displaystyle nlcw(G)\leq cw(G)\leq 2\cdot nlcw(G).}$

literature

• Frank Gurski, Irene Rothe, Jörg Rothe, Egon Wanke: Exact algorithms for difficult graph problems , Springer-Verlag, Berlin Heidelberg, 2010, ISBN 978-3-642-04499-1

Individual evidence

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