# Tag Info

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