A bipartite graph $G=(A,B,E)$ is $\mathcal{H}$-convex for some family of graphs $\mathcal{H}$ if there exists a graph $H \in \mathcal{H}$ with $V(H)=A$ such that the neighbours in $A$ of each $b \in B$ induce a connected subgraph of $H$. Many $\mathsf{NP}$-complete problems are polynomial-time solvable for $\mathcal{H}$-convex graphs when $\mathcal{H}$ is the set of paths. The underlying reason is that the class has bounded mim-width. We extend this result to families of $\mathcal{H}$-convex graphs where $\mathcal{H}$ is the set of cycles, or $\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 strengthen many known results via one general and short proof. We also 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$.

Solving problems on generalized convex graphs via mim-width / Bonomo-Braberman, F.; Brettell, N.; Munaro, A.; Paulusma, D.. - In: JOURNAL OF COMPUTER AND SYSTEM SCIENCES. - ISSN 0022-0000. - 140:(2024). [10.1016/j.jcss.2023.103493]

Solving problems on generalized convex graphs via mim-width

Munaro A.;
2024-01-01

Abstract

A bipartite graph $G=(A,B,E)$ is $\mathcal{H}$-convex for some family of graphs $\mathcal{H}$ if there exists a graph $H \in \mathcal{H}$ with $V(H)=A$ such that the neighbours in $A$ of each $b \in B$ induce a connected subgraph of $H$. Many $\mathsf{NP}$-complete problems are polynomial-time solvable for $\mathcal{H}$-convex graphs when $\mathcal{H}$ is the set of paths. The underlying reason is that the class has bounded mim-width. We extend this result to families of $\mathcal{H}$-convex graphs where $\mathcal{H}$ is the set of cycles, or $\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 strengthen many known results via one general and short proof. We also 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$.
2024
Solving problems on generalized convex graphs via mim-width / Bonomo-Braberman, F.; Brettell, N.; Munaro, A.; Paulusma, D.. - In: JOURNAL OF COMPUTER AND SYSTEM SCIENCES. - ISSN 0022-0000. - 140:(2024). [10.1016/j.jcss.2023.103493]
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11381/2965393
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? ND
social impact