# Re: Syntax NP Complete - Hamiltonian Paths

• From: Peter F. Patel-Schneider <pfps@research.bell-labs.com>
• Date: Wed, 02 Apr 2003 09:29:23 -0500 (EST)
• Message-Id: <20030402.092923.68558916.pfps@research.bell-labs.com>
```Sneaky!

From: Jeremy Carroll <jjc@hpl.hp.com>
Subject: Syntax NP Complete - Hamiltonian Paths
Date: Wed, 2 Apr 2003 15:44:21 +0300

> On Friday while working on my formal objection I noted that there might be a
> relationship to the NP complete problem of Hamiltonian paths (i.e. finding a
> path through a graph that visits every node) and the EquivalentClasses
> mapping rule.
>
> Unfortunately, there is. I am sorry for not noticing earlier.
>
> It is not hard to fix, but I am not sure where I send my observations.
>
> Proof:
>
> Given an undirected., unlabelled graph G over the integers 1, ... n, and a
> tool that can tell if an RDF/XML document is in OWL DL or not, we can
> determine if there is a Hamiltonian path in the following fashion:
>
> 1: Is G connected, (O(n^3) Roy's algorithm, often misattributed to Warshall)
>   If NO then there is no Hamiltonian Path.
>
> Otherwise:
>  Construct RDF Graph
>
>  _:n<i> owl:equivalentClass _:n<j> . For all i, j s.t. {i,j} is in G.
>
> _:n<i> rdf:type owl:Class .   i = 1 .... n
> _:n<i> owl:unionOf rdf:nil .  i = 1 ... n
>
> Then this RDF Graph is in OWL DL iff there is a Hamiltonian path in G.
>
>
> ==========
>
> Possible fixes include one of:
> 1: use B.1, B.2;
> 2: change mapping rule to
> EquivalentClasses( d1, .... dn )
>
>   T(di) owl:equivalentClass T(dj) .
> or
>  T(dj) owl:equivalentClass T(di) .   For all i,j s.t {i,j} in G, an arbitrary
> connected graph over {1, 2, ... n }
>
> 3: delete optional part of mapping rule for EquivalentClasses

I think that the forcing function here should be to expand the set of RDF
graphs that are in OWL DL/OWL Lite, whereever possible (because this would
lead to fewer problems in getting out of last call).

I therefore would propose that fix 2b is the best one here.

peter
```

Received on Wednesday, 2 April 2003 09:29:33 UTC