We propose a proof-theoretic approach for gaining evidence that certain parameterized problems are not fixed-parameter tractable. We consider proofs that witness that a given propositional formula cannot be satisfied by a truth assignment that sets at most k variables to true, considering k as the parameter. One could separate the ... more >>>

Clique-width is a graph parameter that measures in a certain sense the complexity of a graph. Hard graph problems (e.g., problems expressible in Monadic Second Order Logic with second-order quantification on vertex sets, that includes NP-hard problems) can be solved efficiently for graphs of certified small clique-width. It is widely ... more >>>

Clique-width is a graph parameter, defined by a composition mechanism for vertex-labeled graphs, which measures in a certain sense the complexity of a graph. Hard graph problems (e.g., problems expressible in Monadic Second Order Logic, that includes NP-hard problems) can be solved efficiently for graphs of certified small clique-width. It ... more >>>

The deficiency of a propositional formula F in CNF with n variables and m clauses is defined as m-n. It is known that minimal unsatisfiable formulas (unsatisfiable formulas which become satisfiable by removing any clause) have positive deficiency. Recognition of minimal unsatisfiable formulas is NP-hard, and it was shown recently ... more >>>

more >>>