Linear MIM-width of the Square of Trees

Abstract

Graph parameters measure the amount of structure (or lack thereof) in a graph that makes it amenable to being decomposed in a way that facilitates dynamic programming. Graph decompositions and their associated parameters are important both in practice (as a tool for designing robust algorithms for NP-hard problems) and in theory (relating large classes of problems to the graphs on which they are solvable in polynomial time).

Linear MIM-width is a variant of the graph parameter MIM-width, introduced by (Vatshelle 2012). MIM-width is a parameter that is constant for many classes of graphs. Most graph classes which have been shown to have constant MIM-width also have constant linear MIM-width. However, computing the (linear) MIM-width of graphs, or showing that it is hard, has proven to be a huge challenge. To date, the only graph class with unbounded linear MIM-width, whose linear MIM-width can be computed in polynomial time, is the trees (Høgemo et al. 2019). In this follow-up, we show that for any tree $T$ with linear MIM-width $k$, the linear MIM-width of its square $T^2$ always lies between $k$ and
$2k$, and that these bounds are tight for all $k$.