What does it mean today to study a problem from a computational point of view? We focus
on parameterized complexity and on Column 16 “Graph Restrictions and Their Effect” of DS …

Given a tree T on n vertices, and k, b, s_1, ..., s_b ∈ N k, b, s 1,…, sb∈ N, the Tree
Partitioning problem asks if at most k edges can be removed from T so that the resulting …

We prove essentially tight lower bounds, conditionally to the Exponential Time Hypothesis,
for two fundamental but seemingly very different cutting problems on surface-embedded …

Not all NP-complete problems share the same practical hardness with respect to exact
computation. Whereas some NP-complete problems are amenable to efficient computational …

Given an edge-weighted graph $ G $ on $ n $ nodes, the NP-hard Max-Cut problem asks for
a node bipartition such that the sum of edge weights joining the different partitions is …

We consider the weighted monotone and antimonotone satisfiability problems on
normalized circuits of depth at most t≥ 2, abbreviated Image 1 and Image 2, respectively …

The celebrated grid exclusion theorem states that for every h‐vertex planar graph H, there is
a constant such that if a graph G does not contain H as a minor then G has treewidth at most …

In this paper, we provide bounds for the genus of the pancake graph $\mathbb {P} _n $,
burnt pancake graph $\mathbb {BP} _n $, and undirected generalized pancake graph …

We provide an exposition of the main results of the theory of bidimensionality in
parameterized algorithm design. This theory applies to graph problems that are …

Table 1: The updated NP-Completeness Column: An Ongoing Guide table 35 years later.
Depicted in bold are the references that correspond to unresolved entries in [OG] and [GJ] …