11396 - Claw Decomposition

[crackerwang]

I did not understand the define of claw.
so is the following graph a claw?
the first graph
1 2
1 3
1 4
4 5
4 6

the second graph
1 2
1 3
1 4
2 5
3 6
4 7

and can anyone give me some hint of the algorithm?
thx.

[DP]

Output:

Code: Select all

YES
YES

[Hadi]

NO
NO
.

Although none of your graphs would appear in the test-data. because the problem statement says all graphs has only vertices of degree 3.

HINT: All vertices has degree 3. So, If a vertex is the center of a claw, what can we conclude about its neighbors? What about the neighbors of a vertex which is not the center of a claw?

[Hadi]

Output:

Code: Select all

YES
YES

Well, a program which gets accepted would output 'YES' for both graphs, but none of those graphs are eligible to appear in the test-data, and If their shape is not claw.

[crackerwang]

NO
NO
.

Although none of your graphs would appear in the test-data. because the problem statement says all graphs has only vertices of degree 3.

HINT: All vertices has degree 3. So, If a vertex is the center of a claw, what can we conclude about its neighbors? What about the neighbors of a vertex which is not the center of a claw?

thx.your hinit.

[mpi]

Spoiler:

If somebody is still confused, this is just a graph coloring problem with 2 colors

[Hadi]

P.D.: Sorry, I didn't want to spoil the party

I think you still have the chance to edit your post

[moxlotus]

Oh man this question is so confusing. How do one even know that this is a bipartite graph problem?
Can someone try to explain the question a bit? like give an example of a valid graph

[cosmin79]

I got accepted with a bipartite check algorithm, but I'm still rather unsure about the correctness of the algorithm. Logically, in order to prove that a solution exists iff the graph is bipartite, one would have to show that:
I) if the graph is bipartite, we can indeed construct a solution
II) if the graph is not bipartite, we cannot construct a solution

For I) (our graph is bipartite) , I came up with the following observations:
a) The center of a claw must have a degree 3.
b) (using the fact that a bipartite graph is 2 colourable)
It makes sense that the centers of the claws must all have the same colour in our colouring. (Let's say we find a center x with edges to y1, y2, y3. Now, if we eliminate the subgraph containing those edges, in the remaining graph y1, y2, y3 have degree < 3. Thus, by observation a), they can't be centers. The only nodes we can guarantee that they still have degree 3, are the ones with the same colour as x.
However, I can't figure out how one would construct a solution

For II (not a bipartite graph), the only observation I made was that:
- The graph contains an odd length cycle. Furthermore, given the construction of the colouring algorithm, there exists a cycle of length 3.
I'm not sure this is enough to prove that there isn't a solution.

Could anyone help me figure out how to prove this? Some intuitive proof would also help. Thank you in advance!

[raj]

Need Help I am getting Wrong Answer

My Logic: For every connected components there will two independents set of size 3 then answer will be YES
otherwise NO.

am i right?

[bradd123]

This is my code for 11396-Claw Decomposition. It shows wrong answer. Please give me some test cases in which my code fails.
http://pastebin.com/d0JAVYHx

[brianfry713]

bradd123, don't assume that the graph is connected.

[dheer1206]

I also tried the bipartite check algorithm .
But it keeps showing me wrong answer ..
Here is my code ..
http://pastebin.com/FqQTasKs
Please Help...