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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 转化成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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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. : /*\\
|