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 …

For a tree decomposition $\mathcal {T} $ of a graph $ G $, by $\mu (\mathcal {T}) $ we
denote the size of a largest induced matching in $ G $ all of whose edges intersect one bag …

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 …

A matching M in a graph G is an acyclic matching if the subgraph of G induced by the
endpoints of the edges of M is a forest. Given a graph G and ℓ∈ N, Acyclic Matching asks …

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 …

In this paper, we prove that assuming the exponential time hypothesis (ETH), there is no
f(k)⋅n^k^o(1/\log\logk)-time algorithm that can decide whether an n-vertex graph contains a …

Given a simple graph $ G $ and an integer $ k $, the goal of $ k $-Clique problem is to
decide if $ G $ contains a complete subgraph of size $ k $. We say an algorithm …

The disjoint paths logic, FOL+ DP, is an extension of First-Order Logic (FOL) with the extra
atomic predicate dp k (x 1, y 1,…, xk, yk), expressing the existence of internally vertex …

The Parameterized Inapproximability Hypothesis (PIH) asserts that no fixed parameter
tractable (FPT) algorithm can distinguish a satisfiable CSP instance, parameterized by the …

The goal of this paper is to understand how exponential-time approximation algorithms can
be obtained from existing polynomial-time approximation algorithms, existing parameterized …