Page 1 of 1

10988 - From G to H and back

Posted: Mon Jan 23, 2006 10:51 pm
by sclo
Is there any hint for this question?

Posted: Tue Jan 24, 2006 12:07 am
by Abednego
Here is a hint. H is called the "line graph of G". Search mathworld...

Posted: Wed Jan 25, 2006 3:32 pm
by little joey
I'm a bit confused by the mathworld entry you mention.
As I understand it, a graph is a line graph iff it doesn't contain one of the nine listed graphs as an induced subgraph. Are those pictures correct? The second picture contains the first as an induced subgraph, so why is it included separately?

To solve this problem, do we have to search for the nine induced subgraphs in the line graph?
Is there a way to do that more efficiently then O(m^6)? (m can be 320).

Or do we have to find the incidence matrix C of the original graph from the 'Skiena' equation L = CtC - 2I. That can be quite elaborate, because we only know one dimension of it (and the other dimension, the number of vertices in the original graph, is unbounded in principle). And how to recognise a valid incidence matrix?

A further hint or two would be appreciated... :)

Posted: Wed Jan 25, 2006 4:23 pm
by Adrian Kuegel
The second picture contains the first as an induced subgraph, so why is it included separately?
When you take a subgraph, you can't remove any edges between nodes which belong to the subgraph, so the second doesn't really contain the first.
I also fear that those 9 "forbidden" graphs don't help to solve the problem, the only method I can think of to check for these subgraphs is the naive O(n^6) one.

Posted: Wed Jan 25, 2006 4:27 pm
by Abednego
Yes, you are correct that the second graph contains the first. I think it is a mistake on Mathworld. Only 8 are necessary.

I agree that my hit was not very useful, but it gives you at least 9 graphs which have the answer NO. It's easy to come up with YES graphs by doing the G->H trransformation.

Hmm... What other hints can I give? There exists a linear time algorithm, but it is not necessary to be that efficient for this problem. Try to understand exactly why those 9 graphs are impossible. That will help you.

Posted: Wed Jan 25, 2006 10:05 pm
by sclo
I have some sort of greedy algorithm that can fail all 9 of those graphs, now I just need to make sure that a graph can pass if it doesn't contain those induced subgraphs. I bet that this is linear.

Posted: Fri Jan 27, 2006 5:04 pm
by little joey
Adrian Kuegel wrote: When you take a subgraph, you can't remove any edges between nodes which belong to the subgraph, so the second doesn't really contain the first.

Code: Select all

    1
   /|
  / |
 /  |
2---3---4
 \  |
  \ |
   \|
    5
The induced subgraph formed by the vertices 1, 3, 4 and 5 is equal to the first picture (the 'claw').

Still in the dark how to tackle this problem....

Posted: Fri Jan 27, 2006 6:09 pm
by Abednego
I sent a correction about this to Mathworld. They should fix it soon.

igor

Posted: Fri Jan 27, 2006 7:04 pm
by Adrian Kuegel
The induced subgraph formed by the vertices 1, 3, 4 and 5 is equal to the first picture (the 'claw').
You are absolutely right. I didn't see this subgraph :oops:

Posted: Sat Jan 28, 2006 8:16 am
by sclo
Still no success at getting accepted. My program will fail all the graphs on Mathworld. I've tried adding more vertices and edges (keeping the property that they contain the induced subgraph) and they still fail. Now I keep getting wrong answers. One thing, if my algorithm says yes, it is definitely true that H is a line-graph. There must be something wrong with my "no". In all cases I checked that when my algorithm returns "no", the graph doesn't include any of the forbidden subgraphs, so I need more critical test cases.

Posted: Sat Jan 28, 2006 10:25 am
by sclo
There must be something wrong with my "no"
It seems that my "no" is not always correct, so I just added some randomization and iterate and get AC.

Posted: Sat Jan 28, 2006 4:36 pm
by little joey
Finaly made it. Thanks Igor for the problem, it's been a roller coaster ride. Spent hours on Google, without much succes, until I followed your hint and tried to actualy understand the problem.
Some final remarks:

For those who don't want to wait until Mathworld updates its site, here is the correct second picture:

Code: Select all

    1
   /|\
  / | \
 /  |  \
2---3   4
 \  |  /
  \ | /
   \|/
    5
It is essential to note that the original graph G should be simple. My initial attempt allowed multiple edges, but got WA. In fact 6 out of the 9 Beineke graphs can be inverted, if multiple edges were allowed. I think this should have been mentioned in the problem description.