HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Finding subgraph problem

Submitted by: @import:stackexchange-cs··
0
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

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.

Context

StackExchange Computer Science Q#85094, answer score: 2

Revisions (0)

No revisions yet.