BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Igor Razgon

Igor Razgon appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Data Structures and AlgorithmsComputational ComplexityDiscrete Mathematicsmath.COArtificial IntelligenceLogic in Computer Science

Catalog footprint

What is connected

19works
6topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

19 published item(s)

preprint2024arXiv

FPT Approximation of Generalised Hypertree Width for Bounded Intersection Hypergraphs

Generalised hypertree width ($ghw$) is a hypergraph parameter that is central to the tractability of many prominent problems with natural hypergraph structure. Computing $ghw$ of a hypergraph is notoriously hard. The decision version of the problem, checking whether $ghw(H) \leq k$, is paraNP-hard when parameterised by $k$. Furthermore, approximation of $ghw$ is at least as hard as approximation of Set-Cover, which is known to not admit any fpt approximation algorithms. Research in the computation of ghw so far has focused on identifying structural restrictions to hypergraphs -- such as bounds on the size of edge intersections -- that permit XP algorithms for $ghw$. Yet, even under these restrictions that problem has so far evaded any kind of fpt algorithm. In this paper we make the first step towards fpt algorithms for $ghw$ by showing that the parameter can be approximated in fpt time for graphs of bounded edge intersection size. In concrete terms we show that there exists an fpt algorithm, parameterised by $k$ and $d$, that for input hypergraph $H$ with maximal cardinality of edge intersections $d$ and integer $k$ either outputs a tree decomposition with $ghw(H) \leq 4k(k+d+1+)(2k-1)$, or rejects, in which case it is guaranteed that $ghw(H) > k$. Thus, in the special case, of hypergraphs of bounded edge intersection, we obtain an fpt $O(k^3)$-approximation algorithm for $ghw$.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Regular resolution for CNFs with almost bounded one-sided treewidth

We introduce a one-sided incidence tree decomposition of a CNF $φ$. This is a tree decomposition of the incidence graph of $φ$ where the underlying tree is rooted and the set of bags containing each clause induces a directed path in the tree. The one-sided treewidth is the smallest width of a one-sided incidence tree decomposition. We consider a class of unsatisfiable CNF $φ$ that can be turned into one of one sided treewidth at most $k$ by removal of at most $p$ clauses. We show that the size of regular resolution for this class of CNFs is FPT parameterized by $k$ and $p$. The results contributes to understanding the complexity of resolution for CNFs of bounded incidence treewidth, an open problem well known in the areas of proof complexity and knowledge compilation. In particular, the result significantly generalizes all the restricted classes of CNFs of bounded incidence treewidth that are known to admit an FPT sized resolution. The proof includes an auxiliary result and several new notions that may be of an independent interest.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

The splitting power of branching programs of bounded repetition and CNFs of bounded width

In this paper we study syntactic branching programs of bounded repetition representing CNFs of bounded treewidth. For this purpose we introduce two new structural graph parameters $d$-pathwidth and clique preserving $d$-pathwidth denoted by $d-pw(G)$ and $d-cpw(G)$ where $G$ is a graph. We show that $2-cpw(G) \leq O(tw(G) Δ(G))$ where $tw(G)$ and $Δ(G)$ are, respectively the treewidth and maximal degree of $G$. Using this upper bound, we demonstrate that each CNF $ψ$ can be represented as a conjunction of two OBDDs of size $2^{O(Δ(ψ)*tw(ψ)^2)}$ where $tw(ψ)$ is the treewidth of the primal graph of $ψ$ and each variable occurs in $ψ$ at most $Δ(ψ)$ times. Next we use $d$-pathwdith to obtain lower bounds for monotone branching programs. In particular, we consider the monotone version of syntactic nondeterministic read $d$ times branching programs (just forbidding negative literals as edge labels) and introduce a further restriction that each computational path can be partitioned into at most $d$ read-once subpaths. We call the resulting model separable monotone read $d$ times branching programs and abbreviate them $d$-SMNBPs. For each graph $G$ without isolated vertices, we introduce a CNF $ψ(G)$ whsose clauses are $(u \vee e \vee v)$ for each edge $e=\{u,v\}$ of $G$. We prove that a $d$-SMNBP representing $ψ(G)$ is of size at least $Ω(c^{d-pw(G)})$ where $c=(8/7)^{1/12}$. We use this 'generic' lower bound to obtain an exponential lower bound for a 'concrete' class of CNFs $ψ(K_n)$. In particular, we demonstrate that for each $0<a<1$, the size of $n^{a}$-SMNBP representing $ψ(K_n)$ is at least $c^{n^b}$ where $b$ is an arbitrary constant such that $a+b<1$. This lower bound is tight in the sense $ψ(K_n)$ can be represented by a poly-sized $n$-SMNBP.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Non-deterministic branching programs with logarithmic repetition cannot efficiently compute small monotone CNFs

In this paper we establish an exponential lower bound on the size of syntactic non-deterministic read $d$-times branching programs for $d \leq \log n /10^5$ computing a class of monotone CNFs with a linear number of clauses. This result provides the first separation of classes NP and co-NP for syntactic branching programs with a logarithmic repetition and the first separation of syntactic non-deterministic branching programs with a logarithmic repetition from small monotone CNFs.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Two types of branching programs with bounded repetition that cannot efficiently compute monotone 3-CNFs

It is known that there are classes of 2-CNFs requiring exponential size non-deterministic read-once branching programs to compute them. However, to the best of our knowledge, there are no superpolynomial lower bounds for branching programs of a higher repetition computing a class of 2-CNFs. This work is an attempt to make a progress in this direction. We consider a class of monotone 3-CNFs that are almost 2-CNFs in the sense that in each clause there is a literal occurring in this clause only. We prove exponential lower bounds for two classes of non-deterministic branching programs. The first class significantly generalizes monotone read-$k$-times {\sc nbp}s and the second class generalizes oblivious read $k$ times branching programs. The lower bounds remain exponential for $k \leq \log n/a$ where $a$ is a sufficiently large constant.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Graphs without large bicliques and well-quasi-orderability by the induced subgraph relation

Recently, Daligault, Rao and Thomassé asked in [3] if every hereditary class which is well-quasi-ordered by the induced subgraph relation is of bounded clique-width. There are two reasons why this questions is interesting. First, it connects two seemingly unrelated notions. Second, if the question is answered affirmatively, this will have a strong algorithmic consequence. In particular, this will mean (through the use of Courcelle theorem [2]), that any problem definable in Monadic Second Order Logic can be solved in a polynomial time on any class well-quasi-ordered by the induced subgraph relation. In the present paper, we answer this question affirmatively for graphs without large bicliques. Thus the above algorithmic consequence is true, for example, for classes of graphs of bounded degree.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

On oblivious branching programs with bounded repetition that cannot efficiently compute CNFs of bounded treewidth

In this paper we study complexity of an extension of ordered binary decision diagrams (OBDDs) called $c$-OBDDs on CNFs of bounded (primal graph) treewidth. In particular, we show that for each $k$ there is a class of CNFs of treewidth $k \geq 3$ for which the equivalent $c$-OBDDs are of size $Ω(n^{k/(8c-4)})$. Moreover, this lower bound holds if $c$-OBDD is non-deterministic and semantic. Our second result uses the above lower bound to separate the above model from sentential decision diagrams (SDDs). In order to obtain the lower bound, we use a structural graph parameter called matching width. Our third result shows that matching width and pathwidth are linearly related.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

On the read-once property of branching programs and CNFs of bounded treewidth

In this paper we prove a space lower bound of $n^{Ω(k)}$ for non-deterministic (syntactic) read-once branching programs ({\sc nrobp}s) on functions expressible as {\sc cnf}s with treewidth at most $k$ of their primal graphs. This lower bound rules out the possibility of fixed-parameter space complexity of {\sc nrobp}s parameterized by $k$. We use lower bound for {\sc nrobp}s to obtain a quasi-polynomial separation between Free Binary Decision Diagrams and Decision Decomposable Negation Normal Forms, essentially matching the existing upper bound introduced by Beame et al. and thus proving the tightness of the latter.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

No small nondeterministic read-once branching programs for CNFs of bounded treewidth

In this paper, given a parameter $k$, we demonstrate an infinite class of {\sc cnf}s of treewidth at most $k$ of their primary graphs such that the equivalent nondeterministic read-once branching programs ({\sc nrobp}s) are of size at least $n^{ck}$ for some universal constant $c$. Thus we rule out the possibility of fixed-parameter space complexity of {\sc nrobp}s parameterized by the smallest treewidth of the equivalent {\sc cnf}.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

On OBDDs for CNFs of bounded treewidth

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

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Soft Constraints of Difference and Equality

In many combinatorial problems one may need to model the diversity or similarity of assignments in a solution. For example, one may wish to maximise or minimise the number of distinct values in a solution. To formulate problems of this type, we can use soft variants of the well known AllDifferent and AllEqual constraints. We present a taxonomy of six soft global constraints, generated by combining the two latter ones and the two standard cost functions, which are either maximised or minimised. We characterise the complexity of achieving arc and bounds consistency on these constraints, resolving those cases for which NP-hardness was neither proven nor disproven. In particular, we explore in depth the constraint ensuring that at least k pairs of variables have a common value. We show that achieving arc consistency is NP-hard, however achieving bounds consistency can be done in polynomial time through dynamic programming. Moreover, we show that the maximum number of pairs of equal variables can be approximated by a factor 1/2 with a linear time greedy algorithm. Finally, we provide a fixed parameter tractable algorithm with respect to the number of values appearing in more than two distinct domains. Interestingly, this taxonomy shows that enforcing equality is harder than enforcing difference.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Cliquewidth and Knowledge Compilation

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 $18k+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 ({\sc dnnf}) of size $O(9^{18k}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.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

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

Given an undirected graph $G$, a collection $\{(s_1,t_1),..., (s_k,t_k)\}$ 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.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Finding small separators in linear time via treewidth reduction

We present a method for reducing the treewidth of a graph while preserving all of its minimal $s-t$ separators up to a certain fixed size $k$. This technique allows us to solve $s-t$ Cut and Multicut problems with various additional restrictions (e.g., the vertices being removed from the graph form an independent set or induce a connected graph) in linear time for every fixed number $k$ of removed vertices. Our results have applications for problems that are not directly defined by separators, but the known solution methods depend on some variant of separation. for example, we can solve similarly restricted generalizations of Bipartization (delete at most $k$ vertices from $G$ to make it bipartite) in almost linear time for every fixed number $k$ of removed vertices. These results answer a number of open questions in the area of parameterized complexity. Furthermore, our technique turns out to be relevant for $(H,C,K)$- and $(H,C,\le K)$-coloring problems as well, which are cardinality constrained variants of the classical $H$-coloring problem. We make progress in the classification of the parameterized complexity of these problems by identifying new cases that can be solved in almost linear time for every fixed cardinality bound.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Large Isolating Cuts Shrink the Multiway Cut

We propose a preprocessing algorithm for the multiway cut problem that establishes its polynomial kernelizability when the difference between the parameter $k$ and the size of the smallest isolating cut is at most $log(k)$. To the best of our knowledge, this is the first progress towards kernelization of the multiway cut problem. We pose two open questions that, if answered affirmatively, would imply, combined with the proposed result, unconditional polynomial kernelizability of the multiway cut problem.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Computing multiway cut within the given excess over the largest minimum isolating cut

Let $(G,T)$ be an instance of the (vertex) multiway cut problem where $G$ is a graph and $T$ is a set of terminals. For $t \in T$, a set of nonterminal vertices separating $t$ from $T \setminus \{T\}$ is called an \emph{isolating cut} of $t$. The largest among all the smallest isolating cuts is a natural lower bound for a multiway cut of $(G,T)$. Denote this lower bound by $m$ and let $k$ be an integer. In this paper we propose an $O(kn^{k+3})$ algorithm that computes a multiway cut of $(G,T)$ of size at most $m+k$ or reports that there is no such multiway cut. The core of the proposed algorithm is the following combinatorial result. Let $G$ be a graph and let $X,Y$ be two disjoint subsets of vertices of $G$. Let $m$ be the smallest size of a vertex $X-Y$ separator. Then, for the given integer $k$, the number of \emph{important} $X-Y$ separators \cite{MarxTCS} of size at most $m+k$ is at most $\sum_{i=0}^k{n \choose i}$.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Treewidth reduction for constrained separation and bipartization problems

We present a method for reducing the treewidth of a graph while preserving all the minimal $s-t$ separators. This technique turns out to be very useful for establishing the fixed-parameter tractability of constrained separation and bipartization problems. To demonstrate the power of this technique, we prove the fixed-parameter tractability of a number of well-known separation and bipartization problems with various additional restrictions (e.g., the vertices being removed from the graph form an independent set). These results answer a number of open questions in the area of parameterized complexity.

0 citations0 reviewsNo code linkedOpen access