19 citations · 44 across the 21 of their papers we have counts for
6 papers · 1 filter
Solving Partition Problems Almost Always Requires Pushing Many Vertices Around
Iyad Kanj, Christian Komusiewicz, Manuel Sorge +1
A fundamental graph problem is to recognize whether the vertex set of a graph can be bipartitioned into sets and such that and satisfy properties an…
The Complexity of Tree Partitioning
Zhao An, Qilong Feng, Iyad Kanj +1
Given a tree on vertices, and , the Tree Partitioning problem asks if at most edges can be removed from so that the resulting componen…
Parameterized Algorithms for Recognizing Monopolar and 2-Subcolorable Graphs
Iyad Kanj, Christian Komusiewicz, Manuel Sorge +1
A graph is a -graph if can be bipartitioned into and such that satisfies property and satisfies property . The $(Π_{A},Π_{B})…
On the Subexponential Time Complexity of CSP
Iyad Kanj, Stefan Szeider
A CSP with n variables ranging over a domain of d values can be solved by brute-force in d^n steps (omitting a polynomial factor). With a more careful approach, this trivial upper…
Local Backbones
Ronald de Haan, Iyad Kanj, Stefan Szeider
A backbone of a propositional CNF formula is a variable whose truth value is the same in every truth assignment that satisfies the formula. The notion of backbones for CNF formulas…
What makes normalized weighted satisfiability tractable
Iyad Kanj, Ge Xia
We consider the weighted antimonotone and the weighted monotone satisfiability problems on normalized circuits of depth at most , abbreviated {\sc wsat} and {\sc w…