Algorithms for the $k$-admissible matching number of trees

edit

Background and motivation.

Let $G$ be a tree, let $M$ be a matching of $G$, and let $k = 1,\dots,\nu(G)$, where $\nu(G)$ denotes the matching number of $G$, i.e. the maximum cardinality of a set of pairwise disjoint edges of $G$.

We say that $M$ is a $k$-admissible matching if there exists a sequence $M_1,\dots,M_r$ of non-empty subsets of $M$ satisfying the following conditions.

(a) $M = M_1 \cup \cdots \cup M_r$.\ (b) $M_i \cap M_j = \emptyset$ for all $i \neq j$.\ (c) For all $i \neq j$, if $e_i \in M_i$ and $e_j \in M_j$, then ${e_i,e_j}$ is a gap in $G$, that is, ${e_i,e_j}$ is an induced matching of size $2$.\ (d) $|M_1| + \cdots + |M_r| \le n + k - 1$.

In this case, we say that $M = M_1 \cup \cdots \cup M_r$ is a $k$-admissible partition of $G$.

The $k$-admissible matching number of $G$ is defined by $$ \mathrm{aim}(G,k) = \max{ |M| : M \text{ is a $k$-admissible matching of } G }, $$ for $k = 1,\dots,\nu(G).$

This invariant arises in the study of the regularity of certain squarefree monomial ideals.

Question.

Is there a known algorithm to compute $\mathrm{aim}(G,k)$?

I have searched for existing implementations in SageMath but I could not find any routine for computing this invariant. Apparently, there appear to be no routines for computing even the matching number of a graph. This led me to wonder whether designing an algorithm to compute the matching number itself might already be a nontrivial task, which could in turn explain the lack of available implementations. This turn on my next question:

Is it possible to provide a routine in SageMath that takes as input a tree $G$ and an integer $k$, and returns $\mathrm{aim}(G,k)$ as output?