j***n
发帖数: 301 | 1 Hi Everyone,
I need to proof Vertex Cover problem is NP complete even for cubic graphs. N
otice that a cubic graph is a graph such that every vertex has degree of *ex
actly three*. I found one paper but his definition for cubic graph is a litt
le loose in that the degree can be less than 3.
Can anybody give me a hint?
Thanks! |
A*******r
发帖数: 768 | 2 转化成3-SAT??
N
ex
litt
【在 j***n 的大作中提到】
: Hi Everyone,
: I need to proof Vertex Cover problem is NP complete even for cubic graphs. N
: otice that a cubic graph is a graph such that every vertex has degree of *ex
: actly three*. I found one paper but his definition for cubic graph is a litt
: le loose in that the degree can be less than 3.
: Can anybody give me a hint?
: Thanks!
|
j***n
发帖数: 301 | 3 首先要转也是从3-sat转过来吧？
【在 A*******r 的大作中提到】
: 转化成3-SAT??
:
: N
: ex
: litt
|
s*****g
发帖数: 5159 | 4 Check Garey and Johnson 1979, I remember there is a similar proof.
N
ex
litt
【在 j***n 的大作中提到】
: Hi Everyone,
: I need to proof Vertex Cover problem is NP complete even for cubic graphs. N
: otice that a cubic graph is a graph such that every vertex has degree of *ex
: actly three*. I found one paper but his definition for cubic graph is a litt
: le loose in that the degree can be less than 3.
: Can anybody give me a hint?
: Thanks!
|
s*x
发帖数: 3328 | 5 you can change a graph with vertex \leq 3 into a graph with vertex degree =3
by adding dummy vertex in polynomial time. So it doesn't matter whether \
leq 3 or =3.
/*\\ |
j***n
发帖数: 301 | 6 Got it. Thanks!
=3
【在 s*x 的大作中提到】
: you can change a graph with vertex \leq 3 into a graph with vertex degree =3
: by adding dummy vertex in polynomial time. So it doesn't matter whether \
: leq 3 or =3.
: /*\\
|
