patternMinor
Finding subgraph problem
Viewed 0 times
problemsubgraphfinding
Problem
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
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
Solution
(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.
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.
Context
StackExchange Computer Science Q#85094, answer score: 2
Revisions (0)
No revisions yet.