10988 - From G to H and back

sclo · Post by **sclo** » Mon Jan 23, 2006 10:51 pm

Is there any hint for this question?

Abednego · Post by **Abednego** » Tue Jan 24, 2006 12:07 am

Here is a hint. H is called the "line graph of G". Search mathworld...

little joey · Post by **little joey** » Wed Jan 25, 2006 3:32 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...

Adrian Kuegel · Post by **Adrian Kuegel** » Wed Jan 25, 2006 4:23 pm

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 · Post by **Abednego** » Wed Jan 25, 2006 4:27 pm

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.

sclo · Post by **sclo** » Wed Jan 25, 2006 10:05 pm

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 · Post by **little joey** » Fri Jan 27, 2006 5:04 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....

Abednego · Post by **Abednego** » Fri Jan 27, 2006 6:09 pm

I sent a correction about this to Mathworld. They should fix it soon.

igor

Adrian Kuegel · Post by **Adrian Kuegel** » Fri Jan 27, 2006 7:04 pm

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 · Post by **sclo** » Sat Jan 28, 2006 8:16 am

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 · Post by **sclo** » Sat Jan 28, 2006 10:25 am

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 · Post by **little joey** » Sat Jan 28, 2006 4:36 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.