Cookies

We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.


Durham Research Online
You are in:

Solving problems on generalized convex graphs via mim-width

Bonomo-Braberman, F. and Brettell, N. and Munaro, A. and Paulusma, D. (2021) 'Solving problems on generalized convex graphs via mim-width.', WADS 2021 Halifax, Nova Scotia, 9-11 Aug 2021.

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.

Item Type:Conference item (Paper)
Full text:Publisher-imposed embargo
(AM) Accepted Manuscript
File format - PDF
(491Kb)
Status:Peer-reviewed
Publisher Web site:https://projects.cs.dal.ca/wads2021/
Date accepted:13 April 2021
Date deposited:01 June 2021
Date of first online publication:2021
Date first made open access:No date available

Save or Share this output

Export:
Export
Look up in GoogleScholar