Solving problems on generalized convex graphs via mim-width

BONOMO, FLAVIA; BRETTELL, NICK; MUNARO, ANDREA; PAULUSMA, DANIËL

Halifax

Simposio; 17th Algorithm and Data Structures Symposium (WADS); 2021

A bipartite graph $G=(A,B,E)$ is ${cal H}$-convex, for some family of graphs ${cal H}$, if there exists a graph $Hin {cal H}$ with $V(H)=A$ such that the set of neighbours in $A$ of each $bin B$ induces a connected subgraph of~$H$. Many $mathsf{NP}$-complete problemsbecome polynomial-time solvable for ${mathcal H}$-convex graphs when ${mathcal H}$ is the set of paths. In this case, the class of ${mathcal 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 ${mathcal H}$-convex graphs where (i) ${mathcal H}$ is the set of cycles, or (ii) ${mathcal 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 re-prove 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 ${mathcal H}$-convex graphs is unbounded if ${mathcal 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 ${cal H}$-convex graphs.