Skip to main content
edited tags
Link
added 21 characters in body
Source Link

Parametrized maximum independent clauses problem:
Input : A kr-CNFSAT formula F having n variables and m clauses, k
Ques : Does there exists at least k clauses such that they are mutually independent i.e. no variable occurs more than once in all these clauses combined.
Parameter : k
I would like to know whether this problem is in FPT or not. In both situations, an idea to proceed forward will be appreciated.

Parametrized maximum independent clauses problem:
Input : A k-CNFSAT formula F having n variables and m clauses, k
Ques : Does there exists at least k clauses such that they are mutually independent i.e. no variable occurs more than once in all these clauses combined.
I would like to know whether this problem is in FPT or not. In both situations, an idea to proceed forward will be appreciated.

Parametrized maximum independent clauses problem:
Input : A r-CNFSAT formula F having n variables and m clauses, k
Ques : Does there exists at least k clauses such that they are mutually independent i.e. no variable occurs more than once in all these clauses combined.
Parameter : k
I would like to know whether this problem is in FPT or not. In both situations, an idea to proceed forward will be appreciated.

Source Link

Is parametrized maximum independent clauses problem in FPT?

Parametrized maximum independent clauses problem:
Input : A k-CNFSAT formula F having n variables and m clauses, k
Ques : Does there exists at least k clauses such that they are mutually independent i.e. no variable occurs more than once in all these clauses combined.
I would like to know whether this problem is in FPT or not. In both situations, an idea to proceed forward will be appreciated.