121 citations · 373 across the 96 of their papers we have counts for
7 papers · 1 filter
Shortest Cycles With Monotone Submodular Costs
Fedor V. Fomin, Petr A. Golovach, Tuukka Korhonen +2
We introduce the following submodular generalization of the Shortest Cycle problem. For a nonnegative monotone submodular cost function defined on the edges (or the vertices) o…
A Framework for Approximation Schemes on Disk Graphs
Daniel Lokshtanov, Fahad Panolan, Saket Saurabh +2
We initiate a systematic study of approximation schemes for fundamental optimization problems on disk graphs, a common generalization of both planar graphs and unit-disk graphs. Ou…
An Improved Parameterized Algorithm for Treewidth
Tuukka Korhonen, Daniel Lokshtanov
We give an algorithm that takes as input an -vertex graph and an integer , runs in time , and outputs a tree decomposition of of width at most $k…
Fixed-parameter tractability of Graph Isomorphism in graphs with an excluded minor
Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk +1
We prove that Graph Isomorphism and Canonization in graphs excluding a fixed graph as a minor can be solved by an algorithm working in time , where is s…
Highly unbreakable graph with a fixed excluded minor are almost rigid
Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk +1
A set in a graph is -unbreakable if every separation of order at most in satisfies or . In this…
Point Separation and Obstacle Removal by Finding and Hitting Odd Cycles
Neeraj Kumar, Daniel Lokshtanov, Saket Saurabh +2
Suppose we are given a pair of points and a set of geometric objects in the plane, called obstacles. We show that in polynomial time one can construct an auxiliary (…
Wordle is NP-hard
Daniel Lokshtanov, Bernardo Subercaseaux
Wordle is a single-player word-guessing game where the goal is to discover a secret word that has been chosen from a dictionary . In order to discover , the player can ma…