16
One example: choosing the property "G contains a node that has an edge to all nodes in G" makes P1 trivial in $O(n + m)$ (pick node with largest degree), but makes P2 the problem of finding the minimum size dominating set, which is NP-hard.
7
What you look for in question Q1 is known as an $f$-factor of the graph. Here $f$ is a non-negative integer valued function on the vertices, $f(v)$ specifying the degree we want in the subgraph at vertex $v$.
Q2 is looking for a so called $(g,f)$ factor, where $g(v)$ is a lower bound and $f(v)$ is an upper bound on the degree of the sought subgraph at each ...
4
The problem is NP-complete. We'll make a series of reductions from max-cut to show this.
Problem 0 (your problem): Given a graph $G$, does G have an induced subgraph with at least k vertices, such that all vertices have even degree within the subgraph?
Problem 1: Given a graph $G$ and subset $A$ of vertices, does $G$ have an induced subgraph with at least $...
3
I recently worked on a research paper that answers your questions - specifically, if we have a $k$-regular graph $G$ (each vertex in $G$ has degree $k$), and a set $S \subseteq \{1, ..., k\}$, what is the complexity of finding a subset of edges of $G$ such that each vertex in $G$ has degree in $S$? More formally, what is the complexity of finding an $S$-...
1
I have a partial solution, with constructions for the first question and for the second question when $n = 2\ (\text{mod}\ 4)$.
Here are constructions for $n = 8$ and $n = 14$. These generalise to constructions for $n = 0\ (\text{mod}\ 4)$ and $n = 2\ (\text{mod}\ 4)$, by taking any square, for example 1,2,3,6 in the second construction, and replacing it ...
Only top voted, non community-wiki answers of a minimum length are eligible
