Jump to content

Help to explain the article about Split Contraction


Alex12

Recommended Posts

Hello all.

Recently I have read the article: 'A. Agrawa, D. Lokshtanov, S. Saurabh and M. Zehavi. Split Contraction: The Untold Story'.

I am interested in the theorem from the article. The theorem statement can be stated as: «SRBPC parameterized by the number of parts in R is W[1]-hard».

I did not understand what is Split Contraction, SRBPC, Perfect Code and W[1]-hard. Could you please explain it easier for me?

And I need explanation the proof of the theorem.

As I understood, the theorem proofs through some Lemmas. And I ask you to explain for me these lemmas easier.

Thanks.

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
×
×
  • Create New...

Important Information

We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.