[PDF][PDF] Various properties of various ultrafilters, various graph width parameters, and various connectivity systems
T Fujita - arXiv preprint arXiv, 2024 - researchgate.net
This paper investigates ultrafilters in the context of connectivity systems, defined as pairs (X,
f) where X is a finite set and f is a symmetric submodular function. Ultrafilters, essential in …
f) where X is a finite set and f is a symmetric submodular function. Ultrafilters, essential in …
A Short Review on Novel Approaches for Maximum Clique Problem: from Classical algorithms to Graph Neural Networks and Quantum algorithms
This manuscript provides a comprehensive review of the Maximum Clique Problem, a
computational problem that involves finding subsets of vertices in a graph that are all …
computational problem that involves finding subsets of vertices in a graph that are all …
Parameterized analysis and crossing minimization problems
M Zehavi - Computer Science Review, 2022 - Elsevier
In this survey/introductory article, we first present the basics of the field of Parameterized
Complexity, made accessible to readers without background on the subject. Afterwards, we …
Complexity, made accessible to readers without background on the subject. Afterwards, we …
Computing tree decompositions with small independence number
The independence number of a tree decomposition is the maximum of the independence
numbers of the subgraphs induced by its bags. The tree-independence number of a graph is …
numbers of the subgraphs induced by its bags. The tree-independence number of a graph is …
FPT-approximation for FPT problems
Over the past decade, many results have focused on the design of parameterized
approximation algorithms for W [1]-hard problems. However, there are fundamental …
approximation algorithms for W [1]-hard problems. However, there are fundamental …
Constant approximating k-clique is w [1]-hard
B Lin - Proceedings of the 53rd Annual ACM SIGACT …, 2021 - dl.acm.org
For every graph G, let ω (G) be the largest size of complete subgraph in G. This paper
presents a simple algorithm which, on input a graph G, a positive integer k and a small …
presents a simple algorithm which, on input a graph G, a positive integer k and a small …
Planar disjoint paths, treewidth, and kernels
M Włodarczyk, M Zehavi - 2023 IEEE 64th Annual Symposium …, 2023 - ieeexplore.ieee.org
In the PLANAR DISJOINT PATHS problem, one is given an undirected planar graph with a
set of k vertex pairs \left(s_i,t_i\right) and the task is to find k pairwise vertex-disjoint paths …
set of k vertex pairs \left(s_i,t_i\right) and the task is to find k pairwise vertex-disjoint paths …
Almost polynomial factor inapproximability for parameterized k-clique
CS Karthik, S Khot - 37th Computational Complexity Conference …, 2022 - drops.dagstuhl.de
The k-Clique problem is a canonical hard problem in parameterized complexity. In this
paper, we study the parameterized complexity of approximating the k-Clique problem where …
paper, we study the parameterized complexity of approximating the k-Clique problem where …
Parameterized Inapproximability of the Minimum Distance Problem over All Fields and the Shortest Vector Problem in All ℓp Norms
We prove that the Minimum Distance Problem (MDP) on linear codes over any fixed finite
field and parameterized by the input distance bound is W [1]-hard to approximate within any …
field and parameterized by the input distance bound is W [1]-hard to approximate within any …
Baby pih: Parameterized inapproximability of min csp
V Guruswami, X Ren, S Sandeep - arXiv preprint arXiv:2310.16344, 2023 - arxiv.org
The Parameterized Inapproximability Hypothesis (PIH) is the analog of the PCP theorem in
the world of parameterized complexity. It asserts that no FPT algorithm can distinguish a …
the world of parameterized complexity. It asserts that no FPT algorithm can distinguish a …