2
$\begingroup$

Let $G(V,E)$ be a graph (not necessarily bipartite), where edge $e \in E$ has weight $w_e$ (non-negative real). Then one can write the LP relaxation for maximum weight perfect matching as follows $$ \text{maximize}~~\sum_{e\in E} w_e x_e \\ \text{subject to}~~\sum_{e\in E: v\in e}x_e=1\text{ for all }v\in V \\ 0\le x_{e}\le 1\text{ for }e\in E. $$ In the corresponding Integer Program $x_e$ is a binary variable s.t. $$ x_e = \begin{cases} 1 \text{ if } e \text{ is in the perfect matching}\\ 0 \text{ otherwise} \end{cases} $$ I am unable to come up with an example where given $G$ has a perfect matching, the LP does not have an all integral optimal solution $x_e^{\text{*}}$. I tried taking small examples with odd length cycles, though there was a fractional optimal for the LP, there was an all integral optimal as well (in the examples I took).
I am aware that for bipartite graphs if the LP is feasible, then there always exists an all integral optimal for the LP. Does it hold for general graphs as well? If not I would appreciate hints so I can come up with such an example.

$\endgroup$
1
  • $\begingroup$ @Dmitry There is equality because I want perfect matching ie. each vertex should be incident to exactly one edge in the matching. For a triangle, perfect matching does not exist. I want an example of a graph where I know a perfect matching exists and the LP relaxation does not have an all integral optimal $\endgroup$
    – sashas
    Mar 13 at 20:40
2
$\begingroup$

Consider the graph consisting of two triangles $123,456$ connected by an edge $34$. The graph has a unique perfect matching $12,34,56$. Give the edges of the triangles weight $1$, and the edge $34$ weight $\epsilon$. The maximum weight perfect matching has weight $2+\epsilon$. Conversely, the fractional matching giving a weight of $1/2$ to each edge of each triangle has weight $3$.

$\endgroup$
1
  • $\begingroup$ I'm amazed how frequently it happens that there is a question which nobody touches for hour(s), and then several people post almost the same solution almost simultaneously. $\endgroup$
    – user114966
    Mar 13 at 21:45
3
$\begingroup$

enter image description here

AB, CD, EF is the unique perfect matching

Assigning $x_e = 0.5$ to all edges except CD gives the optimal LP solution.

$\endgroup$

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.