Outputs (5)

Clique-width minimization is NP-hard (2006)
Conference Proceeding
Fellows, M. R., Rosamond, F. A., Rotics, U., & Szeider, S. (2006). Clique-width minimization is NP-hard. . https://doi.org/10.1145/1132516.1132568

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 problem... Read More about Clique-width minimization is NP-hard.

Backdoor Sets for DLL Subsolvers (2005)
Journal Article
Szeider, S. (2005). Backdoor Sets for DLL Subsolvers. Journal of Automated Reasoning, 35(1-3), 73-88. https://doi.org/10.1007/s10817-005-9007-9

We study the parameterized complexity of detecting small backdoor sets for instances of the propositional satisfiability problem (SAT). The notion of backdoor sets has been recently introduced by Williams, Gomes, and Selman for explaining the ‘heavy-... Read More about Backdoor Sets for DLL Subsolvers.

The Complexity of Resolution with Generalized Symmetry Rules (2005)
Journal Article
Szeider, S. (2005). The Complexity of Resolution with Generalized Symmetry Rules. Theory of Computing Systems, 38(2), 171-188. https://doi.org/10.1007/s00224-004-1192-0

We generalize Krishnamurthys well-studied symmetry rule for resolution systems by considering homomorphisms instead of symmetries; symmetries are injective maps of literals whichpreserve complements and clauses; homomorphisms arise from symmetries by... Read More about The Complexity of Resolution with Generalized Symmetry Rules.

Minimal unsatisfiable formulas with bounded clause-variable difference are fixed-parameter tractable (2004)
Journal Article
Szeider, S. (2004). Minimal unsatisfiable formulas with bounded clause-variable difference are fixed-parameter tractable. Journal of Computer and System Sciences, 69(4), 656-674. https://doi.org/10.1016/j.jcss.2004.04.009

Recognition of minimal unsatisfiable CNF formulas (unsatisfiable CNF formulas which become satisfiable if any clause is removed) is a classical DP-complete problem. It was shown recently that minimal unsatisfiable formulas with n variables and n+k cl... Read More about Minimal unsatisfiable formulas with bounded clause-variable difference are fixed-parameter tractable.

Finding Paths in Graphs Avoiding Forbidden Transitions; (2003)
Journal Article
Szeider, S. (2003). Finding Paths in Graphs Avoiding Forbidden Transitions;. Discrete Applied Mathematics, 126(2-3), 261-273. https://doi.org/10.1016/s0166-218x%2802%2900251-2

Let v be a vertex of a graph G; a transition graph T(v) of v is a graph whose vertices are the edges incident with v. We consider graphs G with prescribed transition systems T={T(v) | vV(G)}. A path P in G is called T-compatible, if each pair uv,vw o... Read More about Finding Paths in Graphs Avoiding Forbidden Transitions;.