0
$\begingroup$

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$

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.