Despite some online searching I couldn't find examples of dedicated Integer Linear Programs ($\mathrm{ILP}$s) for determining smallest matchings, that are not contained in a larger one.
It seems that the following could be an example of such an $\mathrm{ILP}$:
$\quad\quad\min\quad \sum\limits_{\lbrace i,j\rbrace\subset \lbrace 1,\dots,n\rbrace}x_{\lbrace i,j\rbrace}$,
s.t.
$x_{\lbrace i,j\rbrace}\in\lbrace 0,1\rbrace$
$x_{\lbrace i,j\rbrace}+\sum\limits_{h\ne i}x_{\lbrace h,j\rbrace}+\sum\limits_{k\ne j}x_{\lbrace i,k\rbrace}\ \in\ \lbrace 1,2\rbrace,\quad\forall \lbrace h,i,j,k\rbrace\subseteq\lbrace 1,\dots,n\rbrace$
Questions:
- has the above $\mathrm{ILP}$ formulation of the MMM problem already appeared in the literature?
- what is know resp. can be said, about the integrality gap of the relaxed $\mathrm{LP}$-formulation, i.e. when
$\quad\quad\min\quad \sum\limits_{\lbrace i,j\rbrace\subset \lbrace 1,\dots,n\rbrace}x_{\lbrace i,j\rbrace}$,$\quad$ s.t.
$\quad x_{\lbrace i,j\rbrace}\in\left[ 0,1\right]$
$\quad x_{\lbrace i,j\rbrace}+\sum\limits_{h\ne i}x_{\lbrace h,j\rbrace}+\sum\limits_{k\ne j}x_{\lbrace i,k\rbrace}\ \in\ \left[1,2\right],\quad\forall \lbrace h,i,j,k\rbrace\subseteq\lbrace 1,\dots,n\rbrace$
