Path length

The path length or distance is a term from graph theory . It says how “ path- like” a graph is. Since many algorithms run efficiently on paths (or path decompositions) that do not on general graphs, it is interesting to know the path width. A related term is the tree width .

Formal definition

The path width of a graph G is defined as the smallest width of all path decompositions (tree decompositions that form a path) of G.

A path decomposition of is a pair , where a path is and a family of subsets of , one for each node in such that: ${\displaystyle G=(V,E)}$ ${\displaystyle (X,T)}$ ${\displaystyle T=(I,F)}$ ${\displaystyle X=\{X_{i}|i\in I\}}$ ${\displaystyle V}$ ${\displaystyle I}$

• ${\displaystyle \bigcup _{i\in I}X_{i}=V}$.
• There is one with for all edges . ${\displaystyle (v,w)\in E}$ ${\displaystyle i\in I}$ ${\displaystyle v,w\in X_{i}}$
• For everyone , if there is on the path from to in , then . ${\displaystyle i,j,k\in I}$ ${\displaystyle j}$ ${\displaystyle i}$ ${\displaystyle k}$ ${\displaystyle T}$ ${\displaystyle X_{i}\cap X_{k}\subseteq X_{j}}$

Explanation

Expressed more clearly, the nodes of the graph are distributed in buckets or bags, which are arranged one after the other in a path.

The following rules apply:

• Every knot out is in at least one pocket, ${\displaystyle V}$
• the two end nodes of each edge are together in at least one pocket and
• for each knot , all the pockets that contain it follow one another. ${\displaystyle v\in V}$

The breadth of a path decomposition is the maximum number of nodes in a single pocket minus 1.

literature

• Reinhard Diestel: graph theory. 4th edition. Springer-Verlag, Berlin Heidelberg 2010, ISBN 978-3-642-14911-5 .
• 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 .