10988 - From G to H and back
Moderator: Board moderators
10988 - From G to H and back
Is there any hint for this question?
-
- Guru
- Posts: 1080
- Joined: Thu Dec 19, 2002 7:37 pm
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...
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...

The biggest problem with most problems is not how to solve the problem, but how to not solve what is not the problem.
-
- Guru
- Posts: 724
- Joined: Wed Dec 19, 2001 2:00 am
- Location: Germany
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.The second picture contains the first as an induced subgraph, so why is it included separately?
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.
-
- A great helper
- Posts: 281
- Joined: Tue Sep 10, 2002 5:14 am
- Location: Mountain View, CA, USA
- Contact:
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.
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.
If only I had as much free time as I did in college...
-
- Guru
- Posts: 1080
- Joined: Thu Dec 19, 2002 7:37 pm
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
Still in the dark how to tackle this problem....
The biggest problem with most problems is not how to solve the problem, but how to not solve what is not the problem.
-
- Guru
- Posts: 724
- Joined: Wed Dec 19, 2001 2:00 am
- Location: Germany
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.
-
- Guru
- Posts: 1080
- Joined: Thu Dec 19, 2002 7:37 pm
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:
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.
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
The biggest problem with most problems is not how to solve the problem, but how to not solve what is not the problem.