## 10988 - From G to H and back

All about problems in Volume 109. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

### 10988 - From G to H and back

Is there any hint for this question?

Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:
Here is a hint. H is called the "line graph of G". Search mathworld...
If only I had as much free time as I did in college...

little joey
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...
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
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.

Abednego
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.
If only I had as much free time as I did in college...

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:
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.

little joey
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
``````
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....
The biggest problem with most problems is not how to solve the problem, but how to not solve what is not the problem.

Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:
I sent a correction about this to Mathworld. They should fix it soon.

igor
If only I had as much free time as I did in college...

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
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

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:
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.

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:
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.

little joey
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:

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.
The biggest problem with most problems is not how to solve the problem, but how to not solve what is not the problem.