11396 - Claw Decomposition

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

Moderator: Board moderators

crackerwang
New poster
Posts: 10
Joined: Sun Jan 20, 2008 8:19 am

11396 - Claw Decomposition

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
Learning poster
Posts: 62
Joined: Sun Aug 13, 2006 9:15 am
Location: Bangladesh
Contact:
Output:

Code: Select all

``````YES
YES
``````

Hadi
Learning poster
Posts: 63
Joined: Mon Aug 29, 2005 8:13 am
Location: Tebriz
Contact:
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
Learning poster
Posts: 63
Joined: Mon Aug 29, 2005 8:13 am
Location: Tebriz
Contact:
DP wrote: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
New poster
Posts: 10
Joined: Sun Jan 20, 2008 8:19 am
Hadi wrote: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
New poster
Posts: 46
Joined: Fri Nov 03, 2006 7:53 pm
Location: Madrid
Spoiler:
If somebody is still confused, this is just a graph coloring problem with 2 colors
Last edited by mpi on Sun Jan 20, 2008 9:28 pm, edited 1 time in total.

Hadi
Learning poster
Posts: 63
Joined: Mon Aug 29, 2005 8:13 am
Location: Tebriz
Contact:
mpi wrote:P.D.: Sorry, I didn't want to spoil the party
I think you still have the chance to edit your post

moxlotus
New poster
Posts: 31
Joined: Sat Sep 17, 2011 6:47 am

Re: 11396 - Claw Decomposition

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
New poster
Posts: 11
Joined: Fri Aug 09, 2013 7:25 pm

Re: 11396 - Claw Decomposition

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
Learning poster
Posts: 78
Joined: Fri Feb 15, 2013 5:39 pm

Wrong Answer : 11396 - Claw Decomposition

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
New poster
Posts: 17
Joined: Thu Jul 03, 2014 11:13 am

Re: 11396 - Claw Decomposition

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11396 - Claw Decomposition

bradd123, don't assume that the graph is connected.
Check input and AC output for thousands of problems on uDebug!

dheer1206
New poster
Posts: 1
Joined: Wed Jan 18, 2017 9:09 pm

Re: 11396 - Claw Decomposition

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