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.
$\begingroup$
$\endgroup$
1
asked Mar 13, 2021 at 20:21
-
$\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$– advocateofnoneCommented Mar 13, 2021 at 20:40
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
1
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$.
answered Mar 13, 2021 at 21:41
-
$\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$– user114966Commented Mar 13, 2021 at 21:45
$\begingroup$
$\endgroup$
AB, CD, EF is the unique perfect matching
Assigning $x_e = 0.5$ to all edges except CD gives the optimal LP solution.