Skip to main content

Research Repository

Advanced Search

Solving problems on generalized convex graphs via mim-width

Bonomo-Braberman, F.; Brettell, N.; Munaro, A.; Paulusma, D.

Solving problems on generalized convex graphs via mim-width Thumbnail


Authors

F. Bonomo-Braberman

N. Brettell

A. Munaro



Contributors

Anna Lubiw
Editor

Mohammad Salavatipour
Editor

Meng He
Editor

Abstract

A bipartite graph G = (A, B, E) is H-convex, for some family of graphs H, if there exists a graph H ∈ H with V (H) = A such that the set of neighbours in A of each b ∈ B induces a connected subgraph of H. Many NP-complete problems become polynomial-time solvable for H-convex graphs when H is the set of paths. In this case, the class of H-convex graphs is known as the class of convex graphs. The underlying reason is that this class has bounded mim-width. We extend the latter result to families of H-convex graphs where (i) H is the set of cycles, or (ii) H is the set of trees with bounded maximum degree and a bounded number of vertices of degree at least 3. As a consequence, we can reprove and strengthen a large number of results on generalized convex graphs known in the literature. To complement result (ii), we show that the mim-width of H-convex graphs is unbounded if H is the set of trees with arbitrarily large maximum degree or an arbitrarily large number of vertices of degree at least 3. In this way we are able to determine complexity dichotomies for the aforementioned graph problems. Afterwards we perform a more refined width-parameter analysis, which shows even more clearly which width parameters are bounded for classes of H-convex graphs.

Citation

Bonomo-Braberman, F., Brettell, N., Munaro, A., & Paulusma, D. (2021). Solving problems on generalized convex graphs via mim-width. In A. Lubiw, M. Salavatipour, & M. He (Eds.), Algorithms and Data Structures: 17th International Symposium, WADS 2021, Virtual Event, August 9–11, 2021, Proceedings (200-214). https://doi.org/10.1007/978-3-030-83508-8_15

Acceptance Date Apr 13, 2021
Online Publication Date Jul 31, 2021
Publication Date 2021
Deposit Date May 28, 2021
Publicly Available Date Jun 1, 2021
Publisher Springer Verlag
Volume 12808
Pages 200-214
Series Title Lecture Notes in Computer Science
Series ISSN 0302-9743
Book Title Algorithms and Data Structures: 17th International Symposium, WADS 2021, Virtual Event, August 9–11, 2021, Proceedings
ISBN 9783030835071
DOI https://doi.org/10.1007/978-3-030-83508-8_15
Public URL https://durham-repository.worktribe.com/output/1625344

Files





You might also like



Downloadable Citations