5
$\begingroup$

The question is asked first at here. 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 Jukka Suomela. 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.

Improve this question
$\endgroup$
6
  • $\begingroup$ (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. $\endgroup$
    – Tsuyoshi Ito
    Aug 23, 2011 at 14:06
  • 1
    $\begingroup$ 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? $\endgroup$
    – Jukka Suomela
    Aug 28, 2011 at 13:18
  • $\begingroup$ @Jukka: I am so sorry. I will ask another new question. $\endgroup$
    – Peng Zhang
    Aug 28, 2011 at 16:23
  • 2
    $\begingroup$ 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. $\endgroup$
    – Suresh Venkat
    Aug 28, 2011 at 16:55
  • 1
    $\begingroup$ @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. $\endgroup$
    – Tsuyoshi Ito
    Aug 28, 2011 at 17:12

2 Answers 2

Reset to default
6
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ 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$. $\endgroup$
    – Peng Zhang
    Aug 27, 2011 at 11:54
  • $\begingroup$ @Peng: Right, I guess that shows that it is in P even if $c$ is part of input. $\endgroup$
    – Jukka Suomela
    Aug 27, 2011 at 12:05
4
$\begingroup$

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 :).

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – Peng Zhang
    Aug 24, 2011 at 14:21
  • 3
    $\begingroup$ 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$. $\endgroup$
    – Chandra Chekuri
    Aug 24, 2011 at 16:49
  • $\begingroup$ 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 $\endgroup$
    – Peng Zhang
    Aug 27, 2011 at 17:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.