Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with tree-width:
TR03-002 | 13th December 2002
Stefan Szeider

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

Revisions: 1

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

TR14-145 | 4th November 2014
Yuan Li, Alexander Razborov, Benjamin Rossman

On the $AC^0$ Complexity of Subgraph Isomorphism

Let $P$ be a fixed graph (hereafter called a ``pattern''), and let
$Subgraph(P)$ denote the problem of deciding whether a given graph $G$
contains a subgraph isomorphic to $P$. We are interested in
$AC^0$-complexity of this problem, determined by the smallest possible exponent
$C(P)$ for which $Subgraph(P)$ possesses bounded-depth circuits ... more >>>

ISSN 1433-8092 | Imprint