Approximately counting and sampling small witnesses using a colorful decision oracle
In this paper, we design efficient algorithms to approximately count the number of edges of a
given k-hypergraph, and to sample an approximately uniform random edge. The hypergraph …
given k-hypergraph, and to sample an approximately uniform random edge. The hypergraph …
[HTML][HTML] Refined notions of parameterized enumeration kernels with applications to matching cut enumeration
An enumeration kernel as defined by Creignou et al.(2017)[11] for a parameterized
enumeration problem consists of an algorithm that transforms each instance into one whose …
enumeration problem consists of an algorithm that transforms each instance into one whose …
Efficiently enumerating hitting sets of hypergraphs arising in data profiling
The transversal hypergraph problem asks to enumerate the minimal hitting sets of a
hypergraph. If the solutions have bounded size, Eiter and Gottlob [SICOMP'95] gave an …
hypergraph. If the solutions have bounded size, Eiter and Gottlob [SICOMP'95] gave an …
The (Coarse) Fine-Grained Structure of NP-Hard SAT and CSP Problems
V Lagerkvist, M Wahlström - ACM Transactions on Computation Theory …, 2021 - dl.acm.org
We study the fine-grained complexity of NP-complete satisfiability (SAT) problems and
constraint satisfaction problems (CSPs) in the context of the strong exponential-time …
constraint satisfaction problems (CSPs) in the context of the strong exponential-time …
Densification of witnesses for randomized algorithm design
X Wang - Journal of Advances in Mathematics and …, 2023 - ebooks.manu2sent.com
This paper investigates the densification of witnesses for randomized algorithm design and
its application in factoring integers. By defining a set operation named with Cartesian …
its application in factoring integers. By defining a set operation named with Cartesian …
Quantum Parameterized Complexity
Parameterized complexity theory was developed in the 1990s to enrich the complexity-
theoretic analysis of problems that depend on a range of parameters. In this paper we …
theoretic analysis of problems that depend on a range of parameters. In this paper we …
Which NP-hard SAT and CSP problems admit exponentially improved algorithms?
V Lagerkvist, M Wahlström - arXiv preprint arXiv:1801.09488, 2018 - arxiv.org
We study the complexity of SAT ($\Gamma $) problems for potentially infinite languages
$\Gamma $ closed under variable negation (sign-symmetric languages). Via an algebraic …
$\Gamma $ closed under variable negation (sign-symmetric languages). Via an algebraic …
Listing all fixed-length simple cycles in sparse graphs in optimal time
G Manoussakis - … Symposium on Fundamentals of Computation Theory, 2017 - Springer
The degeneracy of an n-vertex graph G is the smallest number k such that every subgraph of
G contains a vertex of degree at most k. We present an algorithm for enumerating all simple …
G contains a vertex of degree at most k. We present an algorithm for enumerating all simple …
[引用][C] On the enumeration of minimal hitting sets in lexicographical order
[引用][C] Computing the permanental polynomial of 4k-intercyclic bipartite graphs
H Wankhede, R Singh, RB Bapat - 2023