Michael Lampis

MFCS Conference 2025 Conference Paper

Broadcasting Under Structural Restrictions

• Yudai Egami
• Tatsuya Gima
• Tesshu Hanaka
• Yasuaki Kobayashi
• Michael Lampis
• Valia Mitsou
• Edouard Nemery
• Yota Otachi

In the Telephone Broadcast problem we are given a graph G = (V, E) with a designated source vertex s ∈ V. Our goal is to transmit a message, which is initially known only to s, to all vertices of the graph by using a process where in each round an informed vertex may transmit the message to one of its uninformed neighbors. The optimization objective is to minimize the number of rounds. Following up on several recent works, we investigate the structurally parameterized complexity of Telephone Broadcast. In particular, we first strengthen existing NP-hardness results by showing that the problem remains NP-complete on graphs of bounded tree-depth and also on cactus graphs which are one vertex deletion away from being path forests. Motivated by this (severe) hardness, we study several other parameterizations of the problem and obtain FPT algorithms parameterized by vertex integrity (generalizing a recent FPT algorithm parameterized by vertex cover by Fomin, Fraigniaud, and Golovach [TCS 2024]) and by distance to clique, as well as FPT approximation algorithms parameterized by clique-cover and cluster vertex deletion. Furthermore, we obtain structural results that relate the length of the optimal broadcast protocol of a graph G with its pathwidth and tree-depth. By presenting a substantial improvement over the best previously known bound for pathwidth (Aminian, Kamali, Seyed-Javadi, and Sumedha [ICALP 2025]) we exponentially improve the approximation ratio achievable in polynomial time on graphs of bounded pathwidth from 𝒪(4^pw) to 𝒪(pw).

MFCS Conference 2025 Conference Paper

Parameterized Spanning Tree Congestion

• Michael Lampis
• Valia Mitsou
• Edouard Nemery
• Yota Otachi
• Manolis Vasilakis
• Daniel Vaz 0001

In this paper we study the Spanning Tree Congestion problem, where we are given an undirected graph G = (V, E) and are asked to find a spanning tree T of minimum maximum congestion. Here, the congestion of an edge e ∈ T is the number of edges uv ∈ E such that the (unique) path from u to v in T traverses e. We consider this well-studied NP-hard problem from the point of view of (structural) parameterized complexity and obtain the following results: - We resolve a natural open problem by showing that Spanning Tree Congestion is not FPT parameterized by treewidth (under standard assumptions). More strongly, we present a generic reduction which applies to (almost) any parameter of the form "vertex-deletion distance to class 𝒞", thus obtaining W[1]-hardness for more restricted parameters, including tree-depth plus feedback vertex set, or incomparable to treewidth, such as twin cover. Via a slight tweak of the same reduction we also show that the problem is NP-complete on graphs of modular-width 4. - Even though it is known that Spanning Tree Congestion remains NP-hard on instances with only one vertex of unbounded degree, it is currently open whether the problem remains hard on bounded-degree graphs. We resolve this question by showing NP-hardness on graphs of maximum degree 8. - Complementing the problem’s W[1]-hardness for treewidth, we formulate an algorithm that runs in time roughly {(k+w)}^{𝒪(w)}, where k is the desired congestion and w the treewidth, improving a previous argument for parameter k+w that was based on Courcelle’s theorem. This explicit algorithm pays off in two ways: it allows us to obtain an FPT approximation scheme for parameter treewidth, that is, a (1+ε)-approximation running in time roughly {(w/ε)}^{𝒪(w)}; and it leads to an exact FPT algorithm for parameter clique-width+k via a Win/Win argument. - Finally, motivated by the problem’s hardness for most standard structural parameters, we present FPT algorithms for several more restricted cases, namely, for the parameters vertex-deletion distance to clique; vertex integrity; and feedback edge set, in the latter case also achieving a single-exponential running time dependence on the parameter.

AAMAS Conference 2025 Conference Paper

Satisfactory Budget Division

• Laurent Gourvès
• Michael Lampis
• Nikolaos Melissinos
• Aris Pagourtzis

A divisible budget must be allocated to several projects, and agents are asked for their opinion on how much they would give to each project. We consider that an agent is satisfied by a division of the budget if, for at least a certain predefined number τ of projects, the part of the budget actually allocated to each project is at least as large as the amount the agent requested. The objective is to find a budget division that “best satisfies” the agents. In this context, different problems can be stated and we address the following ones. We study (i) the largest proportion of agents that can be satisfied for any instance, (ii) classes of instances admitting a budget division that satisfies all agents, (iii) the complexity of deciding if, for a given instance, every agent can be satisfied, and finally (iv) the question of finding, for a given instance, the smallest total budget to satisfy all agents. We provide answers to these complementary questions for several natural values of the parameter τ, capturing scenarios where we seek to satisfy for each agent all; almost all; half; or at least one of her requests.

SODA Conference 2025 Conference Paper

The Primal Pathwidth SETH

• Michael Lampis

TCS Journal 2024 Journal Article

Filling crosswords is very hard

• Laurent Gourvès
• Ararat Harutyunyan
• Michael Lampis
• Nikolaos Melissinos

We revisit a classical crossword filling puzzle which already appeared in Garey& Jonhson's book. We are given a grid with n vertical and horizontal slots and a dictionary with m words. We are asked to place words from the dictionary in the slots so that shared cells are consistent. We attempt to pinpoint the source of intractability of this problem by carefully taking into account the structure of the grid graph, which contains a vertex for each slot and an edge if two slots intersect. Our main approach is to consider the case where this graph has a tree-like structure. Unfortunately, if we impose the common rule that words cannot be reused, we discover that the problem remains NP-hard under very severe structural restrictions, namely, if the grid graph is a union of stars and the alphabet has size 2, or the grid graph is a matching (so the crossword is a collection of disjoint crosses) and the alphabet has size 3. The problem does become slightly more tractable if word reuse is allowed, as we obtain an m tw algorithm in this case, where tw is the treewidth of the grid graph. However, even in this case, we show that our algorithm cannot be improved to obtain fixed-parameter tractability. More strongly, we show that under the ETH the problem cannot be solved in time m o ( k ), where k is the number of horizontal slots of the instance (which trivially bounds tw). Motivated by these mostly negative results, we also consider the much more restricted case where the problem is parameterized by the number of slots n. Here, we show that the problem does become FPT (if the alphabet has constant size), but the parameter dependence is exponential in n 2. We show that this dependence is also justified: the existence of an algorithm with running time 2 o ( n 2 ), even for binary alphabet, would contradict the randomized ETH. After that, we consider an optimization version of the problem, where we seek to place as many words on the grid as possible. Here it is easy to obtain a 1 2 -approximation, even on weighted instances, simply by considering only horizontal or only vertical slots. We show that this trivial algorithm is also likely to be optimal, as obtaining a better approximation ratio in polynomial time would contradict the Unique Games Conjecture. The latter two results apply whether word reuse is allowed or not. Finally, we present some special cases where the problem is decidable in polynomial time. In particular, we present three reductions, one to 2-SAT, the second to Maximum Matching and the third to Exact Matching.

MFCS Conference 2024 Conference Paper

Parameterized Vertex Integrity Revisited

• Tesshu Hanaka
• Michael Lampis
• Manolis Vasilakis
• Kanae Yoshiwatari

Vertex integrity is a graph parameter that measures the connectivity of a graph. Informally, its meaning is that a graph has small vertex integrity if it has a small separator whose removal disconnects the graph into connected components which are themselves also small. Graphs with low vertex integrity are very structured; this renders many hard problems tractable and has recently attracted interest in this notion from the parameterized complexity community. In this paper we revisit the NP-complete problem of computing the vertex integrity of a given graph from the point of view of structural parameterizations. We present a number of new results, which also answer some recently posed open questions from the literature. Specifically, we show that unweighted vertex integrity is W[1]-hard parameterized by treedepth; we show that the problem remains W[1]-hard if we parameterize by feedback edge set size (via a reduction from a Bin Packing variant which may be of independent interest); and complementing this we show that the problem is FPT by max-leaf number. Furthermore, for weighted vertex integrity, we show that the problem admits a single-exponential FPT algorithm parameterized by vertex cover or by modular width, the latter result improving upon a previous algorithm which required weights to be polynomially bounded.

MFCS Conference 2023 Conference Paper

Parameterized Max Min Feedback Vertex Set

• Michael Lampis
• Nikolaos Melissinos
• Manolis Vasilakis

Given a graph G and an integer k, Max Min FVS asks whether there exists a minimal set of vertices of size at least k whose deletion destroys all cycles. We present several results that improve upon the state of the art of the parameterized complexity of this problem with respect to both structural and natural parameters. Using standard DP techniques, we first present an algorithm of time tw^O(tw) n^O(1), significantly generalizing a recent algorithm of Gaikwad et al. of time vc^O(vc) n^O(1), where tw, vc denote the input graph’s treewidth and vertex cover respectively. Subsequently, we show that both of these algorithms are essentially optimal, since a vc^o(vc) n^O(1) algorithm would refute the ETH. With respect to the natural parameter k, the aforementioned recent work by Gaikwad et al. claimed an FPT branching algorithm with complexity 10^k n^O(1). We point out that this algorithm is incorrect and present a branching algorithm of complexity 9. 34^k n^O(1).

TCS Journal 2022 Journal Article

Upper Dominating Set: Tight algorithms for pathwidth and sub-exponential approximation

• Louis Dublois
• Michael Lampis
• Vangelis Th. Paschos

In the Upper Dominating Set problem, the goal is to find a minimal dominating set of maximum size. We study the complexity of parameterized algorithms for Upper Dominating Set, as well as its sub-exponential approximation. First, we prove that, under the ETH, Upper Dominating Set cannot be solved in time O ( n o ( k ) ) (improving on O ( n o ( k ) ) ), and in the same time we show under the same complexity assumption that for any constant ratio r and any ε > 0, there is no r-approximation algorithm running in time O ( n k 1 − ε ). Then, we settle the problem's complexity parameterized by pathwidth by giving an algorithm running in time O ⁎ ( 6 p w ) (improving the current best O ⁎ ( 7 p w ) ), and a lower bound showing that our algorithm is the best we can get under the SETH. Furthermore, we obtain a simple sub-exponential approximation algorithm for this problem: an algorithm that produces an r-approximation in time n O ( n / r ), for any desired approximation ratio r < n. We finally show that this time-approximation trade-off is tight, up to an arbitrarily small constant in the second exponent: under the randomized ETH, and for any ratio r > 1 and ε > 0, no algorithm can output an r-approximation in time n ( n / r ) 1 − ε. Hence, we completely characterize the approximability of the problem in sub-exponential time.

MFCS Conference 2018 Conference Paper

New Results on Directed Edge Dominating Set

• Rémy Belmonte
• Tesshu Hanaka
• Ioannis Katsikarelis
• Eun Jung Kim 0002
• Michael Lampis

We study a family of generalizations of Edge Dominating Set on directed graphs called Directed (p, q)-Edge Dominating Set. In this problem an arc (u, v) is said to dominate itself, as well as all arcs which are at distance at most q from v, or at distance at most p to u. First, we give significantly improved FPT algorithms for the two most important cases of the problem, (0, 1)-dEDS and (1, 1)-dEDS (that correspond to versions of Dominating Set on line graphs), as well as polynomial kernels. We also improve the best-known approximation for these cases from logarithmic to constant. In addition, we show that (p, q)-dEDS is FPT parameterized by p+q+tw, but W-hard parameterized just by tw, where tw is the treewidth of the underlying graph of the input. We then go on to focus on the complexity of the problem on tournaments. Here, we provide a complete classification for every possible fixed value of p, q, which shows that the problem exhibits a surprising behavior, including cases which are in P; cases which are solvable in quasi-polynomial time but not in P; and a single case (p=q=1) which is NP-hard (under randomized reductions) and cannot be solved in sub-exponential time, under standard assumptions.

SAT Conference 2018 Conference Paper

QBF as an Alternative to Courcelle's Theorem

• Michael Lampis
• Stefan Mengel
• Valia Mitsou

Abstract We propose reductions to quantified Boolean formulas (QBF) as a new approach to showing fixed-parameter linear algorithms for problems parameterized by treewidth. We demonstrate the feasibility of this approach by giving new algorithms for several well-known problems from artificial intelligence that are in general complete for the second level of the polynomial hierarchy. By reduction from QBF we show that all resulting algorithms are essentially optimal in their dependence on the treewidth. Most of the problems that we consider were already known to be fixed-parameter linear by using Courcelle’s Theorem or dynamic programming, but we argue that our approach has clear advantages over these techniques: on the one hand, in contrast to Courcelle’s Theorem, we get concrete and tight guarantees for the runtime dependence on the treewidth. On the other hand, we avoid tedious dynamic programming and, after showing some normalization results for CNF-formulas, our upper bounds often boil down to a few lines.

TCS Journal 2018 Journal Article

The many facets of upper domination

• Cristina Bazgan
• Ljiljana Brankovic
• Katrin Casel
• Henning Fernau
• Klaus Jansen
• Kim-Manuel Klein
• Michael Lampis
• Mathieu Liedloff

This paper studies Upper Domination, i. e. , the problem of computing the maximum cardinality of a minimal dominating set in a graph with respect to classical and parameterised complexity as well as approximability.

TCS Journal 2013 Journal Article

Parameterized maximum path coloring

• Michael Lampis

We study the well-known Max Path Coloring problem from a parameterized point of view, focusing on trees and low-treewidth networks. We observe the existence of a variety of reasonable parameters for the problem, such as the maximum degree and treewidth of the network graph, the number of available colors and the number of requests one seeks to satisfy or reject. In an effort to understand the impact of each of these parameters on the problem’s complexity we study various parameterized versions of the problem deriving fixed-parameter tractability and hardness results both for undirected and bi-directed graphs.

TCS Journal 2012 Journal Article

Ordered coloring of grids and related graphs

• Amotz Bar-Noy
• Panagiotis Cheilaris
• Michael Lampis
• Valia Mitsou
• Stathis Zachos

We investigate a coloring problem, called ordered coloring, in grids and some other families of grid-like graphs. Ordered coloring (also known as vertex ranking) has applications, among other areas, in efficient solving of sparse linear systems of equations and scheduling parallel assembly of products. Our main technical results improve upper and lower bounds for the ordered chromatic number of grids and related graphs.