2 citations · 2 across the 2 of their papers we have counts for
5 papers · 1 filter
Tight Lower Bounds for List Edge Coloring
Łukasz Kowalik, Arkadiusz Socała
The fastest algorithms for edge coloring run in time , where and are the number of edges and vertices of the input graph, respectively. For dense graphs, this…
On Directed Feedback Vertex Set parameterized by treewidth
Marthe Bonamy, Łukasz Kowalik, Jesper Nederlof +3
We study the Directed Feedback Vertex Set problem parameterized by the treewidth of the input graph. We prove that unless the Exponential Time Hypothesis fails, the problem cannot…
On the fine-grained complexity of rainbow coloring
Łukasz Kowalik, Juho Lauri, Arkadiusz Socała
The Rainbow k-Coloring problem asks whether the edges of a given graph can be colored in colors so that every pair of vertices is connected by a rainbow path, i.e., a path with…
Tight Lower Bounds on Graph Embedding Problems
Marek Cygan, Fedor V. Fomin, Alexander Golovnev +4
We prove that unless the Exponential Time Hypothesis (ETH) fails, deciding if there is a homomorphism from graph to graph cannot be done in time . We al…
The Hardness of Subgraph Isomorphism
Marek Cygan, Jakub Pachocki, Arkadiusz Socała
Subgraph Isomorphism is a very basic graph problem, where given two graphs and one is to check whether is a subgraph of . Despite its simple definition, the Subgraph…