## Counting in Graphs of Bounded Treewidth

- Many graph counting problems are NP-hard but can be solved in linear or polynomial time with a dynamic programming algorithm when we restrict the input graph with bounded treewidth or pathwidth. We introduce the concepts of tree decomposition and path decomposition and convert them into a nice tree decomposition and a nice path decomposition, respectively, which are more convenient for our problem. We consider a graph G with n vertices with treewidth or pathwidth at most k (partial k-tree) and solve vertex partitioning problems such as counting the total number of independent sets, connected spanning subgraphs, connected induced subgraphs, and vertex colorings of j colors. We describe the general framework of a fixed parameter (k) tractable algorithm that solves all the mentioned counting problems and analyzes its complexity. This means that for a fixed treewidth or pathwidth k, the time complexity of the algorithm is polynomial in the number of vertices n, though it might be exponential in k.

Author: | Md Kamruzzaman |
---|---|

Advisor: | Peter Tittmann, Klaus Dohmen |

Document Type: | Master's Thesis |

Language: | English |

Date of Publication (online): | 2024/08/09 |

Year of first Publication: | 2024 |

Publishing Institution: | Hochschule Mittweida |

Granting Institution: | Hochschule Mittweida |

Date of final exam: | 2024/07/23 |

Release Date: | 2024/08/09 |

GND Keyword: | Graphentheorie; Algorithmus |

Page Number: | 49 |

Institutes: | Angewandte Computer‐ und Biowissenschaften |

DDC classes: | 511.5 Graphentheorie |

Open Access: | Frei zugänglich |