CODEWITHSUNDEEP
algorithmgraphgraph-algorithmdepth-first-search
Abhishek Garg
Abhishek Garg

Reputation: 11

Path containing all the vertices in a biconnected graph

You are given a biconnected graph. A graph in which more than one simple path exists between any two different nodes.

Suppose there are N vertices in the graph. Now you have to choose a starting point and an ending point from these N vertices(possibly same) and travel from starting point to the ending point such that all the vertices are visited atleast once but all the edges are visited atmost once. You have to tell whether such a path exists or not.

Upvotes: 1

Views: 119

Answers (1)

David Eisenstat
David Eisenstat

Reputation: 65516

I think this problem is NP-hard, via the following reduction from Hamiltonian path on a biconnected cubic graph inspired by Catlin's observation that in cubic graphs, having a Hamiltonian cycle is equivalent to having a spanning Eulerian circuit. The reduction just spits out the input graph. If the input graph has a Hamiltonian path, then that path is a spanning Eulerian trail (what the problem calls for us to look for). Conversely, suppose that we have a spanning Eulerian trail. There are three cases for the trail:

  1. Two vertices with degree one in the trail; all other vertices have even degree.
  2. All vertices have even degree.
  3. Two vertices with degree three in the trail; all other vertices have even degree.

Case 1 immediately gives us a Hamiltonian path. Case 2 immediately gives us a Hamiltonian cycle, from which we can delete any edge and get a Hamiltonian path. Case 3 isn't too hard either; the vertices of degree three are the beginning and the end of the trail, so delete the first edge and last edge and get a Hamiltonian path.

Upvotes: 1

Related Questions