Studying graph - stability to apprehend relative hardness of constructive-non-constructive approximation
The complexity of constructing gerechte designs.
The NP-completeness of automorphic colorings
Given a graph G, an automorphic edge(vertex)-coloring of G is a proper edge(vertex)-coloring such that each automorphism of the graph preserves the coloring. The automorphic chromatic index (number) is the least integer k for which G admits an automorphic edge(vertex)-coloring with k colors. We show that it is NP-complete to determine the automorphic chromatic index and the automorphic chromatic number of an arbitrary graph.
Three notes on the complexity of model checking fixpoint logic with chop
This paper analyses the complexity of model checking fixpoint logic with Chop – an extension of the modal μ-calculus with a sequential composition operator. It uses two known game-based characterisations to derive the following results: the combined model checking complexity as well as the data complexity of FLC are EXPTIME-complete. This is already the case for its alternation-free fragment. The expression complexity of FLC is trivially P-hard and limited from above by the complexity of solving...
Tractability of multivariate problems for weighted spaces of functions
We survey recent results on tractability of multivariate problems. We mainly restrict ourselves to linear multivariate problems studied in the worst case setting. Typical examples include multivariate integration and function approximation for weighted spaces of smooth functions.
Vertex-partitioning into fixed additive induced-hereditary properties is NP-hard.