## Abstract

We define a notion called leftmost separator of size at most k. A leftmost separator of size k is a minimal separator S that separates two given sets of vertices X and Y such that we “cannot move S more towards X” such that |S| remains smaller than the threshold. One of the incentives is that by using leftmost separators we can improve the time complexity of treewidth approximation. Treewidth approximation is a problem which is known to have a linear time FPT algorithm in terms of input size, and only single exponential in terms of the parameter, treewidth. It is not known whether this result can be improved theoretically. However, the coefficient of the parameter k (the treewidth) in the exponent is large. Hence, our goal is to decrease the coefficient of k in the exponent, in order to achieve a more practical algorithm. Hereby, we trade a linear-time algorithm for an O(nlog n) -time algorithm. The previous known O(f(k) nlog n) -time algorithms have dependences of 2^{24} ^{k}k!, 2^{8.766} ^{k}k^{2} (a better analysis shows that it is 2^{7.671} ^{k}k^{2} ), and higher. In this paper, we present an algorithm for treewidth approximation which runs in time O(26.755knlogn), Furthermore, we count the number of leftmost separators and give a tight upper bound for them. We show that the number of leftmost separators of size ≤ k is at most C_{k} _{-} _{1} (Catalan number). Then, we present an algorithm which outputs all leftmost separators in time O(4kkn).

Original language | English (US) |
---|---|

Title of host publication | Combinatorial Optimization and Applications - 15th International Conference, COCOA 2021, Proceedings |

Editors | Ding-Zhu Du, Donglei Du, Chenchen Wu, Dachuan Xu |

Publisher | Springer Science and Business Media Deutschland GmbH |

Pages | 273-287 |

Number of pages | 15 |

ISBN (Print) | 9783030926809 |

DOIs | |

State | Published - 2021 |

Event | 15th Annual International Conference on Combinatorial Optimization and Applications, COCOA 2021 - Tianjin, China Duration: Dec 17 2021 → Dec 19 2021 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 13135 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | 15th Annual International Conference on Combinatorial Optimization and Applications, COCOA 2021 |
---|---|

Country/Territory | China |

City | Tianjin |

Period | 12/17/21 → 12/19/21 |

## All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- General Computer Science