3
$\begingroup$

Given a graph $G(V.E,w)$ Here $w: E \mapsto R$. We need to find optimal set of matchings(set of edges that have no common vertices) and $t_i$'s such that after all these matchings, it results in $\forall e \in E, w(e) =0$. Each edge i.e $\forall j \in M_i, w(j) \leftarrow w(j) - t_i$. Weights cannot be negative, hence if you have non integer weights if $w(j) < 0$ then $w(j) = 0$. Hence we need $ [(M_1,t_1), (M_2,t_2), \cdots (M_k,t_k)]$ such that k is minimum. Each $M_i$ reduces the weight of edges chosen in that $M_i$ to be reduced by $t_i$. We need to determine a sequence of Matchings with least length, after which all edge weights become zero. I want to design an algorithm which finds a optimal sequence of Matchings, $t_i$ pairs. I have no idea how to find the optimal matching other than very inefficient algorithms like maximum weight matching,etc and going through every sequence. I am unable to come up with any general algorithm.

Equivalently: given a graph $(V,E)$ with weights on the edges $w:E \to \mathbb{R}$, I want to find a set of matchings $M_1,\dots,M_k$ and non-negative numbers $t_1,\dots,t_k \in \mathbb{R}_{\ge 0}$ such that

$$\sum_{e \in M_i} t_i = w(e)$$

for all $e \in E$, where the sum is taken over all $i$ such that the matching $M_i$ includes the edge $e$. In particular, I want to find the minimal $k$ such that such a solution exists. Is there an efficient algorithm to solve this problem?

|cite|improve this question
$\endgroup$
  • $\begingroup$ I am looking it theoretically. But please assume everything is finite. Any practical perspective is also helpful $\endgroup$ – T.Harish Nov 27 '17 at 20:09
  • $\begingroup$ In the bipartite case, the answer seems to be the trivial lower bound, which is the maximal degree of a vertex. See link.springer.com/content/pdf/10.1007/BF01963619.pdf. $\endgroup$ – Yuval Filmus Nov 28 '17 at 11:46
  • $\begingroup$ I edited your question to add what seems to be an equivalent restatement of your problem. Did I get it right? $\endgroup$ – D.W.♦ Dec 5 '17 at 0:30
  • $\begingroup$ Thanks for the modification. Just want to confirm in it is $$\forall e \in E \space, w(e) = \sum_{e \in M_i} t_i $$ $\endgroup$ – T.Harish Dec 6 '17 at 4:57
  • $\begingroup$ A better clear notation won't be this $$ \forall e \in E \space, w(e) = \sum_{y \in M_i} t_i$$ $\endgroup$ – T.Harish Dec 6 '17 at 5:02

Your Answer

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

Browse other questions tagged or ask your own question.