13 citations · 77 across the 56 of their papers we have counts for
16 papers · 1 filter
On Computational Aspects of Cores of Ordered Graphs
Michal Čertík, Andreas Emil Feldmann, Jaroslav Nešetřil +1
An ordered graph is a graph enhanced with a linear order on the vertex set. An ordered graph is a core if it does not have an order-preserving homomorphism to a proper subgraph. We…
On Computational Aspects of Ordered Matching Problems
Michal Čertík, Andreas Emil Feldmann, Jaroslav Nešetřil +1
Ordered matchings, defined as graphs with linearly ordered vertices, where each vertex is connected to exactly one edge, play a crucial role in the area of ordered graphs and their…
Complexity Aspects of Homomorphisms of Ordered Graphs
Michal Čertík, Andreas Emil Feldmann, Jaroslav Nešetřil +1
We examine ordered graphs, defined as graphs with linearly ordered vertices, from the perspective of homomorphisms (and colorings) and their complexities. We demonstrate the corres…
Finding large -colorable induced subgraphs in (bull, chair)-free and (bull,E)-free graphs
Nadzieja Hodur, Monika Pilśniak, Magdalena Prorok +1
We study the Max Partial -Coloring problem, where we are given a vertex-weighted graph, and we ask for a maximum-weight induced subgraph that admits a proper -coloring. For $…
Fundamental Problems on Bounded-Treewidth Graphs: The Real Source of Hardness
Barış Can Esmer, Jacob Focke, Dániel Marx +1
It is known for many algorithmic problems that if a tree decomposition of width is given in the input, then the problem can be solved with exponential dependence on . A line…
List homomorphisms by deleting edges and vertices: tight complexity bounds for bounded-treewidth graphs
Barış Can Esmer, Jacob Focke, Dániel Marx +1
The goal of this paper is to investigate a family of optimization problems arising from list homomorphisms, and to understand what the best possible algorithms are if we restrict t…
Counting list homomorphisms from graphs of bounded treewidth: tight complexity bounds
Jacob Focke, Dániel Marx, Paweł Rzążewski
The goal of this work is to give precise bounds on the counting complexity of a family of generalized coloring problems (list homomorphisms) on bounded-treewidth graphs. Given grap…
Complexity of the list homomorphism problem in hereditary graph classes
Karolina Okrasa, Paweł Rzążewski
A homomorphism from a graph to a graph is an edge-preserving mapping from to . For a fixed graph , in the list homomorphism problem, denoted by LHom(), w…
Fine-grained complexity of the list homomorphism problem: feedback vertex set and cutwidth
Marta Piecyk, Paweł Rzążewski
For graphs , a homomorphism from to is an edge-preserving mapping from to . In the list homomorphism problem, denoted by \textsc{LHom}(), we are given…
Sparsification Lower Bounds for List -Coloring
Hubie Chen, Bart M. P. Jansen, Karolina Okrasa +2
We investigate the List -Coloring problem, the generalization of graph coloring that asks whether an input graph admits a homomorphism to the undirected graph (possibly…
Full complexity classification of the list homomorphism problem for bounded-treewidth graphs
Karolina Okrasa, Marta Piecyk, Paweł Rzążewski
A homomorphism from a graph to a graph is an edge-preserving mapping from to . Let be a fixed graph with possible loops. In the list homomorphism problem,…
Parameterized Inapproximability of Independent Set in -Free Graphs
Pavel Dvořák, Andreas Emil Feldmann, Ashutosh Rai +1
We study the Independent Set (IS) problem in -free graphs, i.e., graphs excluding some fixed graph as an induced subgraph. We prove several inapproximability results both fo…
Subexponential-time algorithms for finding large induced sparse subgraphs
Jana Novotná, Karolina Okrasa, Michał Pilipczuk +3
Let and be hereditary graph classes. Consider the following problem: given a graph , find a largest, in terms of the number of vertices…
Subexponential algorithms for variants of homomorphism problem in string graphs
Karolina Okrasa, Paweł Rzążewski
We consider the complexity of finding weighted homomorphisms from intersection graphs of curves (string graphs) with vertices to a fixed graph . We provide a complete dichot…
Tight Euler tours in uniform hypergraphs - computational aspects
Zbigniew Lonc, Paweł Naroski, Paweł Rzążewski
By a tight tour in a -uniform hypergraph we mean any sequence of its vertices such that for all the set $e_i=\{w_i,w_{i+1}\ldots,…
Complexity of Token Swapping and its Variants
Édouard Bonnet, Tillmann Miltzow, Paweł Rzążewski
In the Token Swapping problem we are given a graph with a token placed on each vertex. Each token has exactly one destination vertex, and we try to move all the tokens to their des…