Author name cluster

Igor Razgon

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

9 papers

2 author rows

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.

Details DOI

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.

Details

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.

Details

STOC Conference 2011 Conference Paper

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

Dániel Marx
Igor Razgon

Given an undirected graph $G$, a collection {(s 1 ,t 1 ), ..., (s l ,t l )} of pairs of vertices, and an integer p, the Edge Multicut problem ask if there is a set S of at most p edges such that the removal of S disconnects every s i from the corresponding t i . Vertex Multicut is the analogous problem where S is a set of at most p vertices. Our main result is that both problems can be solved in time 2 O(p 3 ) ⋅ n O(1) , i.e., fixed-parameter tractable parameterized by the size p of the cutset in the solution. By contrast, it is unlikely that an algorithm with running time of the form f(p) ⋅ n O(1) exists for the directed version of the problem, as we show it to be W[1]-hard parameterized by the size of the cutset.

Details

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.

Details DOI

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.

Details

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

The (parameterized) feedback vertex set problem on directed graphs, which we refer to as the dfvs problem, is defined as follows: given a directed graph G and a parameter k, either construct a feedback vertex set of at most k vertices in G or report that no such set exists. Whether or not the dfvs problem is fixed-parameter tractable has been a well-known open problem in parameterized computation and complexity, i.e., whether the problem can be solved in time f(k)n O(1) for some function f. In this paper we develop new algorithmic techniques that result in an algorithm with running time 4 k k! n O(1) for the dfvs problem, thus showing that this problem is fixed-parameter tractable.

Details

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.

PDF