Solving problems on generalized convex graphs via mim-width

A bipartite graph G = (A, B, E) is 7-t-convex for some family of graphs 7-t if there exists a graph H is an element of 7-t with V (H) = A such that the neighbours in A of each b is an element of B induce a connected subgraph of H. Many NP-complete problems are polynomial-time solvable for 7-t-convex graphs when 7-t is the set of paths. The underlying reason is that the class has bounded mim-width. We extend this result to families of 7-t-convex graphs where 7-t is the set of cycles, or 7-t is the set of trees with bounded maximum degree and a bounded number of vertices of degree at least 3. As a consequence, we strengthen many known results via one general and short proof. We also show that the mim-width of 7-t-convex graphs is unbounded if 7-t is the set of trees with arbitrarily large maximum degree or an arbitrarily large number of vertices of degree at least 3. (c) 2023 The Author(s). Published by Elsevier Inc. This is an open access article under the CC BY license (http://creativecommons .org /licenses /by /4 .0/).

Automated summary

This article discusses the convexity and mim-width of bipartite graphs, and it proves that for certain families of graphs 7-t, the 7-t-convex graphs can be solved in polynomial time for NP-complete problems. It also explores the bounded and unbounded mim-width of 7-t-convex graphs for different sets 7-t.