Source author record

Michael Lampis

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Computational Complexity Data Structures and Algorithms math.CO Discrete Mathematics Logic in Computer Science Computer Science and Game Theory math.OC

Catalog footprint

Research overview

19works

7topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Digraph Coloring and Distance to Acyclicity

In $k$ -Digraph Coloring we are given a digraph and are asked to partition its vertices into at most $k$ sets, so that each set induces a DAG. This well-known problem is NP-hard, as it generalizes (undirected) $k$ -Coloring, but becomes trivial if the input digraph is acyclic. This poses the natural parameterized complexity question what happens when the input is "almost" acyclic. In this paper we study this question using parameters that measure the input's distance to acyclicity in either the directed or the undirected sense. It is already known that, for all $k\ge 2$ , $k$ -Digraph Coloring is NP-hard on digraphs of DFVS at most $k+4$ . We strengthen this result to show that, for all $k\ge 2$ , $k$ -Digraph Coloring is NP-hard for DFVS $k$ . Refining our reduction we obtain two further consequences: (i) for all $k\ge 2$ , $k$ -Digraph Coloring is NP-hard for graphs of feedback arc set (FAS) at most $k^2$ ; interestingly, this leads to a dichotomy, as we show that the problem is FPT by $k$ if FAS is at most $k^2-1$ ; (ii) $k$ -Digraph Coloring is NP-hard for graphs of DFVS $k$ , even if the maximum degree $Δ$ is at most $4k-1$ ; we show that this is also almost tight, as the problem becomes FPT for DFVS $k$ and $Δ\le 4k-3$ . We then consider parameters that measure the distance from acyclicity of the underlying graph. We show that $k$ -Digraph Coloring admits an FPT algorithm parameterized by treewidth, whose parameter dependence is $(tw!)k^{tw}$ . Then, we pose the question of whether the $tw!$ factor can be eliminated. Our main contribution in this part is to settle this question in the negative and show that our algorithm is essentially optimal, even for the much more restricted parameter treedepth and for $k=2$ . Specifically, we show that an FPT algorithm solving $2$ -Digraph Coloring with dependence $td^{o(td)}$ would contradict the ETH.

preprint2022arXiv

Grundy Distinguishes Treewidth from Pathwidth

Structural graph parameters, such as treewidth, pathwidth, and clique-width, are a central topic of study in parameterized complexity. A main aim of research in this area is to understand the "price of generality" of these widths: as we transition from more restrictive to more general notions, which are the problems that see their complexity status deteriorate from fixed-parameter tractable to intractable? This type of question is by now very well-studied, but, somewhat strikingly, the algorithmic frontier between the two (arguably) most central width notions, treewidth and pathwidth, is still not understood: currently, no natural graph problem is known to be W-hard for one but FPT for the other. Indeed, a surprising development of the last few years has been the observation that for many of the most paradigmatic problems, their complexities for the two parameters actually coincide exactly, despite the fact that treewidth is a much more general parameter. It would thus appear that the extra generality of treewidth over pathwidth often comes "for free". Our main contribution in this paper is to uncover the first natural example where this generality comes with a high price. We consider Grundy Coloring, a variation of coloring where one seeks to calculate the worst possible coloring that could be assigned to a graph by a greedy First-Fit algorithm. We show that this well-studied problem is FPT parameterized by pathwidth; however, it becomes significantly harder (W[1]-hard) when parameterized by treewidth. Furthermore, we show that Grundy Coloring makes a second complexity jump for more general widths, as it becomes para-NP-hard for clique-width. Hence, Grundy Coloring nicely captures the complexity trade-offs between the three most well-studied parameters. Completing the picture, we show that Grundy Coloring is FPT parameterized by modular-width.

preprint2022arXiv

Hedonic Games and Treewidth Revisited

We revisit the complexity of the well-studied notion of Additively Separable Hedonic Games (ASHGs). Such games model a basic clustering or coalition formation scenario in which selfish agents are represented by the vertices of an edge-weighted digraph $G=(V,E)$ , and the weight of an arc $uv$ denotes the utility $u$ gains by being in the same coalition as $v$ . We focus on (arguably) the most basic stability question about such a game: given a graph, does a Nash stable solution exist and can we find it efficiently? We study the (parameterized) complexity of ASHG stability when the underlying graph has treewidth $t$ and maximum degree $Δ$ . The current best FPT algorithm for this case was claimed by Peters [AAAI 2016], with time complexity roughly $2^{O(Δ^5t)}$ . We present an algorithm with parameter dependence $(Δt)^{O(Δt)}$ , significantly improving upon the parameter dependence on $Δ$ given by Peters, albeit with a slightly worse dependence on $t$ . Our main result is that this slight performance deterioration with respect to $t$ is actually completely justified: we observe that the previously claimed algorithm is incorrect, and that in fact no algorithm can achieve dependence $t^{o(t)}$ for bounded-degree graphs, unless the ETH fails. This, together with corresponding bounds we provide on the dependence on $Δ$ and the joint parameter establishes that our algorithm is essentially optimal for both parameters, under the ETH. We then revisit the parameterization by treewidth alone and resolve a question also posed by Peters by showing that Nash Stability remains strongly NP-hard on stars under additive preferences. Nevertheless, we also discover an island of mild tractability: we show that Connected Nash Stability is solvable in pseudo-polynomial time for constant $t$ , though with an XP dependence on $t$ which, as we establish, cannot be avoided.

preprint2021arXiv

(In)approximability of Maximum Minimal FVS

We study the approximability of the NP-complete \textsc{Maximum Minimal Feedback Vertex Set} problem. Informally, this natural problem seems to lie in an intermediate space between two more well-studied problems of this type: \textsc{Maximum Minimal Vertex Cover}, for which the best achievable approximation ratio is $\sqrt{n}$ , and \textsc{Upper Dominating Set}, which does not admit any $n^{1-ε}$ approximation. We confirm and quantify this intuition by showing the first non-trivial polynomial time approximation for \textsc{Max Min FVS} with a ratio of $O(n^{2/3})$ , as well as a matching hardness of approximation bound of $n^{2/3-ε}$ , improving the previous known hardness of $n^{1/2-ε}$ . The approximation algorithm also gives a cubic kernel when parameterized by the solution size. Along the way, we also obtain an $O(Δ)$ -approximation and show that this is asymptotically best possible, and we improve the bound for which the problem is NP-hard from $Δ\ge 9$ to $Δ\ge 6$ . Having settled the problem's approximability in polynomial time, we move to the context of super-polynomial time. We devise a generalization of our approximation algorithm which, for any desired approximation ratio $r$ , produces an $r$ -approximate solution in time $n^{O(n/r^{3/2})}$ . This time-approximation trade-off is essentially tight: we show that under the ETH, for any ratio $r$ and $ε>0$ , no algorithm can $r$ -approximate this problem in time $n^{O((n/r^{3/2})^{1-ε})}$ , hence we precisely characterize the approximability of the problem for the whole spectrum between polynomial and sub-exponential time, up to an arbitrarily small constant in the second exponent.

preprint2021arXiv

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 \textsc{Upper Dominating Set} problem, the goal is to find an upper dominating set of maximum size. We study the complexity of parameterized algorithms for \textsc{Upper Dominating Set}, as well as its sub-exponential approximation. First, we prove that, under ETH, \textsc{ $k$ -Upper Dominating Set} cannot be solved in time $O(n^{o(k)})$ (improving on $O(n^{o(\sqrt{k})})$ ), and in the same time we show under the same complexity assumption that for any constant ratio $r$ and any $\varepsilon > 0$ , there is no $r$ -approximation algorithm running in time $O(n^{k^{1-\varepsilon}})$ . Then, we settle the problem's complexity parameterized by pathwidth by giving an algorithm running in time $O^*(6^{pw})$ (improving the current best $O^*(7^{pw})$ ), 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 $\varepsilon > 0$ , no algorithm can output an $r$ -approximation in time $n^{(n/r)^{1-\varepsilon}}$ . Hence, we completely characterize the approximability of the problem in sub-exponential time.

preprint2020arXiv

Parameterized Complexity of $(A,\ell)$ -Path Packing

Given a graph $G = (V,E)$ , $A \subseteq V$ , and integers $k$ and $\ell$ , the \textsc{ $(A,\ell)$ -Path Packing} problem asks to find $k$ vertex-disjoint paths of length $\ell$ that have endpoints in $A$ and internal points in $V \setminus A$ . We study the parameterized complexity of this problem with parameters $|A|$ , $\ell$ , $k$ , treewidth, pathwidth, and their combinations. We present sharp complexity contrasts with respect to these parameters. Among other results, we show that the problem is polynomial-time solvable when $\ell \le 3$ , while it is NP-complete for constant $\ell \ge 4$ . We also show that the problem is W[1]-hard parameterized by pathwidth ${}+|A|$ , while it is fixed-parameter tractable parameterized by treewidth ${}+\ell$ .

preprint2020arXiv

Parameterized Orientable Deletion

A graph is $d$ -orientable if its edges can be oriented so that the maximum in-degree of the resulting digraph is at most $d$ . $d$ -orientability is a well-studied concept with close connections to fundamental graph-theoretic notions and applications as a load balancing problem. In this paper we consider the d-ORIENTABLE DELETION problem: given a graph $G=(V,E)$ , delete the minimum number of vertices to make $G$ $d$ -orientable. We contribute a number of results that improve the state of the art on this problem. Specifically: - We show that the problem is W[2]-hard and $\log n$ -inapproximable with respect to $k$ , the number of deleted vertices. This closes the gap in the problem's approximability. - We completely characterize the parameterized complexity of the problem on chordal graphs: it is FPT parameterized by $d+k$ , but W-hard for each of the parameters $d,k$ separately. - We show that, under the SETH, for all $d,ε$ , the problem does not admit a $(d+2-ε)^{tw}$ , algorithm where $tw$ is the graph's treewidth, resolving as a special case an open problem on the complexity of PSEUDOFOREST DELETION. - We show that the problem is W-hard parameterized by the input graph's clique-width. Complementing this, we provide an algorithm running in time $d^{O(d\cdot cw)}$ , showing that the problem is FPT by $d+cw$ , and improving the previously best known algorithm for this case.

preprint2015arXiv

Algorithmic Aspects of Upper Domination

In this paper we study combinatorial and algorithmic resp. complexity questions of upper domination, i.e., the maximum cardinality of a minimal dominating set in a graph. We give a full classification of the related maximisation and minimisation problems, as well as the related parameterised problems, on general graphs and on graphs of bounded degree, and we also study planar graphs.

preprint2015arXiv

Sub-exponential Approximation Schemes for CSPs: from Dense to Almost Sparse

It has long been known, since the classical work of (Arora, Karger, Karpinski, JCSS~99), that \MC\ admits a PTAS on dense graphs, and more generally, \kCSP\ admits a PTAS on "dense" instances with $Ω(n^k)$ constraints. In this paper we extend and generalize their exhaustive sampling approach, presenting a framework for $(1-\eps)$-approximating any \kCSP\ problem in \emph{sub-exponential} time while significantly relaxing the denseness requirement on the input instance. Specifically, we prove that for any constants $δ\in (0, 1]$ and $\eps > 0$, we can approximate \kCSP\ problems with $Ω(n^{k-1+δ})$ constraints within a factor of $(1-\eps)$ in time $2^{O(n^{1-δ}\ln n /\eps^3)}$. The framework is quite general and includes classical optimization problems, such as \MC, {\sc Max}-DICUT, \kSAT, and (with a slight extension) $k$ -{\sc Densest Subgraph}, as special cases. For \MC\ in particular (where $k=2$ ), it gives an approximation scheme that runs in time sub-exponential in $n$ even for "almost-sparse" instances (graphs with $n^{1+δ}$ edges). We prove that our results are essentially best possible, assuming the ETH. First, the density requirement cannot be relaxed further: there exists a constant $r < 1$ such that for all $δ> 0$ , \kSAT\ instances with $O(n^{k-1})$ clauses cannot be approximated within a ratio better than $r$ in time $2^{O(n^{1-δ})}$ . Second, the running time of our algorithm is almost tight \emph{for all densities}. Even for \MC\ there exists $r<1$ such that for all $δ' > δ>0$ , \MC\ instances with $n^{1+δ}$ edges cannot be approximated within a ratio better than $r$ in time $2^{n^{1-δ'}}$ .

preprint2015arXiv

Time-Approximation Trade-offs for Inapproximable Problems

In this paper we focus on problems which do not admit a constant-factor approximation in polynomial time and explore how quickly their approximability improves as the allowed running time is gradually increased from polynomial to (sub-)exponential. We tackle a number of problems: For Min Independent Dominating Set, Max Induced Path, Forest and Tree, for any $r(n)$ , a simple, known scheme gives an approximation ratio of $r$ in time roughly $r^{n/r}$ . We show that, for most values of $r$ , if this running time could be significantly improved the ETH would fail. For Max Minimal Vertex Cover we give a non-trivial $\sqrt{r}$ -approximation in time $2^{n/r}$ . We match this with a similarly tight result. We also give a $\log r$ -approximation for Min ATSP in time $2^{n/r}$ and an $r$ -approximation for Max Grundy Coloring in time $r^{n/r}$ . Furthermore, we show that Min Set Cover exhibits a curious behavior in this super-polynomial setting: for any $δ> 0$ it admits an $m^δ$ -approximation, where $m$ is the number of sets, in just quasi-polynomial time. We observe that if such ratios could be achieved in polynomial time, the ETH or the Projection Games Conjecture would fail.

preprint2014arXiv

Model Checking Lower Bounds for Simple Graphs

A well-known result by Frick and Grohe shows that deciding FO logic on trees involves a parameter dependence that is a tower of exponentials. Though this lower bound is tight for Courcelle's theorem, it has been evaded by a series of recent meta-theorems for other graph classes. Here we provide some additional non-elementary lower bound results, which are in some senses stronger. Our goal is to explain common traits in these recent meta-theorems and identify barriers to further progress. More specifically, first, we show that on the class of threshold graphs, and therefore also on any union and complement-closed class, there is no model-checking algorithm with elementary parameter dependence even for FO logic. Second, we show that there is no model-checking algorithm with elementary parameter dependence for MSO logic even restricted to paths (or equivalently to unary strings), unless E=NE. As a corollary, we resolve an open problem on the complexity of MSO model-checking on graphs of bounded max-leaf number. Finally, we look at MSO on the class of colored trees of depth d. We show that, assuming the ETH, for every fixed d>=1 at least d+1 levels of exponentiation are necessary for this problem, thus showing that the (d+1)-fold exponential algorithm recently given by Gajarsky and Hlinĕny is essentially optimal.

preprint2014arXiv

Parameterized Approximation Schemes using Graph Widths

Combining the techniques of approximation algorithms and parameterized complexity has long been considered a promising research area, but relatively few results are currently known. In this paper we study the parameterized approximability of a number of problems which are known to be hard to solve exactly when parameterized by treewidth or clique-width. Our main contribution is to present a natural randomized rounding technique that extends well-known ideas and can be used for both of these widths. Applying this very generic technique we obtain approximation schemes for a number of problems, evading both polynomial-time inapproximability and parameterized intractability bounds.

preprint2014arXiv

Parameterized Edge Hamiltonicity

We study the parameterized complexity of the classical Edge Hamiltonian Path problem and give several fixed-parameter tractability results. First, we settle an open question of Demaine et al. by showing that Edge Hamiltonian Path is FPT parameterized by vertex cover, and that it also admits a cubic kernel. We then show fixed-parameter tractability even for a generalization of the problem to arbitrary hypergraphs, parameterized by the size of a (supplied) hitting set. We also consider the problem parameterized by treewidth or clique-width. Surprisingly, we show that the problem is FPT for both of these standard parameters, in contrast to its vertex version, which is W-hard for clique-width. Our technique, which may be of independent interest, relies on a structural characterization of clique-width in terms of treewidth and complete bipartite subgraphs due to Gurski and Wanke.

preprint2013arXiv

Closing a Gap in the Complexity of Refinement Modal Logic

Refinement Modal Logic (RML), which was recently introduced by Bozzelli et al., is an extension of classical modal logic which allows one to reason about a changing model. In this paper we study computational complexity questions related to this logic, settling a number of open problems. Specifically, we study the complexity of satisfiability for the existential fragment of RML, a problem posed by Bozzelli, van Ditmarsch and Pinchinat. Our main result is a tight PSPACE upper bound for this problem, which we achieve by introducing a new tableau system. As a direct consequence, we obtain a tight characterization of the complexity of RML satisfiability for any fixed number of alternations of refinement quantifiers. Additionally, through a simple reduction we establish that the model checking problem for RML is PSPACE-complete, even for formulas with a single quantifier.

preprint2013arXiv

New Inapproximability Bounds for TSP

In this paper, we study the approximability of the metric Traveling Salesman Problem (TSP) and prove new explicit inapproximability bounds for that problem. The best up to now known hardness of approximation bounds were 185/184 for the symmetric case (due to Lampis) and 117/116 for the asymmetric case (due to Papadimitriou and Vempala). We construct here two new bounded occurrence CSP reductions which improve these bounds to 123/122 and 75/74, respectively. The latter bound is the first improvement in more than a decade for the case of the asymmetric TSP. One of our main tools, which may be of independent interest, is a new construction of a bounded degree wheel amplifier used in the proof of our results.

preprint2013arXiv

Parameterized Algorithms for Modular-Width

It is known that a number of natural graph problems which are FPT parameterized by treewidth become W-hard when parameterized by clique-width. It is therefore desirable to find a different structural graph parameter which is as general as possible, covers dense graphs but does not incur such a heavy algorithmic penalty. The main contribution of this paper is to consider a parameter called modular-width, defined using the well-known notion of modular decompositions. Using a combination of ILPs and dynamic programming we manage to design FPT algorithms for Coloring and Partitioning into paths (and hence Hamiltonian path and Hamiltonian cycle), which are W-hard for both clique-width and its recently introduced restriction, shrub-depth. We thus argue that modular-width occupies a sweet spot as a graph parameter, generalizing several simpler notions on dense graphs but still evading the "price of generality" paid by clique-width.

preprint2013arXiv

The Computational Complexity of the Game of Set and its Theoretical Applications

The game of SET is a popular card game in which the objective is to form Sets using cards from a special deck. In this paper we study single- and multi-round variations of this game from the computational complexity point of view and establish interesting connections with other classical computational problems. Specifically, we first show that a natural generalization of the problem of finding a single Set, parameterized by the size of the sought Set is W-hard; our reduction applies also to a natural parameterization of Perfect Multi-Dimensional Matching, a result which may be of independent interest. Second, we observe that a version of the game where one seeks to find the largest possible number of disjoint Sets from a given set of cards is a special case of 3-Set Packing; we establish that this restriction remains NP-complete. Similarly, the version where one seeks to find the smallest number of disjoint Sets that overlap all possible Sets is shown to be NP-complete, through a close connection to the Independent Edge Dominating Set problem. Finally, we study a 2-player version of the game, for which we show a close connection to Arc Kayles, as well as fixed-parameter tractability when parameterized by the number of rounds played.

preprint2012arXiv

Local Improvement Gives Better Expanders

It has long been known that random regular graphs are with high probability good expanders. This was first established in the 1980s by Bollobás by directly calculating the probability that a set of vertices has small expansion and then applying the union bound. In this paper we improve on this analysis by relying on a simple high-level observation: if a graph contains a set of vertices with small expansion then it must also contain such a set of vertices that is locally optimal, that is, a set whose expansion cannot be made smaller by exchanging a vertex from the set with one from the set's complement. We show that the probability that a set of vertices satisfies this additional property is significantly smaller. Thus, after again applying the union bound, we obtain improved lower bounds on the expansion of random $Δ$ -regular graphs for $Δ\ge 4$ . In fact, the gains from this analysis increase as $Δ$ grows, a fact we explain by extending our technique to general $Δ$ . Thus, in the end we obtain an improvement not only for some small special cases but on the general asymptotic bound on the expansion of $Δ$ -regular graphs given by Bollobás.

preprint2012arXiv

Scrabble is PSPACE-Complete

In this paper we study the computational complexity of the game of Scrabble. We prove the PSPACE-completeness of a derandomized model of the game, answering an open question of Erik Demaine and Robert Hearn.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Michael Lampis

Research overview

Is this your work?

19 publications

Digraph Coloring and Distance to Acyclicity

Grundy Distinguishes Treewidth from Pathwidth

Hedonic Games and Treewidth Revisited

(In)approximability of Maximum Minimal FVS

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

Parameterized Complexity of $(A,\ell)$ -Path Packing

Parameterized Orientable Deletion

Algorithmic Aspects of Upper Domination

Sub-exponential Approximation Schemes for CSPs: from Dense to Almost Sparse

Time-Approximation Trade-offs for Inapproximable Problems

Model Checking Lower Bounds for Simple Graphs

Parameterized Approximation Schemes using Graph Widths

Parameterized Edge Hamiltonicity

Closing a Gap in the Complexity of Refinement Modal Logic

New Inapproximability Bounds for TSP

Parameterized Algorithms for Modular-Width

The Computational Complexity of the Game of Set and its Theoretical Applications

Local Improvement Gives Better Expanders

Scrabble is PSPACE-Complete

See the researcher in context

Building this map preview

Michael Lampis

Research overview

Is this your work?

19 publications

Digraph Coloring and Distance to Acyclicity

Grundy Distinguishes Treewidth from Pathwidth

Hedonic Games and Treewidth Revisited

(In)approximability of Maximum Minimal FVS

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

Parameterized Complexity of (A,ℓ)(A,\ell)(A,ℓ)-Path Packing

Parameterized Orientable Deletion

Algorithmic Aspects of Upper Domination

Sub-exponential Approximation Schemes for CSPs: from Dense to Almost Sparse

Time-Approximation Trade-offs for Inapproximable Problems

Model Checking Lower Bounds for Simple Graphs

Parameterized Approximation Schemes using Graph Widths

Parameterized Edge Hamiltonicity

Closing a Gap in the Complexity of Refinement Modal Logic

New Inapproximability Bounds for TSP

Parameterized Algorithms for Modular-Width

The Computational Complexity of the Game of Set and its Theoretical Applications

Local Improvement Gives Better Expanders

Scrabble is PSPACE-Complete

See the researcher in context

Building this map preview

Parameterized Complexity of $(A,\ell)$ -Path Packing