Search Results

Documents authored by Lampis, Michael

Document
DOI: 10.4230/LIPIcs.MFCS.2024.58
Parameterized Vertex Integrity Revisited

Authors: Tesshu Hanaka, Michael Lampis, Manolis Vasilakis, and Kanae Yoshiwatari

Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)

Abstract
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.
Cite as

Tesshu Hanaka, Michael Lampis, Manolis Vasilakis, and Kanae Yoshiwatari. Parameterized Vertex Integrity Revisited. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 58:1-58:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{hanaka_et_al:LIPIcs.MFCS.2024.58,
  author =	{Hanaka, Tesshu and Lampis, Michael and Vasilakis, Manolis and Yoshiwatari, Kanae},
  title =	{{Parameterized Vertex Integrity Revisited}},
  booktitle =	{49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)},
  pages =	{58:1--58:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-335-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{306},
  editor =	{Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.58},
  URN =		{urn:nbn:de:0030-drops-206141},
  doi =		{10.4230/LIPIcs.MFCS.2024.58},
  annote =	{Keywords: Parameterized Complexity, Treedepth, Vertex Integrity}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.61
Parameterized Algorithms for Steiner Forest in Bounded Width Graphs

Authors: Andreas Emil Feldmann and Michael Lampis

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
In this paper we reassess the parameterized complexity and approximability of the well-studied Steiner Forest problem in several graph classes of bounded width. The problem takes an edge-weighted graph and pairs of vertices as input, and the aim is to find a minimum cost subgraph in which each given vertex pair lies in the same connected component. It is known that this problem is APX-hard in general, and NP-hard on graphs of treewidth 3, treedepth 4, and feedback vertex set size 2. However, Bateni, Hajiaghayi and Marx [JACM, 2011] gave an approximation scheme with a runtime of n^O(k²/ε) on graphs of treewidth k. Our main result is a much faster efficient parameterized approximation scheme (EPAS) with a runtime of 2^O(k²/ε log k/ε)⋅n^O(1). If k instead is the vertex cover number of the input graph, we show how to compute the optimum solution in 2^O(k log k)⋅n^O(1) time, and we also prove that this runtime dependence on k is asymptotically best possible, under ETH. Furthermore, if k is the size of a feedback edge set, then we obtain a faster 2^O(k)⋅n^O(1) time algorithm, which again cannot be improved under ETH.
Cite as

Andreas Emil Feldmann and Michael Lampis. Parameterized Algorithms for Steiner Forest in Bounded Width Graphs. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 61:1-61:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{feldmann_et_al:LIPIcs.ICALP.2024.61,
  author =	{Feldmann, Andreas Emil and Lampis, Michael},
  title =	{{Parameterized Algorithms for Steiner Forest in Bounded Width Graphs}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{61:1--61:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.61},
  URN =		{urn:nbn:de:0030-drops-202048},
  doi =		{10.4230/LIPIcs.ICALP.2024.61},
  annote =	{Keywords: Steiner Forest, Approximation Algorithms, FPT algorithms}
}
Document
DOI: 10.4230/LIPIcs.ESA.2023.77
Structural Parameterizations for Two Bounded Degree Problems Revisited

Authors: Michael Lampis and Manolis Vasilakis

Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)

Abstract
We revisit two well-studied problems, Bounded Degree Vertex Deletion and Defective Coloring, where the input is a graph G and a target degree Δ and we are asked either to edit or partition the graph so that the maximum degree becomes bounded by Δ. Both problems are known to be parameterized intractable for the most well-known structural parameters, such as treewidth. We revisit the parameterization by treewidth, as well as several related parameters and present a more fine-grained picture of the complexity of both problems. In particular: - Both problems admit straightforward DP algorithms with table sizes (Δ+2)^tw and (χ_d(Δ+1))^{tw} respectively, where tw is the input graph’s treewidth and χ_d the number of available colors. We show that, under the SETH, both algorithms are essentially optimal, for any non-trivial fixed values of Δ, χ_d, even if we replace treewidth by pathwidth. Along the way, we obtain an algorithm for Defective Coloring with complexity quasi-linear in the table size, thus settling the complexity of both problems for treewidth and pathwidth. - Given that the standard DP algorithm is optimal for treewidth and pathwidth, we then go on to consider the more restricted parameter tree-depth. Here, previously known lower bounds imply that, under the ETH, Bounded Vertex Degree Deletion and Defective Coloring cannot be solved in time n^o(∜{td}) and n^o(√{td}) respectively, leaving some hope that a qualitatively faster algorithm than the one for treewidth may be possible. We close this gap by showing that neither problem can be solved in time n^o(td), under the ETH, by employing a recursive low tree-depth construction that may be of independent interest. - Finally, we consider a structural parameter that is known to be restrictive enough to render both problems FPT: vertex cover. For both problems the best known algorithm in this setting has a super-exponential dependence of the form vc^𝒪(vc). We show that this is optimal, as an algorithm with dependence of the form vc^o(vc) would violate the ETH. Our proof relies on a new application of the technique of d-detecting families introduced by Bonamy et al. [ToCT 2019]. Our results, although mostly negative in nature, paint a clear picture regarding the complexity of both problems in the landscape of parameterized complexity, since in all cases we provide essentially matching upper and lower bounds.
Cite as

Michael Lampis and Manolis Vasilakis. Structural Parameterizations for Two Bounded Degree Problems Revisited. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 77:1-77:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{lampis_et_al:LIPIcs.ESA.2023.77,
  author =	{Lampis, Michael and Vasilakis, Manolis},
  title =	{{Structural Parameterizations for Two Bounded Degree Problems Revisited}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{77:1--77:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.77},
  URN =		{urn:nbn:de:0030-drops-187302},
  doi =		{10.4230/LIPIcs.ESA.2023.77},
  annote =	{Keywords: ETH, Parameterized Complexity, SETH}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2023.62
Parameterized Max Min Feedback Vertex Set

Authors: Michael Lampis, Nikolaos Melissinos, and Manolis Vasilakis

Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)

Abstract
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).
Cite as

Michael Lampis, Nikolaos Melissinos, and Manolis Vasilakis. Parameterized Max Min Feedback Vertex Set. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 62:1-62:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{lampis_et_al:LIPIcs.MFCS.2023.62,
  author =	{Lampis, Michael and Melissinos, Nikolaos and Vasilakis, Manolis},
  title =	{{Parameterized Max Min Feedback Vertex Set}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{62:1--62:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.62},
  URN =		{urn:nbn:de:0030-drops-185965},
  doi =		{10.4230/LIPIcs.MFCS.2023.62},
  annote =	{Keywords: ETH, Feedback vertex set, Parameterized algorithms, Treewidth}
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2023.132
First Order Logic on Pathwidth Revisited Again

Authors: Michael Lampis

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

Abstract
Courcelle’s celebrated theorem states that all MSO-expressible properties can be decided in linear time on graphs of bounded treewidth. Unfortunately, the hidden constant implied by this theorem is a tower of exponentials whose height increases with each quantifier alternation in the formula. More devastatingly, this cannot be improved, under standard assumptions, even if we consider the much more restricted problem of deciding FO-expressible properties on trees. In this paper we revisit this well-studied topic and identify a natural special case where the dependence of Courcelle’s theorem can, in fact, be improved. Specifically, we show that all FO-expressible properties can be decided with an elementary dependence on the input formula, if the input graph has bounded pathwidth (rather than treewidth). This is a rare example of treewidth and pathwidth having different complexity behaviors. Our result is also in sharp contrast with MSO logic on graphs of bounded pathwidth, where it is known that the dependence has to be non-elementary, under standard assumptions. Our work builds upon, and generalizes, a corresponding meta-theorem by Gajarský and Hliněný for the more restricted class of graphs of bounded tree-depth.
Cite as

Michael Lampis. First Order Logic on Pathwidth Revisited Again. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 132:1-132:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{lampis:LIPIcs.ICALP.2023.132,
  author =	{Lampis, Michael},
  title =	{{First Order Logic on Pathwidth Revisited Again}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{132:1--132:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.132},
  URN =		{urn:nbn:de:0030-drops-181848},
  doi =		{10.4230/LIPIcs.ICALP.2023.132},
  annote =	{Keywords: Algorithmic Meta-Theorems, FO logic, Pathwidth}
}
Document
DOI: 10.4230/LIPIcs.ESA.2022.64
Hedonic Games and Treewidth Revisited

Authors: Tesshu Hanaka and Michael Lampis

Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)

Abstract
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(Δ⁵t)}. 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.
Cite as

Tesshu Hanaka and Michael Lampis. Hedonic Games and Treewidth Revisited. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 64:1-64:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{hanaka_et_al:LIPIcs.ESA.2022.64,
  author =	{Hanaka, Tesshu and Lampis, Michael},
  title =	{{Hedonic Games and Treewidth Revisited}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{64:1--64:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.64},
  URN =		{urn:nbn:de:0030-drops-170025},
  doi =		{10.4230/LIPIcs.ESA.2022.64},
  annote =	{Keywords: Hedonic Games, Nash Equilibrium, Treewidth}
}
Document
DOI: 10.4230/LIPIcs.STACS.2022.45
Determining a Slater Winner Is Complete for Parallel Access to NP

Authors: Michael Lampis

Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)

Abstract
We consider the complexity of deciding the winner of an election under the Slater rule. In this setting we are given a tournament T = (V,A), where the vertices of V represent candidates and the direction of each arc indicates which of the two endpoints is preferable for the majority of voters. The Slater score of a vertex v ∈ V is defined as the minimum number of arcs that need to be reversed so that T becomes acyclic and v becomes the winner. We say that v is a Slater winner in T if v has minimum Slater score in T. Deciding if a vertex is a Slater winner in a tournament has long been known to be NP-hard. However, the best known complexity upper bound for this problem is the class Θ₂^p, which corresponds to polynomial-time Turing machines with parallel access to an NP oracle. In this paper we close this gap by showing that the problem is Θ₂^p-complete, and that this hardness applies to instances constructible by aggregating the preferences of 7 voters.
Cite as

Michael Lampis. Determining a Slater Winner Is Complete for Parallel Access to NP. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 45:1-45:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{lampis:LIPIcs.STACS.2022.45,
  author =	{Lampis, Michael},
  title =	{{Determining a Slater Winner Is Complete for Parallel Access to NP}},
  booktitle =	{39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)},
  pages =	{45:1--45:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-222-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{219},
  editor =	{Berenbrink, Petra and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.45},
  URN =		{urn:nbn:de:0030-drops-158555},
  doi =		{10.4230/LIPIcs.STACS.2022.45},
  annote =	{Keywords: Slater winner, Feedback Arc Set, Tournaments}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2021.34
Fine-Grained Meta-Theorems for Vertex Integrity

Authors: Michael Lampis and Valia Mitsou

Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)

Abstract
Vertex Integrity is a graph measure which sits squarely between two more well-studied notions, namely vertex cover and tree-depth, and that has recently gained attention as a structural graph parameter. In this paper we investigate the algorithmic trade-offs involved with this parameter from the point of view of algorithmic meta-theorems for First-Order (FO) and Monadic Second Order (MSO) logic. Our positive results are the following: (i) given a graph G of vertex integrity k and an FO formula ϕ with q quantifiers, deciding if G satisfies ϕ can be done in time 2^O(k²q + q log q) + n^O(1); (ii) for MSO formulas with q quantifiers, the same can be done in time 2^{2^O(k²+kq)} + n^O(1). Both results are obtained using kernelization arguments, which pre-process the input to sizes 2^O(k²)q and 2^O(k²+kq) respectively. The complexities of our meta-theorems are significantly better than the corresponding meta-theorems for tree-depth, which involve towers of exponentials. However, they are worse than the roughly 2^{O(kq)} and 2^{2^{O(k+q)}} complexities known for corresponding meta-theorems for vertex cover. To explain this deterioration we present two formula constructions which lead to fine-grained complexity lower bounds and establish that the dependence of our meta-theorems on k is best possible. More precisely, we show that it is not possible to decide FO formulas with q quantifiers in time 2^o(k²q), and that there exists a constant-size MSO formula which cannot be decided in time 2^{2^o(k²)}, both under the ETH. Hence, the quadratic blow-up in the dependence on k is unavoidable and vertex integrity has a complexity for FO and MSO logic which is truly intermediate between vertex cover and tree-depth.
Cite as

Michael Lampis and Valia Mitsou. Fine-Grained Meta-Theorems for Vertex Integrity. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 34:1-34:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{lampis_et_al:LIPIcs.ISAAC.2021.34,
  author =	{Lampis, Michael and Mitsou, Valia},
  title =	{{Fine-Grained Meta-Theorems for Vertex Integrity}},
  booktitle =	{32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
  pages =	{34:1--34:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-214-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{212},
  editor =	{Ahn, Hee-Kap and Sadakane, Kunihiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.34},
  URN =		{urn:nbn:de:0030-drops-154674},
  doi =		{10.4230/LIPIcs.ISAAC.2021.34},
  annote =	{Keywords: Model-Checking, Fine-grained complexity, Vertex Integrity}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2021.36
Filling Crosswords Is Very Hard

Authors: Laurent Gourvès, Ararat Harutyunyan, Michael Lampis, and Nikolaos Melissinos

Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)

Abstract
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 and 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². We show that this dependence is also justified: the existence of an algorithm with running time 2^o(n²), even for binary alphabet, would contradict the randomized ETH. Finally, 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.
Cite as

Laurent Gourvès, Ararat Harutyunyan, Michael Lampis, and Nikolaos Melissinos. Filling Crosswords Is Very Hard. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 36:1-36:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{gourves_et_al:LIPIcs.ISAAC.2021.36,
  author =	{Gourv\`{e}s, Laurent and Harutyunyan, Ararat and Lampis, Michael and Melissinos, Nikolaos},
  title =	{{Filling Crosswords Is Very Hard}},
  booktitle =	{32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
  pages =	{36:1--36:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-214-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{212},
  editor =	{Ahn, Hee-Kap and Sadakane, Kunihiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.36},
  URN =		{urn:nbn:de:0030-drops-154690},
  doi =		{10.4230/LIPIcs.ISAAC.2021.36},
  annote =	{Keywords: Crossword Puzzle, Treewidth, ETH}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2021.92
Minimum Stable Cut and Treewidth

Authors: Michael Lampis

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

Abstract
A stable or locally-optimal cut of a graph is a cut whose weight cannot be increased by changing the side of a single vertex. Equivalently, a cut is stable if all vertices have the (weighted) majority of their neighbors on the other side. Finding a stable cut is a prototypical PLS-complete problem that has been studied in the context of local search and of algorithmic game theory. In this paper we study Min Stable Cut, the problem of finding a stable cut of minimum weight, which is closely related to the Price of Anarchy of the Max Cut game. Since this problem is NP-hard, we study its complexity on graphs of low treewidth, low degree, or both. We begin by showing that the problem remains weakly NP-hard on severely restricted trees, so bounding treewidth alone cannot make it tractable. We match this hardness with a pseudo-polynomial DP algorithm solving the problem in time (Δ⋅ W)^{O(tw)}n^{O(1)}, where tw is the treewidth, Δ the maximum degree, and W the maximum weight. On the other hand, bounding Δ is also not enough, as the problem is NP-hard for unweighted graphs of bounded degree. We therefore parameterize Min Stable Cut by both tw and Δ and obtain an FPT algorithm running in time 2^{O(Δtw)}(n+log W)^{O(1)}. Our main result for the weighted problem is to provide a reduction showing that both aforementioned algorithms are essentially optimal, even if we replace treewidth by pathwidth: if there exists an algorithm running in (nW)^{o(pw)} or 2^{o(Δpw)}(n+log W)^{O(1)}, then the ETH is false. Complementing this, we show that we can, however, obtain an FPT approximation scheme parameterized by treewidth, if we consider almost-stable solutions, that is, solutions where no single vertex can unilaterally increase the weight of its incident cut edges by more than a factor of (1+ε). Motivated by these mostly negative results, we consider Unweighted Min Stable Cut. Here our results already imply a much faster exact algorithm running in time Δ^{O(tw)}n^{O(1)}. We show that this is also probably essentially optimal: an algorithm running in n^{o(pw)} would contradict the ETH.
Cite as

Michael Lampis. Minimum Stable Cut and Treewidth. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 92:1-92:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{lampis:LIPIcs.ICALP.2021.92,
  author =	{Lampis, Michael},
  title =	{{Minimum Stable Cut and Treewidth}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{92:1--92:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.92},
  URN =		{urn:nbn:de:0030-drops-141616},
  doi =		{10.4230/LIPIcs.ICALP.2021.92},
  annote =	{Keywords: Treewidth, Local Max-Cut, Nash Stability}
}
Document
DOI: 10.4230/LIPIcs.STACS.2021.41
Digraph Coloring and Distance to Acyclicity

Authors: Ararat Harutyunyan, Michael Lampis, and Nikolaos Melissinos

Published in: LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)

Abstract
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 of 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. In the directed sense perhaps the most natural notion of distance to acyclicity is directed feedback vertex set (DFVS). It is already known that, for all k ≥ 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 ≥ 2, k-Digraph Coloring is already NP-hard for DFVS exactly k. This immediately provides a dichotomy, as k-Digraph Coloring is trivial if DFVS is at most k-1. Refining our reduction we obtain two further consequences: (i) for all k ≥ 2, k-Digraph Coloring is NP-hard for graphs of feedback arc set (FAS) at most k²; interestingly, this leads to a second dichotomy, as we show that the problem is FPT by k if FAS is at most k²-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 Δ ≤ 4k-3. Since these results imply that the problem is also NP-hard on graphs of bounded directed treewidth, we then consider parameters that measure the distance from acyclicity of the underlying graph. On the positive side, we show that k-Digraph Coloring admits an FPT algorithm parameterized by treewidth, whose parameter dependence is (tw!)k^{tw}. Since this is considerably worse than the k^{tw} dependence of (undirected) k-Coloring, 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.
Cite as

Ararat Harutyunyan, Michael Lampis, and Nikolaos Melissinos. Digraph Coloring and Distance to Acyclicity. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 41:1-41:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{harutyunyan_et_al:LIPIcs.STACS.2021.41,
  author =	{Harutyunyan, Ararat and Lampis, Michael and Melissinos, Nikolaos},
  title =	{{Digraph Coloring and Distance to Acyclicity}},
  booktitle =	{38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)},
  pages =	{41:1--41:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-180-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{187},
  editor =	{Bl\"{a}ser, Markus and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021.41},
  URN =		{urn:nbn:de:0030-drops-136865},
  doi =		{10.4230/LIPIcs.STACS.2021.41},
  annote =	{Keywords: Digraph Coloring, Dichromatic number, NP-completeness, Parameterized complexity, Feedback vertex and arc sets}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2020.9
New Algorithms for Mixed Dominating Set

Authors: Louis Dublois, Michael Lampis, and Vangelis Th. Paschos

Published in: LIPIcs, Volume 180, 15th International Symposium on Parameterized and Exact Computation (IPEC 2020)

Abstract
A mixed dominating set is a set of vertices and edges that dominates all vertices and edges of a graph. We study the complexity of exact and parameterized algorithms for MDS, resolving some open questions. In particular, we settle the problem’s complexity parameterized by treewidth and pathwidth by giving an algorithm running in time O^*(5^{tw}) (improving the current best O^*(6^{tw})), and a lower bound showing that our algorithm cannot be improved under the SETH, even if parameterized by pathwidth (improving a lower bound of O^*((2-ε)^{pw})). Furthermore, by using a simple but so far overlooked observation on the structure of minimal solutions, we obtain branching algorithms which improve the best known FPT algorithm for this problem, from O^*(4.172^k) to O^*(3.510^k), and the best known exact algorithm, from O^*(2ⁿ) and exponential space, to O^*(1.912ⁿ) and polynomial space.
Cite as

Louis Dublois, Michael Lampis, and Vangelis Th. Paschos. New Algorithms for Mixed Dominating Set. In 15th International Symposium on Parameterized and Exact Computation (IPEC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 180, pp. 9:1-9:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{dublois_et_al:LIPIcs.IPEC.2020.9,
  author =	{Dublois, Louis and Lampis, Michael and Paschos, Vangelis Th.},
  title =	{{New Algorithms for Mixed Dominating Set}},
  booktitle =	{15th International Symposium on Parameterized and Exact Computation (IPEC 2020)},
  pages =	{9:1--9:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-172-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{180},
  editor =	{Cao, Yixin and Pilipczuk, Marcin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2020.9},
  URN =		{urn:nbn:de:0030-drops-133127},
  doi =		{10.4230/LIPIcs.IPEC.2020.9},
  annote =	{Keywords: FPT Algorithms, Exact Algorithms, Mixed Domination}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2020.3
(In)approximability of Maximum Minimal FVS

Authors: Louis Dublois, Tesshu Hanaka, Mehdi Khosravian Ghadikolaei, Michael Lampis, and Nikolaos Melissinos

Published in: LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)

Abstract
We study the approximability of the NP-complete 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: Maximum Minimal Vertex Cover, for which the best achievable approximation ratio is √n, and 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 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-ε}. 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 Δ ≥ 9 to Δ ≥ 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.
Cite as

Louis Dublois, Tesshu Hanaka, Mehdi Khosravian Ghadikolaei, Michael Lampis, and Nikolaos Melissinos. (In)approximability of Maximum Minimal FVS. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 3:1-3:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{dublois_et_al:LIPIcs.ISAAC.2020.3,
  author =	{Dublois, Louis and Hanaka, Tesshu and Khosravian Ghadikolaei, Mehdi and Lampis, Michael and Melissinos, Nikolaos},
  title =	{{(In)approximability of Maximum Minimal FVS}},
  booktitle =	{31st International Symposium on Algorithms and Computation (ISAAC 2020)},
  pages =	{3:1--3:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-173-3},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{181},
  editor =	{Cao, Yixin and Cheng, Siu-Wing and Li, Minming},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.3},
  URN =		{urn:nbn:de:0030-drops-133477},
  doi =		{10.4230/LIPIcs.ISAAC.2020.3},
  annote =	{Keywords: Approximation Algorithms, ETH, Inapproximability}
}
Document
DOI: 10.4230/LIPIcs.ESA.2020.14
Grundy Distinguishes Treewidth from Pathwidth

Authors: Rémy Belmonte, Eun Jung Kim, Michael Lampis, Valia Mitsou, and Yota Otachi

Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)

Abstract
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.
Cite as

Rémy Belmonte, Eun Jung Kim, Michael Lampis, Valia Mitsou, and Yota Otachi. Grundy Distinguishes Treewidth from Pathwidth. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 14:1-14:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{belmonte_et_al:LIPIcs.ESA.2020.14,
  author =	{Belmonte, R\'{e}my and Kim, Eun Jung and Lampis, Michael and Mitsou, Valia and Otachi, Yota},
  title =	{{Grundy Distinguishes Treewidth from Pathwidth}},
  booktitle =	{28th Annual European Symposium on Algorithms (ESA 2020)},
  pages =	{14:1--14:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-162-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{173},
  editor =	{Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.14},
  URN =		{urn:nbn:de:0030-drops-128803},
  doi =		{10.4230/LIPIcs.ESA.2020.14},
  annote =	{Keywords: Treewidth, Pathwidth, Clique-width, Grundy Coloring}
}
Document
DOI: 10.4230/LIPIcs.STACS.2019.13
Token Sliding on Split Graphs

Authors: Rémy Belmonte, Eun Jung Kim, Michael Lampis, Valia Mitsou, Yota Otachi, and Florian Sikora

Published in: LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)

Abstract
We consider the complexity of the Independent Set Reconfiguration problem under the Token Sliding rule. In this problem we are given two independent sets of a graph and are asked if we can transform one to the other by repeatedly exchanging a vertex that is currently in the set with one of its neighbors, while maintaining the set independent. Our main result is to show that this problem is PSPACE-complete on split graphs (and hence also on chordal graphs), thus resolving an open problem in this area. We then go on to consider the c-Colorable Reconfiguration problem under the same rule, where the constraint is now to maintain the set c-colorable at all times. As one may expect, a simple modification of our reduction shows that this more general problem is PSPACE-complete for all fixed c >= 1 on chordal graphs. Somewhat surprisingly, we show that the same cannot be said for split graphs: we give a polynomial time (n^{O(c)}) algorithm for all fixed values of c, except c=1, for which the problem is PSPACE-complete. We complement our algorithm with a lower bound showing that c-Colorable Reconfiguration is W[2]-hard on split graphs parameterized by c and the length of the solution, as well as a tight ETH-based lower bound for both parameters.
Cite as

Rémy Belmonte, Eun Jung Kim, Michael Lampis, Valia Mitsou, Yota Otachi, and Florian Sikora. Token Sliding on Split Graphs. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 13:1-13:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{belmonte_et_al:LIPIcs.STACS.2019.13,
  author =	{Belmonte, R\'{e}my and Kim, Eun Jung and Lampis, Michael and Mitsou, Valia and Otachi, Yota and Sikora, Florian},
  title =	{{Token Sliding on Split Graphs}},
  booktitle =	{36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)},
  pages =	{13:1--13:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-100-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{126},
  editor =	{Niedermeier, Rolf and Paul, Christophe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.13},
  URN =		{urn:nbn:de:0030-drops-102529},
  doi =		{10.4230/LIPIcs.STACS.2019.13},
  annote =	{Keywords: reconfiguration, independent set, split graph}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2018.67
New Results on Directed Edge Dominating Set

Authors: Rémy Belmonte, Tesshu Hanaka, Ioannis Katsikarelis, Eun Jung Kim, and Michael Lampis

Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

Abstract
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.
Cite as

Rémy Belmonte, Tesshu Hanaka, Ioannis Katsikarelis, Eun Jung Kim, and Michael Lampis. New Results on Directed Edge Dominating Set. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 67:1-67:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{belmonte_et_al:LIPIcs.MFCS.2018.67,
  author =	{Belmonte, R\'{e}my and Hanaka, Tesshu and Katsikarelis, Ioannis and Kim, Eun Jung and Lampis, Michael},
  title =	{{New Results on Directed Edge Dominating Set}},
  booktitle =	{43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
  pages =	{67:1--67:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Potapov, Igor and Spirakis, Paul and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.67},
  URN =		{urn:nbn:de:0030-drops-96490},
  doi =		{10.4230/LIPIcs.MFCS.2018.67},
  annote =	{Keywords: Edge Dominating Set, Tournaments, Treewidth}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2018.86
Finer Tight Bounds for Coloring on Clique-Width

Authors: Michael Lampis

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract
We revisit the complexity of the classical k-Coloring problem parameterized by clique-width. This is a very well-studied problem that becomes highly intractable when the number of colors k is large. However, much less is known on its complexity for small, concrete values of k. In this paper, we completely determine the complexity of k-Coloring parameterized by clique-width for any fixed k, under the SETH. Specifically, we show that for all k >= 3,epsilon>0, k-Coloring cannot be solved in time O^*((2^k-2-epsilon)^{cw}), and give an algorithm running in time O^*((2^k-2)^{cw}). Thus, if the SETH is true, 2^k-2 is the "correct" base of the exponent for every k. Along the way, we also consider the complexity of k-Coloring parameterized by the related parameter modular treewidth (mtw). In this case we show that the "correct" running time, under the SETH, is O^*({k choose floor[k/2]}^{mtw}). If we base our results on a weaker assumption (the ETH), they imply that k-Coloring cannot be solved in time n^{o(cw)}, even on instances with O(log n) colors.
Cite as

Michael Lampis. Finer Tight Bounds for Coloring on Clique-Width. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 86:1-86:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{lampis:LIPIcs.ICALP.2018.86,
  author =	{Lampis, Michael},
  title =	{{Finer Tight Bounds for Coloring on Clique-Width}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{86:1--86:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.86},
  URN =		{urn:nbn:de:0030-drops-90903},
  doi =		{10.4230/LIPIcs.ICALP.2018.86},
  annote =	{Keywords: Clique-width, SETH, Coloring}
}
Document
DOI: 10.4230/LIPIcs.FUN.2018.5
How Bad is the Freedom to Flood-It?

Authors: Rémy Belmonte, Mehdi Khosravian Ghadikolaei, Masashi Kiyomi, Michael Lampis, and Yota Otachi

Published in: LIPIcs, Volume 100, 9th International Conference on Fun with Algorithms (FUN 2018)

Abstract
Fixed-Flood-It and Free-Flood-It are combinatorial problems on graphs that generalize a very popular puzzle called Flood-It. Both problems consist of recoloring moves whose goal is to produce a monochromatic ("flooded") graph as quickly as possible. Their difference is that in Free-Flood-It the player has the additional freedom of choosing the vertex to play in each move. In this paper, we investigate how this freedom affects the complexity of the problem. It turns out that the freedom is bad in some sense. We show that some cases trivially solvable for Fixed-Flood-It become intractable for Free-Flood-It. We also show that some tractable cases for Fixed-Flood-It are still tractable for Free-Flood-It but need considerably more involved arguments. We finally present some combinatorial properties connecting or separating the two problems. In particular, we show that the length of an optimal solution for Fixed-Flood-It is always at most twice that of Free-Flood-It, and this is tight.
Cite as

Rémy Belmonte, Mehdi Khosravian Ghadikolaei, Masashi Kiyomi, Michael Lampis, and Yota Otachi. How Bad is the Freedom to Flood-It?. In 9th International Conference on Fun with Algorithms (FUN 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 100, pp. 5:1-5:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{belmonte_et_al:LIPIcs.FUN.2018.5,
  author =	{Belmonte, R\'{e}my and Khosravian Ghadikolaei, Mehdi and Kiyomi, Masashi and Lampis, Michael and Otachi, Yota},
  title =	{{How Bad is the Freedom to Flood-It?}},
  booktitle =	{9th International Conference on Fun with Algorithms (FUN 2018)},
  pages =	{5:1--5:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-067-5},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{100},
  editor =	{Ito, Hiro and Leonardi, Stefano and Pagli, Linda and Prencipe, Giuseppe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2018.5},
  URN =		{urn:nbn:de:0030-drops-87961},
  doi =		{10.4230/LIPIcs.FUN.2018.5},
  annote =	{Keywords: flood-filling game, parameterized complexity}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2018.7
Multistage Matchings

Authors: Evripidis Bampis, Bruno Escoffier, Michael Lampis, and Vangelis Th. Paschos

Published in: LIPIcs, Volume 101, 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)

Abstract
We consider a multistage version of the Perfect Matching problem which models the scenario where the costs of edges change over time and we seek to obtain a solution that achieves low total cost, while minimizing the number of changes from one instance to the next. Formally, we are given a sequence of edge-weighted graphs on the same set of vertices V, and are asked to produce a perfect matching in each instance so that the total edge cost plus the transition cost (the cost of exchanging edges), is minimized. This model was introduced by Gupta et al. (ICALP 2014), who posed as an open problem its approximability for bipartite instances. We completely resolve this question by showing that Minimum Multistage Perfect Matching (Min-MPM) does not admit an n^{1-epsilon}-approximation, even on bipartite instances with only two time steps. Motivated by this negative result, we go on to consider two variations of the problem. In Metric Minimum Multistage Perfect Matching problem (Metric-Min-MPM) we are promised that edge weights in each time step satisfy the triangle inequality. We show that this problem admits a 3-approximation when the number of time steps is 2 or 3. On the other hand, we show that even the metric case is APX-hard already for 2 time steps. We then consider the complementary maximization version of the problem, Maximum Multistage Perfect Matching problem (Max-MPM), where we seek to maximize the total profit of all selected edges plus the total number of non-exchanged edges. We show that Max-MPM is also APX-hard, but admits a constant factor approximation algorithm for any number of time steps.
Cite as

Evripidis Bampis, Bruno Escoffier, Michael Lampis, and Vangelis Th. Paschos. Multistage Matchings. In 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 101, pp. 7:1-7:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{bampis_et_al:LIPIcs.SWAT.2018.7,
  author =	{Bampis, Evripidis and Escoffier, Bruno and Lampis, Michael and Paschos, Vangelis Th.},
  title =	{{Multistage Matchings}},
  booktitle =	{16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)},
  pages =	{7:1--7:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-068-2},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{101},
  editor =	{Eppstein, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2018.7},
  URN =		{urn:nbn:de:0030-drops-88338},
  doi =		{10.4230/LIPIcs.SWAT.2018.7},
  annote =	{Keywords: Perfect Matching, Temporal Optimization, Multistage Optimization}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2018.24
Parameterized Orientable Deletion

Authors: Tesshu Hanaka, Ioannis Katsikarelis, Michael Lampis, Yota Otachi, and Florian Sikora

Published in: LIPIcs, Volume 101, 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)

Abstract
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,epsilon, the problem does not admit a (d+2-epsilon)^{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 * cw)}, showing that the problem is FPT by d+cw, and improving the previously best know algorithm for this case.
Cite as

Tesshu Hanaka, Ioannis Katsikarelis, Michael Lampis, Yota Otachi, and Florian Sikora. Parameterized Orientable Deletion. In 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 101, pp. 24:1-24:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{hanaka_et_al:LIPIcs.SWAT.2018.24,
  author =	{Hanaka, Tesshu and Katsikarelis, Ioannis and Lampis, Michael and Otachi, Yota and Sikora, Florian},
  title =	{{Parameterized Orientable Deletion}},
  booktitle =	{16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)},
  pages =	{24:1--24:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-068-2},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{101},
  editor =	{Eppstein, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2018.24},
  URN =		{urn:nbn:de:0030-drops-88506},
  doi =		{10.4230/LIPIcs.SWAT.2018.24},
  annote =	{Keywords: Graph orientations, FPT algorithms, Treewidth, SETH}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2017.8
On the Parameterized Complexity of Red-Blue Points Separation

Authors: Édouard Bonnet, Panos Giannopoulos, and Michael Lampis

Published in: LIPIcs, Volume 89, 12th International Symposium on Parameterized and Exact Computation (IPEC 2017)

Abstract
We study the following geometric separation problem: Given a set R of red points and a set B of blue points in the plane, find a minimum-size set of lines that separate R from B. We show that, in its full generality, parameterized by the number of lines k in the solution, the problem is unlikely to be solvable significantly faster than the brute-force n^{O(k)}-time algorithm, where n is the total number of points. Indeed, we show that an algorithm running in time f(k)n^{o(k/log k)}, for any computable function f, would disprove ETH. Our reduction crucially relies on selecting lines from a set with a large number of different slopes (i.e., this number is not a function of k). Conjecturing that the problem variant where the lines are required to be axis-parallel is FPT in the number of lines, we show the following preliminary result. Separating R from B with a minimum-size set of axis-parallel lines is FPT in the size of either set, and can be solved in time O^*(9^{|B|}) (assuming that B is the smallest set).
Cite as

Édouard Bonnet, Panos Giannopoulos, and Michael Lampis. On the Parameterized Complexity of Red-Blue Points Separation. In 12th International Symposium on Parameterized and Exact Computation (IPEC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 89, pp. 8:1-8:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{bonnet_et_al:LIPIcs.IPEC.2017.8,
  author =	{Bonnet, \'{E}douard and Giannopoulos, Panos and Lampis, Michael},
  title =	{{On the Parameterized Complexity of Red-Blue Points Separation}},
  booktitle =	{12th International Symposium on Parameterized and Exact Computation (IPEC 2017)},
  pages =	{8:1--8:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-051-4},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{89},
  editor =	{Lokshtanov, Daniel and Nishimura, Naomi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2017.8},
  URN =		{urn:nbn:de:0030-drops-85687},
  doi =		{10.4230/LIPIcs.IPEC.2017.8},
  annote =	{Keywords: red-blue points separation, geometric problem, W\lbrack1\rbrack-hardness, FPT algorithm, ETH-based lower bound}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2017.26
Treewidth with a Quantifier Alternation Revisited

Authors: Michael Lampis and Valia Mitsou

Published in: LIPIcs, Volume 89, 12th International Symposium on Parameterized and Exact Computation (IPEC 2017)

Abstract
In this paper we take a closer look at the parameterized complexity of \exists\forall SAT, the prototypical complete problem of the class Sigma_2^p, the second level of the polynomial hierarchy. We provide a number of tight fine-grained bounds on the complexity of this problem and its variants with respect to the most important structural graph parameters. Specifically, we show the following lower bounds (assuming the ETH): - It is impossible to decide \exists\forall SAT in time less than double-exponential in the input formula's treewidth. More strongly, we establish the same bound with respect to the formula's primal vertex cover, a much more restrictive measure. This lower bound, which matches the performance of known algorithms, shows that the degeneration of the performance of treewidth-based algorithms to a tower of exponentials already begins in problems with one quantifier alternation. - For the more general \exists\forall CSP problem over a non-boolean domain of size B, there is no algorithm running in time 2^{B^{o(vc)}}, where vc is the input's primal vertex cover. - \exists\forall SAT is already NP-hard even when the input formula has constant modular treewidth (or clique-width), indicating that dense graph parameters are less useful for problems in Sigma_2^p. - For the two weighted versions of \exists\forall SAT recently introduced by de Haan and Szeider, called \exists_k\forall SAT and \exists\forall_k SAT, we give tight upper and lower bounds parameterized by treewidth (or primal vertex cover) and the weight k. Interestingly, the complexity of these two problems turns out to be quite different: one is double-exponential in treewidth, while the other is double-exponential in k. We complement the above negative results by showing a double-exponential FPT algorithm for QBF parameterized by vertex cover, showing that for this parameter the complexity never goes beyond double-exponential, for any number of quantifier alternations.
Cite as

Michael Lampis and Valia Mitsou. Treewidth with a Quantifier Alternation Revisited. In 12th International Symposium on Parameterized and Exact Computation (IPEC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 89, pp. 26:1-26:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{lampis_et_al:LIPIcs.IPEC.2017.26,
  author =	{Lampis, Michael and Mitsou, Valia},
  title =	{{Treewidth with a Quantifier Alternation Revisited}},
  booktitle =	{12th International Symposium on Parameterized and Exact Computation (IPEC 2017)},
  pages =	{26:1--26:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-051-4},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{89},
  editor =	{Lokshtanov, Daniel and Nishimura, Naomi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2017.26},
  URN =		{urn:nbn:de:0030-drops-85512},
  doi =		{10.4230/LIPIcs.IPEC.2017.26},
  annote =	{Keywords: Treewidth, Exponential Time Hypothesis, Quantified SAT}
}
Document
DOI: 10.4230/LIPIcs.STACS.2018.10
Parameterized (Approximate) Defective Coloring

Authors: Rémy Belmonte, Michael Lampis, and Valia Mitsou

Published in: LIPIcs, Volume 96, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)

Abstract
In Defective Coloring we are given a graph G=(V,E) and two integers chi_d,Delta^* and are asked if we can partition V into chi_d color classes, so that each class induces a graph of maximum degree Delta^*. We investigate the complexity of this generalization of Coloring with respect to several well-studied graph parameters, and show that the problem is W-hard parameterized by treewidth, pathwidth, tree-depth, or feedback vertex set, if chi_d=2. As expected, this hardness can be extended to larger values of chi_d for most of these parameters, with one surprising exception: we show that the problem is FPT parameterized by feedback vertex set for any chi_d != 2, and hence 2-coloring is the only hard case for this parameter. In addition to the above, we give an ETH-based lower bound for treewidth and pathwidth, showing that no algorithm can solve the problem in n^{o(pw)}, essentially matching the complexity of an algorithm obtained with standard techniques. We complement these results by considering the problem's approximability and show that, with respect to Delta^*, the problem admits an algorithm which for any epsilon>0 runs in time (tw/epsilon)^{O(tw)} and returns a solution with exactly the desired number of colors that approximates the optimal Delta^* within (1+epsilon). We also give a (tw)^{O(tw)} algorithm which achieves the desired Delta^* exactly while 2-approximating the minimum value of chi_d. We show that this is close to optimal, by establishing that no FPT algorithm can (under standard assumptions) achieve a better than 3/2-approximation to chi_d, even when an extra constant additive error is also allowed.
Cite as

Rémy Belmonte, Michael Lampis, and Valia Mitsou. Parameterized (Approximate) Defective Coloring. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 10:1-10:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{belmonte_et_al:LIPIcs.STACS.2018.10,
  author =	{Belmonte, R\'{e}my and Lampis, Michael and Mitsou, Valia},
  title =	{{Parameterized (Approximate) Defective Coloring}},
  booktitle =	{35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)},
  pages =	{10:1--10:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-062-0},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{96},
  editor =	{Niedermeier, Rolf and Vall\'{e}e, Brigitte},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2018.10},
  URN =		{urn:nbn:de:0030-drops-85304},
  doi =		{10.4230/LIPIcs.STACS.2018.10},
  annote =	{Keywords: Treewidth, Parameterized Complexity, Approximation, Coloring}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2017.50
Structural Parameters, Tight Bounds, and Approximation for (k,r)-Center

Authors: Ioannis Katsikarelis, Michael Lampis, and Vangelis Th. Paschos

Published in: LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017)

Abstract
In (k,r)-Center we are given a (possibly edge-weighted) graph and are asked to select at most k vertices (centers), so that all other vertices are at distance at most r from a center. In this paper we provide a number of tight fine-grained bounds on the complexity of this problem with respect to various standard graph parameters. Specifically: - For any r>=1, we show an algorithm that solves the problem in O*((3r+1)^cw) time, where cw is the clique-width of the input graph, as well as a tight SETH lower bound matching this algorithm's performance. As a corollary, for r=1, this closes the gap that previously existed on the complexity of Dominating Set parameterized by cw. - We strengthen previously known FPT lower bounds, by showing that (k,r)-Center is W[1]-hard parameterized by the input graph's vertex cover (if edge weights are allowed), or feedback vertex set, even if k is an additional parameter. Our reductions imply tight ETH-based lower bounds. Finally, we devise an algorithm parameterized by vertex cover for unweighted graphs. - We show that the complexity of the problem parameterized by tree-depth is 2^Theta(td^2) by showing an algorithm of this complexity and a tight ETH-based lower bound. We complement these mostly negative results by providing FPT approximation schemes parameterized by clique-width or treewidth which work efficiently independently of the values of k,r. In particular, we give algorithms which, for any epsilon>0, run in time O*((tw/epsilon)^O(tw)), O*((cw/epsilon)^O(cw)) and return a (k,(1+epsilon)r)-center, if a (k,r)-center exists, thus circumventing the problem's W-hardness.
Cite as

Ioannis Katsikarelis, Michael Lampis, and Vangelis Th. Paschos. Structural Parameters, Tight Bounds, and Approximation for (k,r)-Center. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 50:1-50:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{katsikarelis_et_al:LIPIcs.ISAAC.2017.50,
  author =	{Katsikarelis, Ioannis and Lampis, Michael and Paschos, Vangelis Th.},
  title =	{{Structural Parameters, Tight Bounds, and Approximation for (k,r)-Center}},
  booktitle =	{28th International Symposium on Algorithms and Computation (ISAAC 2017)},
  pages =	{50:1--50:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-054-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{92},
  editor =	{Okamoto, Yoshio and Tokuyama, Takeshi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.50},
  URN =		{urn:nbn:de:0030-drops-82441},
  doi =		{10.4230/LIPIcs.ISAAC.2017.50},
  annote =	{Keywords: FPT algorithms, Approximation, Treewidth, Clique-width, Domination}
}
Document
DOI: 10.4230/LIPIcs.STACS.2016.22
Time-Approximation Trade-offs for Inapproximable Problems

Authors: Édouard Bonnet, Michael Lampis, and Vangelis Th. Paschos

Published in: LIPIcs, Volume 47, 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)

Abstract
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 delta>0 it admits an m^delta-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.
Cite as

Édouard Bonnet, Michael Lampis, and Vangelis Th. Paschos. Time-Approximation Trade-offs for Inapproximable Problems. In 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 47, pp. 22:1-22:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{bonnet_et_al:LIPIcs.STACS.2016.22,
  author =	{Bonnet, \'{E}douard and Lampis, Michael and Paschos, Vangelis Th.},
  title =	{{Time-Approximation Trade-offs for Inapproximable Problems}},
  booktitle =	{33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)},
  pages =	{22:1--22:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-001-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{47},
  editor =	{Ollinger, Nicolas and Vollmer, Heribert},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2016.22},
  URN =		{urn:nbn:de:0030-drops-57236},
  doi =		{10.4230/LIPIcs.STACS.2016.22},
  annote =	{Keywords: Algorithm, Complexity, Polynomial and Subexponential Approximation, Reduction, Inapproximability}
}
Document
DOI: 10.4230/LIPIcs.STACS.2016.37
Sub-exponential Approximation Schemes for CSPs: From Dense to Almost Sparse

Authors: Dimitris Fotakis, Michael Lampis, and Vangelis Th. Paschos

Published in: LIPIcs, Volume 47, 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)

Abstract
It has long been known, since the classical work of (Arora, Karger, Karpinski, JCSS'99), that MAX-CUT admits a PTAS on dense graphs, and more generally, MAX-k-CSP admits a PTAS on "dense" instances with Omega(n^k) constraints. In this paper we extend and generalize their exhaustive sampling approach, presenting a framework for (1-epsilon)-approximating any MAX-k-CSP problem in sub-exponential time while significantly relaxing the denseness requirement on the input instance. Specifically, we prove that for any constants delta in (0, 1] and epsilon > 0, we can approximate MAX-k-CSP problems with Omega(n^{k-1+delta}) constraints within a factor of (1-epsilon) in time 2^{O(n^{1-delta}*ln(n) / epsilon^3)}. The framework is quite general and includes classical optimization problems, such as MAX-CUT, MAX-DICUT, MAX-k-SAT, and (with a slight extension) k-DENSEST SUBGRAPH, as special cases. For MAX-CUT 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+delta} 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 delta > 0, MAX-k-SAT instances with O(n^{k-1}) clauses cannot be approximated within a ratio better than r in time 2^{O(n^{1-delta})}. Second, the running time of our algorithm is almost tight for all densities. Even for MAX-CUT there exists r<1 such that for all delta' > delta >0, MAX-CUT instances with n^{1+delta} edges cannot be approximated within a ratio better than r in time 2^{n^{1-delta'}}.
Cite as

Dimitris Fotakis, Michael Lampis, and Vangelis Th. Paschos. Sub-exponential Approximation Schemes for CSPs: From Dense to Almost Sparse. In 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 47, pp. 37:1-37:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{fotakis_et_al:LIPIcs.STACS.2016.37,
  author =	{Fotakis, Dimitris and Lampis, Michael and Paschos, Vangelis Th.},
  title =	{{Sub-exponential Approximation Schemes for CSPs: From Dense to Almost Sparse}},
  booktitle =	{33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)},
  pages =	{37:1--37:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-001-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{47},
  editor =	{Ollinger, Nicolas and Vollmer, Heribert},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2016.37},
  URN =		{urn:nbn:de:0030-drops-57388},
  doi =		{10.4230/LIPIcs.STACS.2016.37},
  annote =	{Keywords: polynomial and subexponential approximation, sampling, randomized rounding}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2015.294
Complexity and Approximability of Parameterized MAX-CSPs

Authors: Holger Dell, Eun Jung Kim, Michael Lampis, Valia Mitsou, and Tobias Mömke

Published in: LIPIcs, Volume 43, 10th International Symposium on Parameterized and Exact Computation (IPEC 2015)

Abstract
We study the optimization version of constraint satisfaction problems (Max-CSPs) in the framework of parameterized complexity; the goal is to compute the maximum fraction of constraints that can be satisfied simultaneously. In standard CSPs, we want to decide whether this fraction equals one. The parameters we investigate are structural measures, such as the treewidth or the clique-width of the variable–constraint incidence graph of the CSP instance. We consider Max-CSPs with the constraint types AND, OR, PARITY, and MAJORITY, and with various parameters k. We attempt to fully classify them into the following three cases: 1. The exact optimum can be computed in FPT-time. 2. It is W[1]-hard to compute the exact optimum, but there is a randomized FPT approximation scheme (FPT-AS), which computes a (1-epsilon)-approximation in time f(k,epsilon) * poly(n). 3. There is no FPT-AS unless FPT=W[1]. For the corresponding standard CSPs, we establish FPT vs. W[1]-hardness results.
Cite as

Holger Dell, Eun Jung Kim, Michael Lampis, Valia Mitsou, and Tobias Mömke. Complexity and Approximability of Parameterized MAX-CSPs. In 10th International Symposium on Parameterized and Exact Computation (IPEC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 43, pp. 294-306, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{dell_et_al:LIPIcs.IPEC.2015.294,
  author =	{Dell, Holger and Kim, Eun Jung and Lampis, Michael and Mitsou, Valia and M\"{o}mke, Tobias},
  title =	{{Complexity and Approximability of Parameterized MAX-CSPs}},
  booktitle =	{10th International Symposium on Parameterized and Exact Computation (IPEC 2015)},
  pages =	{294--306},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-92-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{43},
  editor =	{Husfeldt, Thore and Kanj, Iyad},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2015.294},
  URN =		{urn:nbn:de:0030-drops-55910},
  doi =		{10.4230/LIPIcs.IPEC.2015.294},
  annote =	{Keywords: Approximation, Structural Parameters, Constraint Satisfaction}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2006.684
Periodic Metro Scheduling

Authors: Evangelos Bampas, Georgia Kaouri, Michael Lampis, and Aris Pagourtzis

Published in: OASIcs, Volume 5, 6th Workshop on Algorithmic Methods and Models for Optimization of Railways (ATMOS'06) (2006)

Abstract
We introduce the { extsc{Periodic Metro Sched-ul-ing}} ({ extsc{PMS}}) problem, which aims in generating a periodic timetable for a given set of routes and a given time period, in such a way that the minimum time distance between any two successive trains that pass from the same point of the network is maximized. This can be particularly useful in cases where trains use the same rail segment quite often, as happens in metropolitan rail networks. We present exact algorithms for ({ extsc{PMS}}) in chain and spider networks, and constant ratio approximation algorithms for ring networks and for a special class of tree networks. Some of our algorithms are based on a reduction to the { extsc{Path Coloring}} problem, while others rely on techniques specially designed for the new problem.
Cite as

Evangelos Bampas, Georgia Kaouri, Michael Lampis, and Aris Pagourtzis. Periodic Metro Scheduling. In 6th Workshop on Algorithmic Methods and Models for Optimization of Railways (ATMOS'06). Open Access Series in Informatics (OASIcs), Volume 5, pp. 1-15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{bampas_et_al:OASIcs.ATMOS.2006.684,
  author =	{Bampas, Evangelos and Kaouri, Georgia and Lampis, Michael and Pagourtzis, Aris},
  title =	{{Periodic Metro Scheduling}},
  booktitle =	{6th Workshop on Algorithmic Methods and Models for Optimization of Railways (ATMOS'06)},
  pages =	{1--15},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-01-9},
  ISSN =	{2190-6807},
  year =	{2006},
  volume =	{5},
  editor =	{Jacob, Riko and M\"{u}ller-Hannemann, Matthias},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2006.684},
  URN =		{urn:nbn:de:0030-drops-6841},
  doi =		{10.4230/OASIcs.ATMOS.2006.684},
  annote =	{Keywords: Train scheduling, path coloring, delay-tolerant scheduling, periodic timetabling}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact