2

this is a problem I've got from my class (I assure you it's not homework). I'm still pondering about it until now. You will receive a graph with at most 25 nodes and 25 edges. Additionally, each node will have degree of at most 3. The task is to find the longest path in this graph. However, you won't only receive 1 graph, but 15,000 graphs, and you'll need to find the longest path in all of them in 1 second. Could anyone please give me a solution (or better yet, just a hint) to this problem? Thank you very much!

Info:
- Nodes can be revisited, the only constraints are the edges.
- The graphs are given by the edges. So the first line states how many nodes and edges there are, and the lines after that represent the edges, each edge by a pair of integers.
- The edges are unweighted.
- The only answer required is the length of the path, not the path itself.
- This might be important: the graph isn't necessarily connected.

user4034932
  • 181
  • 1
  • 9
  • 2
    What are the constraints on the longest path? Nodes can (not) be revisited? I suppose edges cannot be revisited? – trincot May 25 '16 at 20:23
  • Since there is a time constraint, I need to ask how are you going to read the input? Has its format been specified? – Nuri Tasdemir May 25 '16 at 20:25
  • 66 microseconds per graph (input, calculation, output). I doubt that its possible – Iłya Bursov May 25 '16 at 20:32
  • The questions have been answered. – user4034932 May 25 '16 at 20:49
  • @Lashane: really? Assuming the graph has an appropriate data structure, this doesn't seem that fantastically fast. – Marcus Müller May 26 '16 at 13:23
  • @MarcusMüller I especially mentioned input/output - pure reading from file and parsing string into data structure could take more, [for example](http://stackoverflow.com/questions/4087280/approximate-cost-to-access-various-caches-and-main-memory) states 2 milliseconds (2000 microseconds) for random hdd seek, of course it will read more than needed for one graph, though it looks like this question missing 99% of details important for it to be answered, so I doubt that it is generally possible – Iłya Bursov May 26 '16 at 14:28

1 Answers1

0

After I saw that "nodes can be revisited", I realised that this is in some ways a trick question. To satisfy those seemingly unbelievable time constraints, what you actually need here is not an algorithm for constructing such a path (usually called a trail, BTW, if vertices can be reused), but rather, for each connected component of the graph, a way of quickly detecting whether all or nearly all edges in that component can be included in a single trail.

So here is my hint: Did you know that there are seven bridges in Königsberg? ;-)

That might seem cryptic, but I think some quick searching around will point you in the right direction, and you will soon find a way to quickly detect whether all edges in a component can form part of the same trail. (You'll need to do some more thinking to figure out how many edges can be included when the answer to the above question is "no".)

j_random_hacker
  • 50,331
  • 10
  • 105
  • 169
  • 2
    Do you have a good approach to the "how many edges can be included when there is not an Eulerian path" part? At first glance it feels like this part is still NP-complete? – Peter de Rivaz May 27 '16 at 10:47
  • @PeterdeRivaz: Very good question, I shouldn't have handwaved at that part. According to http://kam.mff.cuni.cz/conferences/wg2011/files/slides/slides.pdf, the problem of deleting the fewest number of edges to make a graph Eulerian is indeed NP-hard (that is, to make sure the graph has an Eulerian *cycle*; but making sure it has an Eulerian *path* as here, is not easier, since an algo for the latter could be turned into a O(|E|)-times slower one for the former by just deleting each edge in turn, making an EP, and then adding the edge back in). – j_random_hacker May 31 '16 at 13:08
  • 1
    @PeterdeRivaz: Interestingly the problem of making all vertices even-degree with a minimum number of edge deletions *can* be solved in poly-time -- see slides 10 and 11 for more (but not too many!) details. So what makes the problem hard seems to be the constraint that the resulting graph is still connected. – j_random_hacker May 31 '16 at 13:09
  • Plus, even if the longest Eulerian Path can be found in P, that length would still only be a lower bound of the real answer. – user4034932 May 31 '16 at 13:13
  • @user4034932: Hmm... I'm not talking about a "longest Eulerian Path" (what does that mean actually?) I'm talking about the fewest edge deletions needed to give the remaining graph an Eulerian path. This by definition uses *all* of those remaining (i.e., not deleted) edges, so it will be longest-possible (at least if we run it on each connected component in the input). – j_random_hacker May 31 '16 at 13:19
  • There must be some way of using the "degree at most 3" constraint, but I can't think what. – j_random_hacker May 31 '16 at 13:20
  • @j_random_hacker Isn't what you mentioned exactly the longest Eulerian Path? Deleting at little edges as possible means that the resulting path is the longest possible. – user4034932 May 31 '16 at 19:59
  • @user4034932: Yes, what I mentioned *is* (and was intended to be) exactly the longest Eulerian Path... So I'm confused as to what "real answer" could be longer than this? – j_random_hacker Jun 01 '16 at 09:49
  • @j_random_hacker Ah yes, I must have mistaken. If we could find the longest Eulerian Path, it would be the answer. – user4034932 Jun 01 '16 at 12:34