<p>(As it seems that the connection is not completely obvious, I will write an extended version of the above comments as an answer.)</p>

<p>I will focus on the case of $c = 2$. In that case, the problem can be rephrased as follows:</p>

<ul>
<li>Let $G = (V,E)$ be a graph. The task is to find a maximum-size $M \subseteq E$ such that the following constraint is satisfied: for each $\{u,v\} \in M$, either $u$ is incident to at most $1$ edge in $M$, or $v$ is incident to at most $1$ edge in $M$, or both.</li>
</ul>

<p>Equivalently:</p>

<ul>
<li>The subgraph induced by $M$ has to have the property that all neighbours of a non-leaf node (degree > 1) are leaf nodes (degree = 1).</li>
</ul>

<p>Equivalently:</p>

<ul>
<li>The subgraph induced by $M$ consists of node-disjoint stars. </li>
</ul>

<p>In what follows I will interpret unmatched nodes (nodes not incident to any edge in $M$) as stars with 0 edges. Hence a feasible solution <em>partitions</em> the set of nodes into node-disjoint stars.</p>

<p>Now if the number of such stars is $k$, then the number of edges in $M$ is exactly $n-k$: there are $n-k$ leaf nodes that are connected to a star center. Therefore maximising the number of edges in $M$ is equivalent to minimising then number of stars.</p>

<p>Now it is straightforward to see that we have a solution with $k$ such stars iff we have a dominating set of size $k$:</p>

<ol>
<li>Assume that we are given $k$ such stars. Then we can find a dominating set of size $k$: simply take the centers of the stars (in a star with 1 edge you can pick a node arbitrarily).</li>
<li>Assume that we are given a dominating set $D$ with $|D| = k$. Then we can simply connect each node in $V \setminus D$ to one node in $D$. These edges form a family of $k$ stars.</li>
</ol>

<p>Therefore solving the problem optimally in a certain graph family $F$ is exactly as hard as finding a <a href="http://www.nada.kth.se/~viggo/wwwcompendium/node11.html">minimum dominating set</a> in the same graph family $F$. In particular, the problem is NP-hard even in the case of bipartite graphs.</p>

<p>(However, (in)approximability results related to dominating sets cannot be directly applied here. In essence, we have changed the objective function from $\min |D|$ to $\max n-|D|$.)</p>

CC BY-SA 3.0
2011-08-20T23:24:53.327Z
Great. (in)approximability results related to dominating sets cannot be directly applied here just like the infeasibility to apply (in)approximability of vertex cover to independent set.
Peng Zhang
CC BY-SA 3.0
2011-08-20T23:33:44.047Z
For $c=3$, it is also $NP-complete$. We will reduce $( G(V,E),c=2)$ to $( G'(V \cup \{v\} , E \cup \{(u,v)\}, u \in V), c=3)$. $G$ has a $K$ solution iff $G'$ has a $K$ solution.
Peng Zhang
CC BY-SA 3.0
2011-08-20T22:26:51.430Z
2011-08-20T22:46:45.573Z
2011-08-20T22:46:45.573Z
Jukka Suomela
<p>Given a graph $G(V,E)$, the classic maximum matching problem is choosing the maximum subset of edges $M$ s.t., for each edge $(u,v) \in M$, $d(u)=d(v)=1$. </p>

<p>Has anybody studied the following variant? For each edge $(u,v) \in M$ , $\left( \left(d(u) &lt; c\right) \lor \left(d(v) &lt; c\right) \right)$ holds, where c is a constant. We call this constraint a degree-constraint.</p>

<p>The classic constraint is an conjunction on degree with constant 1. The new variant is an disjunction on degree with constant $c$.</p>

<p>The problem on $c=2$ is already $NP-complete$ as shown by Jukka Suomela. I am interested in the potential approximation algorithms. A simple greedy algorithm is selecting maximum star subgraph iteratively until no star subgraph (i.e., no edge(a special star) ) can be selected. But this algorithm performs bad even when $G$ is a tree when $c=3$. There is a inner star whose center has degree $x$, and there are $x$ outer stars each center has degree $x$ and connected to the center of the inner star. The optimum value is $2*x+(x-2)*(x-1)$ by selecting $x-2$ edges from each of $x-2$ outer stars and 2 complete outer stars. The value produced by the greeedy algorithm is $x+1*x$ by selecting the inner star and one edge from every outer star. </p>

<p>The greedy algorithm above is $2\sqrt{n-1}$ approximation, where $n=|V|$. I want to find better approximation algorithm of this algorithm or prove its hardness of approximation.</p>

<p>Furthermore, I want to know the complexity class of this problem in the framework of parameterized complexity. Maybe it bears reasonable fixed parameter algorithm.</p>

<p>Thanks a lot for your comment and answer in advance. :-)</p>

CC BY-SA 3.0
2011-08-20T10:55:10.827Z
So if $c = 1$, you want to find a subgraph that consists of disjoint stars? And, for example, in $K_{n,n}$ the optimal solution then consists of exactly two stars ($2n-2$ edges)?
Jukka Suomela
CC BY-SA 3.0
2011-08-20T11:09:21.223Z
The case of $c=1$ seems to be closely related to the dominating set problem: in a graph with $n$ nodes, you can find a solution with $n-k$ edges iff you have a dominating set of size $k$.
Jukka Suomela
CC BY-SA 3.0
2011-08-20T11:25:29.817Z
Yes. Not $c=1$ but $c=2$ is your instance. Thank you very much. It is exacly what I want to ask about. Has anybody studied this variant before? My current problem is on bipartite graph with $c=3$.
Peng Zhang
CC BY-SA 3.0
2011-08-20T11:28:20.613Z
Well, *many* people have studied [dominating sets](http://www.nada.kth.se/~viggo/wwwcompendium/node11.html). :)  Hard to solve, hard to approximate, even on bipartite graphs. I would assume that the case of a larger $c$ is not any easier...
Jukka Suomela
CC BY-SA 3.0
2011-08-23T06:39:09.120Z
It's a little confusing to see a bounty attached to a question with an accepted answer. You'd have been better of issuing the new question separately. unfortunately, now that you've attached a bounty, I don't think that's possible.
Suresh Venkat
CC BY-SA 3.0
2011-08-23T07:29:05.093Z
I am sorry because I am a beginner here. I would try to as a new question and have link to this current question used to express the background. Is that OK?
Peng Zhang
CC BY-SA 3.0
2011-08-23T14:00:34.883Z
Currently this question has been edited to the same question as [your other question](http://cstheory.stackexchange.com/questions/7929/beyond-np-complete-ask-for-better-approximation-algorithm-or-hardness-of-this-v), and it is confusing.  Maybe it is better to revert this question to the original question.
Tsuyoshi Ito
CC BY-SA 4.0
2019-12-10T05:49:15.490Z
@PengZhang May I suggest an edit to this question. You need to clarify that you are interested in matchings $M$ such that for fixed $c$, $\forall \{u,v\}\in M$, $d_{G[M]}(u)<c$ and $d_{G[M]}(v)<c$
Cyriac Antony
CC BY-SA 4.0
2019-12-11T04:00:08.757Z
@PengZhang Also, please consider renaming your question. "Variant of matching" sound like your are asking for matching that satisfy extra conditions. You are rather asking for a generalization of matching.
Cyriac Antony
<cc.complexity-theory><ds.algorithms><graph-theory><co.combinatorics>
An interesting variant of maximum matching problem
Peng Zhang
# An interesting variant of maximum matching problem

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

Given a graph $G(V,E)$, the classic maximum matching problem is choosing the maximum subset of edges $M$ s.t., for each edge $(u,v) \in M$, $d(u)=d(v)=1$.

Has anybody studied the following variant? For each edge $(u,v) \in M$ , $\left( \left(d(u) < c\right) \lor \left(d(v) < c\right) \right)$ holds, where c is a constant. We call this constraint a degree-constraint.

The classic constraint is an conjunction on degree with constant 1. The new variant is an disjunction on degree with constant $c$.

The problem on $c=2$ is already $NP-complete$ as shown by Jukka Suomela. I am interested in the potential approximation algorithms. A simple greedy algorithm is selecting maximum star subgraph iteratively until no star subgraph (i.e., no edge(a special star) ) can be selected. But this algorithm performs bad even when $G$ is a tree when $c=3$. There is a inner star whose center has degree $x$, and there are $x$ outer stars each center has degree $x$ and connected to the center of the inner star. The optimum value is $2\*x+(x-2)\*(x-1)$ by selecting $x-2$ edges from each of $x-2$ outer stars and 2 complete outer stars. The value produced by the greeedy algorithm is $x+1\*x$ by selecting the inner star and one edge from every outer star.

The greedy algorithm above is $2\sqrt{n-1}$ approximation, where $n=|V|$. I want to find better approximation algorithm of this algorithm or prove its hardness of approximation.

Furthermore, I want to know the complexity class of this problem in the framework of parameterized complexity. Maybe it bears reasonable fixed parameter algorithm.

Thanks a lot for your comment and answer in advance. :-)

**Tags:** cc.complexity-theory, ds.algorithms, graph-theory, co.combinatorics
> **Comments:**
> **username_1**: So if $c = 1$, you want to find a subgraph that consists of disjoint stars? And, for example, in $K_{n,n}$ the optimal solution then consists of exactly two stars ($2n-2$ edges)?  
> **username_1**: The case of $c=1$ seems to be closely related to the dominating set problem: in a graph with $n$ nodes, you can find a solution with $n-k$ edges iff you have a dominating set of size $k$.  
> **username_0**: Yes. Not $c=1$ but $c=2$ is your instance. Thank you very much. It is exacly what I want to ask about. Has anybody studied this variant before? My current problem is on bipartite graph with $c=3$.  
> **username_1**: Well, *many* people have studied [dominating sets](http://www.nada.kth.se/~viggo/wwwcompendium/node11.html). :)  Hard to solve, hard to approximate, even on bipartite graphs. I would assume that the case of a larger $c$ is not any easier...  
> **username_2**: It's a little confusing to see a bounty attached to a question with an accepted answer. You'd have been better of issuing the new question separately. unfortunately, now that you've attached a bounty, I don't think that's possible.  
> **username_0**: I am sorry because I am a beginner here. I would try to as a new question and have link to this current question used to express the background. Is that OK?  
> **username_3**: Currently this question has been edited to the same question as [your other question](http://cstheory.stackexchange.com/questions/7929/beyond-np-complete-ask-for-better-approximation-algorithm-or-hardness-of-this-v), and it is confusing.  Maybe it is better to revert this question to the original question.  
> **username_4**: @PengZhang May I suggest an edit to this question. You need to clarify that you are interested in matchings $M$ such that for fixed $c$, $\forall \{u,v\}\in M$, $d_{G[M]}(u)<c$ and $d_{G[M]}(v)<c$  
> **username_4**: @PengZhang Also, please consider renaming your question. "Variant of matching" sound like your are asking for matching that satisfy extra conditions. You are rather asking for a generalization of matching.  

---

## 1 answers

### Answer by username_1 on 2011-08-20. Score: 8 | Accepted answer

(As it seems that the connection is not completely obvious, I will write an extended version of the above comments as an answer.)

I will focus on the case of $c = 2$. In that case, the problem can be rephrased as follows:

* Let $G = (V,E)$ be a graph. The task is to find a maximum-size $M \subseteq E$ such that the following constraint is satisfied: for each $\{u,v\} \in M$, either $u$ is incident to at most $1$ edge in $M$, or $v$ is incident to at most $1$ edge in $M$, or both.

Equivalently:

* The subgraph induced by $M$ has to have the property that all neighbours of a non-leaf node (degree > 1) are leaf nodes (degree = 1).

Equivalently:

* The subgraph induced by $M$ consists of node-disjoint stars.

In what follows I will interpret unmatched nodes (nodes not incident to any edge in $M$) as stars with 0 edges. Hence a feasible solution *partitions* the set of nodes into node-disjoint stars.

Now if the number of such stars is $k$, then the number of edges in $M$ is exactly $n-k$: there are $n-k$ leaf nodes that are connected to a star center. Therefore maximising the number of edges in $M$ is equivalent to minimising then number of stars.

Now it is straightforward to see that we have a solution with $k$ such stars iff we have a dominating set of size $k$:

1. Assume that we are given $k$ such stars. Then we can find a dominating set of size $k$: simply take the centers of the stars (in a star with 1 edge you can pick a node arbitrarily).
2. Assume that we are given a dominating set $D$ with $|D| = k$. Then we can simply connect each node in $V \setminus D$ to one node in $D$. These edges form a family of $k$ stars.

Therefore solving the problem optimally in a certain graph family $F$ is exactly as hard as finding a [minimum dominating set](http://www.nada.kth.se/~viggo/wwwcompendium/node11.html) in the same graph family $F$. In particular, the problem is NP-hard even in the case of bipartite graphs.

(However, (in)approximability results related to dominating sets cannot be directly applied here. In essence, we have changed the objective function from $\min |D|$ to $\max n-|D|$.)

> **Comments:**
> **username_0**: Great. (in)approximability results related to dominating sets cannot be directly applied here just like the infeasibility to apply (in)approximability of vertex cover to independent set.  
> **username_0**: For $c=3$, it is also $NP-complete$. We will reduce $( G(V,E),c=2)$ to $( G'(V \cup \{v\} , E \cup \{(u,v)\}, u \in V), c=3)$. $G$ has a $K$ solution iff $G'$ has a $K$ solution.  

---

