All reports by Author Stefan Szeider:

__
TR14-143
| 3rd November 2014
__

Ronald de Haan, Stefan Szeider#### Compendium of Parameterized Problems at Higher Levels of the Polynomial Hierarchy

__
TR13-113
| 19th August 2013
__

Moritz MÃ¼ller, Stefan Szeider#### Revisiting Space in Proof Complexity: Treewidth and Pathwidth

__
TR11-071
| 27th April 2011
__

Serge Gaspers, Stefan Szeider#### The Parameterized Complexity of Local Consistency

Revisions: 1

__
TR07-001
| 19th November 2006
__

Stefan S. Dantchev, Barnaby Martin, Stefan Szeider#### Parameterized Proof Complexity: a Complexity Gap for Parameterized Tree-like Resolution

Revisions: 2

__
TR05-081
| 21st July 2005
__

Michael R. Fellows, Frances A. Rosamond, Udi Rotics, Stefan Szeider#### Proving NP-hardness for clique-width II: non-approximability of clique-width

Revisions: 1

__
TR05-080
| 21st July 2005
__

Michael R. Fellows, Frances A. Rosamond, Udi Rotics, Stefan Szeider#### Proving NP-hardness for clique-width I: non-approximability of sequential clique-width

Revisions: 1

__
TR03-002
| 13th December 2002
__

Stefan Szeider#### Minimal unsatisfiable formulas with bounded clause-variable difference are fixed-parameter tractable

Revisions: 1

__
TR00-049
| 2nd May 2000
__

Herbert Fleischner, Stefan Szeider#### Polynomial-Time Recognition of Minimal Unsatisfiable Formulas with Fixed Clause-Variable Difference

Ronald de Haan, Stefan Szeider

We present a list of parameterized problems together with a complexity classification of whether they allow a fixed-parameter tractable reduction to SAT or not. These parameterized problems are based on problems whose complexity lies at the second level of the Polynomial Hierarchy or higher. The list will be updated as ... more >>>

Moritz MÃ¼ller, Stefan Szeider

So-called ordered variants of the classical notions of pathwidth and treewidth are introduced and proposed as proof theoretically meaningful complexity measures for the directed acyclic graphs underlying proofs. The ordered pathwidth of a proof is shown to be roughly the same as its formula space. Length-space lower bounds for R(k)-refutations ... more >>>

Serge Gaspers, Stefan Szeider

We investigate the parameterized complexity of deciding whether a constraint network is $k$-consistent. We show that, parameterized by $k$, the problem is complete for the complexity class co-W[2]. As secondary parameters we consider the maximum domain size $d$ and the maximum number $\ell$ of constraints in which a variable occurs. ... more >>>

Stefan S. Dantchev, Barnaby Martin, Stefan Szeider

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 >>>

Michael R. Fellows, Frances A. Rosamond, Udi Rotics, Stefan Szeider

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 >>>

Michael R. Fellows, Frances A. Rosamond, Udi Rotics, Stefan Szeider

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 >>>

Stefan Szeider

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 >>>

Herbert Fleischner, Stefan Szeider