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

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

<snip>

The MAX2SAT problem is solved in polynomial, and I have been submit it
tohttp://arxiv.org/abs/0801.2447(maybe it also show a little
later).

Just a "heads up": For me, the link takes me to a log-in page, and my
attempt to register failed.

--
Ben.

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

I prove that at least two simplified NP-Complete problems 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 Simplified NP-
Complete MAXSAT 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-complete problems on a 3-connected cubic
planar graph and their applications, 'Technical Report TWCU-M-0004',
Tokyo Woman's Christian University.


----------------------------------
Guohun zhu
.