3
$\begingroup$

Is the following a familiar problem ? Given a graph $G = (V, E)$ and a capacity function $c:V \to \mathbb{N}$ find a spanning subgraph $H$ of $G$ such that $1 \leq deg_H(v) \leq c(v)$ for every vertex $v \in V$.

I would like to know if this is an NP-hard problem so any pointer to a similar problem (NP-hard or not) will be very appreciated as well.

Thank you,

GIlad

$\endgroup$
2
$\begingroup$

(This is edited after the conversation in the Comments below) This is similar to degree-constrained subgraph problems. That is one direction to search in.

You can drop your 'spanning' requirement since you enforce a minimum degree of 1, which means every vertex has to be included in order to satisfy your degree constraints. It feels like it should be polytime with a max flow solution.

$\endgroup$
  • $\begingroup$ Indeed, by spanning I mean the same set of vertices. $H$ does not have to be connected but its minimum degree must be at least one. The slides seems to be very helpful but ,as far as I can tell, none of the problems that were considered in the slides is exactly the same (or a special case) as I described. $\endgroup$ – Gilad Dec 9 '17 at 12:41
  • $\begingroup$ If I'm not mistaken, your problem is the not-connected version of what they call the "Maximum d-degree-bounded connected subgraph" problem, and in particular, at the bottom of that slide, it states: "If the output subgraph is not required to be connected, the problem is in P for any d (using matching techniques)." $\endgroup$ – JimN Dec 9 '17 at 19:01
  • $\begingroup$ The difference between the problems is that in their problem there is no guarantee that the minimum degree of the output subgraph is at least one, and it is quite easy to come up with an example in which a subgraph as I described exists, but there is a maximum subgraph with minimum degree zero. On the other hand, in my problem there is no requirement for the output to be of a maximum weight. So, unless I'm missing something, neither problems generalize the other one. $\endgroup$ – Gilad Dec 10 '17 at 4:55
  • $\begingroup$ You're right - your requirement of a minimum degree of 1 makes it a different problem. I will adjust this answer. $\endgroup$ – JimN Dec 10 '17 at 18:46

Your Answer

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

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