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?