<p>One should be able to get a simple constant factor approximation as follows. Partition the nodes of the graph randomly into two sets $V_1$ and $V_2$ - each node decides with probability half to go to $V_1$ or not. Ignore all the edges with both end points in the same side. We are left with a bipartite graph. Now solve a bipartite matching problem where the nodes in $V_1$ have capacity $1$ and the nodes on the right have no capacity limit. This gives a collection of stars. Analysis is left as an easy exercise :).</p>

CC BY-SA 3.0
2011-08-24T14:21:52.593Z
Thank you very much. :) the capacity may be 2 because the constraint is $< 3$. I find your algorithm is $2-approximation$ and could be easily derandomized. I am keep looking for parameterized reduction rules. Hope the problem is FPT.
Peng Zhang
CC BY-SA 3.0
2011-08-24T16:49:48.640Z
I am not sure FPT is a good framework for this problem. Suppose you want to check if the optimum value is at least $k$. We can assume that the maximum degree in the graph is less than $k$, otherwise the answer is yes. If maximum degree is less than $k$ there will be a matching of size $\Omega(n/k)$ in the graph assuming it has no isolated vertices. Thus for all value of $k < \sqrt{n}$ one can easily check if the optimum value is at least $k$.
Chandra Chekuri
CC BY-SA 3.0
2011-08-27T17:32:10.407Z
FPT with respect to the treewidth of $G$ *should* exisit. 2 reasons: **NO.1** The problem could be described as a MSO-formula. **No.2** The problem when restricted on trees is in P. I am thinking about the dynamic programming with the help of treewidth. Hope for good result.

[MSO-formula]:www.labri.fr/perso/courcell/Conferences/ExpoBerlin2007.pdf
Peng Zhang
CC BY-SA 3.0
2011-08-23T16:10:10.637Z
2011-08-23T16:10:10.637Z
Chandra Chekuri
<p>The case of <strong>trees</strong> and a constant $c$ seems to admit a straightforward dynamic programming algorithm.</p>

<p>You root your tree arbitrarily. You will start from the leaf nodes and propagate information towards the root. You will keep track of the following pieces of information for each subtree; here $u$ is a node and $T(u)$ is the subtree rooted at $u$:</p>

<ul>
<li>$M_1(u)$ = best matching in $T(u)$ if $u$ has unlimited capacity,</li>
<li>$M_2(u)$ = best matching in $T(u)$ if $u$ has capacity $c - 1$,</li>
<li>$M_3(u)$ = best matching in $T(u)$ if $u$ has capacity $c$.</li>
</ul>

<p>Note that $M_1(u)$ and $M_2(u)$ can be extended by adding the edge $(v,u)$, where $v$ is the parent of $u$.</p>

<p>All of these values are trivial to compute for a leaf node. Once you have computed these values for all subtrees of a node $v$, you can compute them for $v$; let $C$ consist of the children of $v$:</p>

<ul>
<li>$M_1(v)$: For each $u \in C$ of $v$ we take either $M_2(u) + (v,u)$ or $M_3(u)$, whichever is better.</li>
<li>$M_2(v)$: We check all subsets $S \subseteq C$ of size at most $c - 2$. For each child $u \in S$ we take $M_1(u) + (v,u)$ or $M_2(u) + (v,u)$, whichever is better. For each child $u \notin S$ we take $M_1(u)$, $M_2(u)$, or $M_3(u)$, whichever is best.</li>
<li>$M_3(v)$: Similar to $M_2(v)$, but we consider subsets of size at most $c - 1$.</li>
</ul>

<p>Everything is polynomial if $c$ is a constant.</p>

CC BY-SA 3.0
2011-08-27T11:54:29.587Z
Thanks a lot. There is an improvement on your DP. Counting $M_2(v)$ and $M_3(v)$ could be done in $|C|\times(c-1)$ time with a knapsack style DP. Saving the time for enumerating all subsets $S\subseteq C$.
Peng Zhang
CC BY-SA 3.0
2011-08-27T12:05:54.077Z
@Peng: Right, I guess that shows that it is in P even if $c$ is part of input.
Jukka Suomela
CC BY-SA 3.0
2011-08-27T10:28:42.240Z
2011-08-27T10:28:42.240Z
Jukka Suomela
<p>The question is asked first at <a href="https://cstheory.stackexchange.com/questions/7878/an-interesting-variant-of-maximum-matching-problem">here</a>. It described what the problem is and a trival greedy algorithm. Also the accepted answer gave a proof of its NP-completeness.</p>
<blockquote>
<p><strong>Problem</strong>: Given a graph <span class="math-container">$G(V,E)$</span>, Find a subset of edges <span class="math-container">$M \subseteq E$</span>. For each edge <span class="math-container">$(u,v) \in M$</span> , <span class="math-container">$\left( \left(d(u) &lt; c\right) \lor \left(d(v) &lt; c\right) \right)$</span> holds, where <span class="math-container">$c=3$</span>. <span class="math-container">$d(u)$</span> means degree in <span class="math-container">$M$</span>, i.e., <span class="math-container">$d(u)=|(u,v) \in M|$</span>. We call this constraint a degree-constraint.</p>
<p><strong>Output</strong>: The maximum sized (cardinality of edges) <span class="math-container">$M$</span>.</p>
</blockquote>
<p>The problem on <span class="math-container">$c=2$</span> is already <span class="math-container">$NP-complete$</span> as shown by Jukka Suomela. There is a <span class="math-container">$2-approximation$</span> algorithm for a general graph already.  Jukka devised a <span class="math-container">$O(|V|c)$</span> DP for this problem when <span class="math-container">$G$</span> is restricted on trees.</p>

CC BY-SA 3.0
2011-08-23T14:06:10.647Z
(1) Please state what d(u) means.  It seems that d(u) denotes the degree in M (not in G) judging from the example, but it is unclear from the current question.  (2) The last two paragraphs only repeat what was stated earlier.  Maybe you forgot to delete them.
Tsuyoshi Ito
CC BY-SA 3.0
2011-08-28T13:18:29.063Z
I think it is a bit confusing that you keep editing your question. Previously, you asked if the problem can be solved in polynomial time if $G$ is a tree, and I answered the question. However, now the question is about something very different – parameterised complexity and bounded-treewidth graphs – and my answer looks completely irrelevant. This leaves me in a bit awkward position: should I delete the answer now, or look like someone who has badly misunderstood your question?
Jukka Suomela
CC BY-SA 3.0
2011-08-28T16:23:26.917Z
@Jukka: I am so sorry. I will ask another new question.
Peng Zhang
CC BY-SA 3.0
2011-08-28T16:35:56.193Z
@Jukka: I was thinking about ask further, deeper questions about the problem. I have posted a follow-up [here]. Thank you very much for your patient help again. 
[here]:http://cstheory.stackexchange.com/questions/7996/faster-fpt-for-a-variant-of-maximum-matching
Peng Zhang
CC BY-SA 3.0
2011-08-28T16:55:37.067Z
You don't need to annotate the question and change the title when it's resolved. the act of accepting an answer is sufficient. Making changes after the fact merely bumps the question back up the queue and makes it look unresolved, the opposite of what you're trying to indicate. The best approach is to accept an answer, and if you see fit, add  a comment to the answer.
Suresh Venkat
CC BY-SA 3.0
2011-08-28T17:12:17.710Z
@Peng: I think that you have messed up your question by editing it heavily after it was answered.  Currently your post does not contain any question.  Please edit the post so that other people can understand the question.
Tsuyoshi Ito
<cc.complexity-theory><graph-algorithms><approximation-algorithms><parameterized-complexity>
A variant of maximum matching: disjunctive constraints on the endpoints' degrees of edges in matching
Peng Zhang
# A variant of maximum matching: disjunctive constraints on the endpoints' degrees of edges in matching

(Asked by: username_0 on 2011-08-23)

The question is asked first at [here](https://cstheory.stackexchange.com/questions/7878/an-interesting-variant-of-maximum-matching-problem). It described what the problem is and a trival greedy algorithm. Also the accepted answer gave a proof of its NP-completeness.

> **Problem**: Given a graph $G(V,E)$, Find a subset of edges $M \subseteq E$. For each edge $(u,v) \in M$ , $\left( \left(d(u) < c\right) \lor \left(d(v) < c\right) \right)$ holds, where $c=3$. $d(u)$ means degree in $M$, i.e., $d(u)=|(u,v) \in M|$. We call this constraint a degree-constraint.
>
> **Output**: The maximum sized (cardinality of edges) $M$.

The problem on $c=2$ is already $NP-complete$ as shown by username_2. There is a $2-approximation$ algorithm for a general graph already. Jukka devised a $O(|V|c)$ DP for this problem when $G$ is restricted on trees.

**Tags:** cc.complexity-theory, graph-algorithms, approximation-algorithms, parameterized-complexity

> **Comments:**
> **username_1**: (1) Please state what d(u) means.  It seems that d(u) denotes the degree in M (not in G) judging from the example, but it is unclear from the current question.  (2) The last two paragraphs only repeat what was stated earlier.  Maybe you forgot to delete them.  
> **username_2**: I think it is a bit confusing that you keep editing your question. Previously, you asked if the problem can be solved in polynomial time if $G$ is a tree, and I answered the question. However, now the question is about something very different – parameterised complexity and bounded-treewidth graphs – and my answer looks completely irrelevant. This leaves me in a bit awkward position: should I delete the answer now, or look like someone who has badly misunderstood your question?  
> **username_0**: @Jukka: I am so sorry. I will ask another new question.  
> **username_0**: @Jukka: I was thinking about ask further, deeper questions about the problem. I have posted a follow-up [here]. Thank you very much for your patient help again.  [here]:http://cstheory.stackexchange.com/questions/7996/faster-fpt-for-a-variant-of-maximum-matching  
> **username_3**: You don't need to annotate the question and change the title when it's resolved. the act of accepting an answer is sufficient. Making changes after the fact merely bumps the question back up the queue and makes it look unresolved, the opposite of what you're trying to indicate. The best approach is to accept an answer, and if you see fit, add  a comment to the answer.  
> **username_1**: @Peng: I think that you have messed up your question by editing it heavily after it was answered.  Currently your post does not contain any question.  Please edit the post so that other people can understand the question.  

---

## 2 answers

### Answer by username_2 on 2011-08-27. Score: 6 | Accepted answer

The case of **trees** and a constant $c$ seems to admit a straightforward dynamic programming algorithm.

You root your tree arbitrarily. You will start from the leaf nodes and propagate information towards the root. You will keep track of the following pieces of information for each subtree; here $u$ is a node and $T(u)$ is the subtree rooted at $u$:

* $M\_1(u)$ = best matching in $T(u)$ if $u$ has unlimited capacity,
* $M\_2(u)$ = best matching in $T(u)$ if $u$ has capacity $c - 1$,
* $M\_3(u)$ = best matching in $T(u)$ if $u$ has capacity $c$.

Note that $M\_1(u)$ and $M\_2(u)$ can be extended by adding the edge $(v,u)$, where $v$ is the parent of $u$.

All of these values are trivial to compute for a leaf node. Once you have computed these values for all subtrees of a node $v$, you can compute them for $v$; let $C$ consist of the children of $v$:

* $M\_1(v)$: For each $u \in C$ of $v$ we take either $M\_2(u) + (v,u)$ or $M\_3(u)$, whichever is better.
* $M\_2(v)$: We check all subsets $S \subseteq C$ of size at most $c - 2$. For each child $u \in S$ we take $M\_1(u) + (v,u)$ or $M\_2(u) + (v,u)$, whichever is better. For each child $u \notin S$ we take $M\_1(u)$, $M\_2(u)$, or $M\_3(u)$, whichever is best.
* $M\_3(v)$: Similar to $M\_2(v)$, but we consider subsets of size at most $c - 1$.

Everything is polynomial if $c$ is a constant.

> **Comments:**
> **username_0**: Thanks a lot. There is an improvement on your DP. Counting $M_2(v)$ and $M_3(v)$ could be done in $|C|\times(c-1)$ time with a knapsack style DP. Saving the time for enumerating all subsets $S\subseteq C$.  
> **username_2**: @Peng: Right, I guess that shows that it is in P even if $c$ is part of input.  

---

### Answer by username_4 on 2011-08-23. Score: 4

One should be able to get a simple constant factor approximation as follows. Partition the nodes of the graph randomly into two sets $V\_1$ and $V\_2$ - each node decides with probability half to go to $V\_1$ or not. Ignore all the edges with both end points in the same side. We are left with a bipartite graph. Now solve a bipartite matching problem where the nodes in $V\_1$ have capacity $1$ and the nodes on the right have no capacity limit. This gives a collection of stars. Analysis is left as an easy exercise :).

> **Comments:**
> **username_0**: Thank you very much. :) the capacity may be 2 because the constraint is $< 3$. I find your algorithm is $2-approximation$ and could be easily derandomized. I am keep looking for parameterized reduction rules. Hope the problem is FPT.  
> **username_4**: I am not sure FPT is a good framework for this problem. Suppose you want to check if the optimum value is at least $k$. We can assume that the maximum degree in the graph is less than $k$, otherwise the answer is yes. If maximum degree is less than $k$ there will be a matching of size $\Omega(n/k)$ in the graph assuming it has no isolated vertices. Thus for all value of $k < \sqrt{n}$ one can easily check if the optimum value is at least $k$.  
> **username_0**: FPT with respect to the treewidth of $G$ *should* exisit. 2 reasons: **NO.1** The problem could be described as a MSO-formula. **No.2** The problem when restricted on trees is in P. I am thinking about the dynamic programming with the help of treewidth. Hope for good result.  [MSO-formula]:www.labri.fr/perso/courcell/Conferences/ExpoBerlin2007.pdf  

---

