research
∙
02/21/2023
New Width Parameters for Independent Set: One-sided-mim-width and Neighbor-depth
We study the tractability of the maximum independent set problem from th...
share
research
∙
12/27/2022
FPT algoritms providing constant ratio approximation of hypertree width parameters for hypergraphs of bounded rank
We propose an algorithm whose input are parameters k and r and a hypergr...
research
∙
02/15/2022
The treewidth and pathwidth of graph unions
For two graphs G_1 and G_2 on the same vertex set [n]:={1,2, …, n}, and ...
research
∙
01/06/2022
The splitting power of branching programs of bounded repetition and CNFs of bounded width
In this paper we study syntactic branching programs of bounded repetitio...
research
∙
03/16/2021
Classification of OBDD size for monotone 2-CNFs
We introduce a new graph parameter called linear upper maximum induced m...
research
∙
12/02/2020
Tree-width dichotomy
We prove that the tree-width of graphs in a hereditary class defined by ...
research
∙
07/03/2020
Fractional Covers of Hypergraphs with Bounded Multi-Intersection
Fractional (hyper-)graph theory is concerned with the specific problems ...
research
∙
02/12/2020
Complexity Analysis of Generalized and Fractional Hypertree Decompositions
Hypertree decompositions (HDs), as well as the more powerful generalized...
research
∙
02/12/2020
Complexity Analysis of General and Fractional Hypertree Decompositions
Hypertree decompositions (HDs), as well as the more powerful generalized...
research
∙
05/26/2019
Regular resolution for CNF of bounded incidence treewidth with few long clauses
We demonstrate that Regular Resolution is FPT for two restricted familie...
research
∙
05/24/2018
Linear read-once and related Boolean functions
It is known that a positive Boolean function f depending on n variables ...
research
∙
09/26/2017
Partial matching width and its application to lower bounds for branching programs
We introduce a new structural graph parameter called partial matching wi...
research
∙
08/25/2017
Non-FPT lower bounds for structural restrictions of decision DNNF
We give a non-FPT lower bound on the size of structured decision DNNF an...
research
∙
10/10/2015
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 deci...
research
∙
11/02/2014
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-determinist...
research
∙
01/16/2014