Re: Hamiltonian cycle problem in 2-connected bipartite cubic graph is Polynomial

On Jan 16, 6:54 pm, Zhu Guohun <ccgh...@xxxxxxxxxxxxxxxxxxxx> wrote:
On 1月16日, 下午7时33分, Ben Bacarisse <ben.use...@xxxxxxxxx> wrote:


Sorry! The arXiv admin remove my submission, they asked me to improve
my paper quality.

I prove that at least two simplifiedNP-Completeproblems is
polynomial in my paper.
First problem is $(2,3)-SAT$ problem wich is proved NP-Completed by
Raman [1].
Second problem is mimimum vertex cover on bridgeless cubic graph [2].

Now I give some idea of my paper under here.

1. Given a bridgeless cubic graph $G$ and a perfect matching $M$,
if all simple cycles in $G \setminus M$ is minimum,
then the minimum size of vertex cover $vc(G)$ is sum of all minimum
vertex cover of all minimum simple cycle.

2. The complexity of determining minimum odd simple cycle from a
cubic graph is $O(n^4)$.

3. The complexity of determining the minimum vertex cover of a 2-
connected cubic graph is $O(n^4)$.

4. Given a $(2,3)-SAT$ with symmetric Horn formulas, finding
maximum SAT is equal to
fiding a minimum vertex cover of SAT2G mapping graph $G$m, where
$d(G)<=2$

5. Given a $(2,3)-SAT$, the MAX2SAT problem could be determining in
polynomial.

6. Given a $(2,4)-SAT$, the MAX2SAT problem could be determining in
polynomial.

some definition is follows:
7. SAT2G mapping graph: a undirected graph was mapped from 2SAT,
clause --> edge and literal-->vertex

8. Horn formulas: a conjunction formulas which contains at most one
positive literal

9. symmetric Horn formulas: positive monotone formulas \cup Horn
formulas,
for example : $L=(x_1 \vee x_2),(x_2 \vee x_3),(\overline{x_3}
\vee x_1),(\overline{x_1} \vee x_4),(\overline{x_2} \vee
x_5),(\overline{x_3} \vee x_6), (\overline{x_4} \vee \overline{x_5}) ,
( \overline{x_5} \vee \overline{x_6}), ( \overline{x_4} \vee
\overline{x_6})$
where $L$ presents a symmetric Horn $(2,3)-SAT$ formula.

reference
[1]Venkatesh Raman, Bala Ravikumar, S. Srinivasa Rao: A SimplifiedNP-CompleteMAXSAT Problem. Inf. Process. Lett. 65(1): 1-6 (1998)
[2]Paola Alimonti and Viggo Kann. Hardness of approximating problems
on cubic graphs. CIAC 97, 288-298, volume 1203 of LNCS, 1997.
[3]Uehara, R. (1996 ),NP-completeproblems on a 3-connected cubic
planar graph and their applications, 'Technical Report TWCU-M-0004',
Tokyo Woman's Christian University.

----------------------------------
Guohun zhu

Guohun ,
You are wasting your time and others time in writing papers that one
can not even read/understand what any sentence is trying to say.
Your thinking is very immature. If such simple minded ideas could have
worked then this problem would have been solved long long back.
So stop wasting others time and creating more noise in a group like
comp.theory.

-Javaid
.