Michael Lampis | DeepAI

AI Chat

Featured Co-authors

Édouard Bonnet
45 publications
Yusuke Kobayashi
36 publications
Yasuaki Kobayashi
32 publications
Yota Otachi
32 publications
Eun Jung Kim
29 publications
Tesshu Hanaka
28 publications
Stefan Mengel
20 publications
Hirotaka Ono
18 publications
Florian Sikora
15 publications
Bruno Escoffier
13 publications
Evripidis Bampis
11 publications

∙ 04/28/2023

Structural Parameterizations for Two Bounded Degree Problems Revisited

We revisit two well-studied problems, Bounded Degree Vertex Deletion and...

0 Michael Lampis, et al. ∙

∙ 02/19/2023

Parameterized Max Min Feedback Vertex Set

Given a graph G and an integer k, Max Min FVS asks whether there exists ...

0 Michael Lampis, et al. ∙

∙ 10/18/2022

First Order Logic on Pathwidth Revisited Again

Courcelle's celebrated theorem states that all MSO-expressible propertie...

0 Michael Lampis, et al. ∙

∙ 02/14/2022

Hedonic Games and Treewidth Revisited

We revisit the complexity of the well-studied notion of Additively Separ...

0 Tesshu Hanaka, et al. ∙

∙ 09/23/2021

Filling Crosswords is Very Hard

We revisit a classical crossword filling puzzle which already appeared i...

0 Laurent Gourvès, et al. ∙

∙ 09/21/2021

Fine-grained Meta-Theorems for Vertex Integrity

Vertex Integrity is a graph measure which sits squarely between two more...

0 Michael Lampis, et al. ∙

∙ 04/27/2021

Minimum Stable Cut and Treewidth

A stable cut of a graph is a cut whose weight cannot be increased by cha...

0 Michael Lampis, et al. ∙

∙ 03/30/2021

Determining a Slater Winner is Complete for Parallel Access to NP

We consider the complexity of deciding the winner of an election under t...

0 Michael Lampis, et al. ∙

∙ 01/19/2021

Upper Dominating Set: Tight Algorithms for Pathwidth and Sub-Exponential Approximation

An upper dominating set is a minimal dominating set in a graph. In the U...

0 Louis Dublois, et al. ∙

∙ 10/13/2020

Digraph Coloring and Distance to Acyclicity

In k-Digraph Coloring we are given a digraph and are asked to partition ...

0 Ararat Harutyunyan, et al. ∙

∙ 09/21/2020

(In)approximability of Maximum Minimal FVS

We study the approximability of the NP-complete Maximum Minimal Feedback...

0 Louis Dublois, et al. ∙

∙ 08/17/2020

Grundy Distinguishes Treewidth from Pathwidth

Structural graph parameters, such as treewidth, pathwidth, and clique-wi...

0 Rémy Belmonte, et al. ∙

∙ 08/08/2020

Parameterized Complexity of (A,ℓ)-Path Packing

Given a graph G = (V,E), A ⊆ V, and integers k and ℓ, the (A,ℓ)-Path Pac...

0 Rémy Belmonte, et al. ∙

∙ 11/20/2019

New Algorithms for Mixed Dominating Set

A mixed dominating set is a collection of vertices and edges that domina...

0 Louis Dublois, et al. ∙

∙ 10/12/2019

Improved (In-)Approximability Bounds for d-Scattered Set

In the d-Scattered Set problem we are asked to select at least k vertice...

0 Ioannis Katsikarelis, et al. ∙

∙ 05/01/2019

Independent Set Reconfiguration Parameterized by Modular-Width

Independent Set Reconfiguration is one of the most well-studied problems...

0 Rémy Belmonte, et al. ∙

∙ 02/13/2019

New Results on Directed Edge Dominating Set

We study a family of generalizations of Edge Dominating Set on directed ...

0 Rémy Belmonte, et al. ∙

∙ 01/27/2019

Parameterized Complexity of Safe Set

In this paper we study the problem of finding a small safe set S in a gr...

0 Rémy Belmonte, et al. ∙

∙ 10/25/2018

Maximum Independent Sets in Subcubic Graphs: New Results

The maximum independent set problem is known to be NP-hard in the class ...

0 Ararat Harutyunyan, et al. ∙

∙ 07/30/2018

Parameterized Orientable Deletion

A graph is d-orientable if its edges can be oriented so that the maximum...

0 Tesshu Hanaka, et al. ∙

∙ 07/14/2018

Token Sliding on Split Graphs

We show that the independent set reconfiguration problem on split graphs...

0 Rémy Belmonte, et al. ∙

∙ 05/22/2018

QBF as an Alternative to Courcelle's Theorem

We propose reductions to quantified Boolean formulas (QBF) as a new appr...

0 Michael Lampis, et al. ∙

∙ 04/23/2018

How Bad is the Freedom to Flood-It?

Fixed-Flood-It and Free-Flood-It are combinatorial problems on graphs th...

0 Rémy Belmonte, et al. ∙

∙ 04/21/2018

Finer Tight Bounds for Coloring on Clique-Width

We revisit the complexity of the classical k-Coloring problem parameteri...

0 Michael Lampis, et al. ∙

∙ 01/31/2018

Parameterized Power Vertex Cover

We study a recently introduced generalization of the Vertex Cover (VC) p...

0 Eric Angel, et al. ∙

∙ 01/11/2018

Parameterized (Approximate) Defective Coloring

In Defective Coloring we are given a graph G = (V, E) and two integers χ...

0 Rémy Belmonte, et al. ∙

∙ 10/02/2017

On the Parameterized Complexity of Red-Blue Points Separation

We study the following geometric separation problem: Given a set R of ...

0 Édouard Bonnet, et al. ∙

∙ 09/07/2017

Structurally Parameterized d-Scattered Set

In d-Scattered Set we are given an (edge-weighted) graph and are asked t...

0 Ioannis Katsikarelis, et al. ∙

Are you a researcher?
Expose your work
to one of the largest
A.I. communities in the world