# $\mathrm{ILP}$-formulation for Minimum Maximal Matching (MMM) Problem

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$$