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 …

For a set of graphs\({\mathcal {H}}\), a graph G is\({\mathcal {H}}\)-subgraph-free if G does
not contain any graph from\({{{\mathcal {H}}}}\) as a subgraph. We propose general and easy …

The Weisfeiler-Leman dimension of a graph $ G $ is the least number $ k $ such that the $ k
$-dimensional Weisfeiler-Leman algorithm distinguishes $ G $ from every other non …

Inspired by recent progress in dynamic programming approaches for weighted model
counting, we investigate a dynamic-programming approach in the context of boolean …

We present a simple, self-contained, linear reduction from 3-SAT to Treewidth. Specifically, it
shows that 1.00005-approximating Treewidth is NP-hard, and solving Treewidth exactly …

It is known that the weighted version of Edge Multiway Cut (also known as Multiterminal Cut)
is NP-complete on planar graphs of maximum degree 3. In contrast, for the unweighted …

Two graphs G and H are homomorphism indistinguishable over a class of graphs F if, for all
graphs F∈ F, the number of homomorphisms from F to G is equal to the number of …