Igor Razgon

TCS Journal 2023 Journal Article

Fractional covers of hypergraphs with bounded multi-intersection

• Georg Gottlob
• Matthias Lanzinger
• Reinhard Pichler
• Igor Razgon

Fractional (hyper-)graph theory is concerned with the specific problems that arise when fractional analogues of otherwise integer-valued (hyper-)graph invariants are considered. The focus of this paper is on fractional edge covers of hypergraphs. Our main technical result generalizes and unifies previous conditions under which the size of the support of fractional edge covers is bounded independently of the size of the hypergraph itself. We show how this combinatorial result can be used to extend previous tractability results for checking if the fractional hypertree width of a given hypergraph is ≤k for some constant k. Moreover, we show a dual version of our main result for fractional hitting sets.

MFCS Conference 2020 Conference Paper

Fractional Covers of Hypergraphs with Bounded Multi-Intersection

• Georg Gottlob
• Matthias Lanzinger
• Reinhard Pichler
• Igor Razgon

Fractional (hyper-)graph theory is concerned with the specific problems that arise when fractional analogues of otherwise integer-valued (hyper-)graph invariants are considered. The focus of this paper is on fractional edge covers of hypergraphs. Our main technical result generalizes and unifies previous conditions under which the size of the support of fractional edge covers is bounded independently of the size of the hypergraph itself. This allows us to extend previous tractability results for checking if the fractional hypertree width of a given hypergraph is ≤ k for some constant k. We also show how our results translate to fractional vertex covers.

KR Conference 2014 Conference Paper

On OBDDs for CNFs of bounded treewidth

• Igor Razgon

In this paper we show that a CNF cannot be compiled into an Ordered Binary Decision Diagram (OBDD) of fixedparameter size parameterized by the primal graph treewidth of the CNF. Thus we provide a parameterized separation between OBDDs and Sentential Decision Diagrams for which such fixed-parameter compilation is possible. We also show that the best existing parameterized upper bound for OBDDs in fact holds for incidence graph treewidth parameterization.

SAT Conference 2013 Conference Paper

Cliquewidth and Knowledge Compilation

• Igor Razgon
• Justyna Petke

Abstract In this paper we study the role of cliquewidth in succinct representation of Boolean functions. Our main statement is the following: Let Z be a Boolean circuit having cliquewidth k. Then there is another circuit Z * computing the same function as Z having treewidth at most 18 k + 2 and which has at most 4| Z | gates where | Z | is the number of gates of Z. In this sense, cliquewidth is not more ‘powerful’ than treewidth for the purpose of representation of Boolean functions. We believe this is quite a surprising fact because it contrasts the situation with graphs where an upper bound on the treewidth implies an upper bound on the cliquewidth but not vice versa. We demonstrate the usefulness of the new theorem for knowledge compilation. In particular, we show that a circuit Z of cliquewidth k can be compiled into a Decomposable Negation Normal Form ( dnnf ) of size O (9 18 k k 2 | Z |) and the same runtime. To the best of our knowledge, this is the first result on efficient knowledge compilation parameterized by cliquewidth of a Boolean circuit.

STOC Conference 2011 Conference Paper

Fixed-parameter tractability of multicut parameterized by the size of the cutset

• Dániel Marx
• Igor Razgon

TCS Journal 2009 Journal Article

Minimum leaf out-branching and related problems

• Gregory Gutin
• Igor Razgon
• Eun Jung Kim

Given a digraph D, the Minimum Leaf Out-Branching problem (MinLOB) is the problem of finding in D an out-branching with the minimum possible number of leaves, i. e. , vertices of out-degree 0. We prove that MinLOB is polynomial-time solvable for acyclic digraphs. In general, MinLOB is NP-hard and we consider three parameterizations of MinLOB. We prove that two of them are NP-complete for every value of the parameter, but the third one is fixed-parameter tractable (FPT). The FPT parameterization is as follows: given a digraph D of order n and a positive integral parameter k, check whether D contains an out-branching with at most n − k leaves (and find such an out-branching if it exists). We find a problem kernel of order O ( k 2 ) and construct an algorithm of running time O ( 2 O ( k log k ) + n 6 ), which is an ‘additive’ FPT algorithm. We also consider transformations from two related problems, the minimum path covering and the maximum internal out-tree problems into MinLOB, which imply that some parameterizations of the two problems are FPT as well.

SAT Conference 2009 Conference Paper

Solving SAT for CNF Formulas with a One-Sided Restriction on Variable Occurrences

• Daniel Johannsen
• Igor Razgon
• Magnus Wahlström

Abstract In this paper we consider the class of boolean formulas in Conjunctive Normal Form (CNF) where for each variable all but at most d occurrences are either positive or negative. This class is a generalization of the class of CNF formulas with at most d occurrences (positive and negative) of each variable which was studied in [Wahlström, 2005]. Applying complement search [Purdom, 1984], we show that for every d there exists a constant \(\gamma_d<2-\frac{1}{2d+1}\) such that satisfiability of a CNF formula on n variables can be checked in runtime \({\ensuremath{{O}}}(\gamma_d^n)\) if all but at most d occurrences of each variable are either positive or negative. We thoroughly analyze the proposed branching strategy and determine the asymptotic growth constant γ d more precisely. Finally, we show that the trivial \({\ensuremath{{O}}}(2^n)\) barrier of satisfiability checking can be broken even for a more general class of formulas, namely formulas where the positive or negative literals of every variable have what we will call a d–covering. To the best of our knowledge, for the considered classes of formulas there are no previous non-trivial upper bounds on the complexity of satisfiability checking.

STOC Conference 2008 Conference Paper

A fixed-parameter algorithm for the directed feedback vertex set problem

• Jianer Chen
• Yang Liu 0002
• Songjian Lu
• Barry O'Sullivan
• Igor Razgon

IJCAI Conference 2005 Conference Paper

CSP Search with Responsibility Sets and Kernels

• Igor Razgon
• Amnon

We introduce data structures called responsibility set and kernel. We present an algorithm FC- RK, which is a modification of FC that maintains these structures and uses them for pruning of the search space. According to our experimental evaluation, FC-RK outperforms FC-CBJ on constraint networks encoding graph k-coloring instances and on non-dense random binary constraint networks.