[r-t] # Extents on N bells

[Richard Smith]

Martin Bright wrote:

> Reducing an NP-complete problem to a linear-time one would be quite a great
> achievement, but I think if it were this easy then somebody would have
> spotted it by now. ;-)

Unless there have been recent developments, it is *not*
known that finding Hamiltonian circuits on a vertex
transitive graphs (or Cayley graphs) is NP-complete.  It is
only when it is generalised to non-vertex transitive graphs
that it is known to be NP-complete.


Chris Poole wrote:

> On Thu, 19 Aug 2004, Chris Poole wrote:
>
> > > --On 19 August 2004 10:10 +0100 Chris Poole <poole at maths.ox.ac.uk> wrote:
> > >
> > > > Why not map the nodes to edges (and vice versa).
> > >
> > > How?  You can't make this work in a one-to-one way - try it.
>
> ... don't you get round it by using hyperedges?

Sure, but once you allow hyperedges (or, in the more general
case, directed hyperedges), is there still an advantage to
considering the graph in this way?

Richard