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

## 1 Answer

You are talking about the independent domination number of the line graph. I have used a similar ILP formulation to find the independent domination number of various graphs:

As shown in some of those posts, the ceiling of the optimal LP objective value provides a lower bound but is not always equal to the optimal ILP objective value. I don't know whether any of those instances arise as line graphs.

• while I see the equivalence of the MMM problem to the independent domination number of the line graph, I couldn't find the corresponding formulation as (or even mention of) an LP when following the links in your answer; did I overlook something? Aug 27, 2022 at 16:51
• One of the links leads to my ILP formulation here: math.stackexchange.com/questions/3374862/…, and this one mentions the LP bound: puzzling.stackexchange.com/questions/109240/… Aug 27, 2022 at 16:54