20 Search Results for "Belmonte, Rémy"

Document
DOI: 10.4230/LIPIcs.STACS.2026.19
A Linear Kernel for Independent Set Reconfiguration in Planar Graphs

Authors: Nicolas Bousquet and Daniel W. Cranston

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract
Fix a positive integer r, and a graph G that is K_{3,r}-minor-free. Let I_s and I_t be two independent sets in G, each of size k. We begin with a "token" on each vertex of I_s and seek to move all tokens to I_t, by repeated "token jumping", removing a single token from one vertex and placing it on another vertex. We require that each intermediate arrangement of tokens again specifies an independent set of size k. Given G, I_s, and I_t, we ask whether there exists a sequence of token jumps that transforms I_s into I_t. When k is part of the input, this problem is known to be PSPACE-complete. But it was shown by Ito, Kamiński, and Ono [Ito et al., 2014] to be fixed-parameter tractable. That is, the problem can be solved in time f(k)⋅ P(n), for some function f and polynomial P, where n denotes the order of G. Here we strengthen the upper bound on the running time in terms of k by showing that the problem has a kernel of size linear in k. More precisely, we transform an arbitrary input problem on a K_{3,r}-minor-free graph (for some fixed positive integer r) into an equivalent problem on a (K_{3,r}-minor-free) graph with order O(k). This answers positively a question of Bousquet, Mouawad, Nishimura, and Siebertz [Nicolas Bousquet et al., 2022] and improves the recent quadratic kernel of Cranston, Mühlenthaler, and Peyrille [Daniel W. Cranston et al., 2024]. For planar graphs, we further strengthen this upper bound to get a kernel of size at most 42k.
Cite as

Nicolas Bousquet and Daniel W. Cranston. A Linear Kernel for Independent Set Reconfiguration in Planar Graphs. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 19:1-19:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bousquet_et_al:LIPIcs.STACS.2026.19,
  author =	{Bousquet, Nicolas and Cranston, Daniel W.},
  title =	{{A Linear Kernel for Independent Set Reconfiguration in Planar Graphs}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{19:1--19:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.19},
  URN =		{urn:nbn:de:0030-drops-255081},
  doi =		{10.4230/LIPIcs.STACS.2026.19},
  annote =	{Keywords: Reconfiguration, Independent Set, Kernel, Planar graphs}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2025.31
Hamiltonicity Parameterized by Mim-Width Is (Indeed) Para-NP-Hard

Authors: Benjamin Bergougnoux and Lars Jaffke

Published in: LIPIcs, Volume 358, 20th International Symposium on Parameterized and Exact Computation (IPEC 2025)

Abstract
We prove that Hamiltonian Path and Hamiltonian Cycle are NP-hard on graphs of linear mim-width 26, even when a linear order of the input graph with mim-width 26 is provided together with input. This fills a gap left by a broken proof of the para-NP-hardness of Hamiltonicity problems parameterized by mim-width.
Cite as

Benjamin Bergougnoux and Lars Jaffke. Hamiltonicity Parameterized by Mim-Width Is (Indeed) Para-NP-Hard. In 20th International Symposium on Parameterized and Exact Computation (IPEC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 358, pp. 31:1-31:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bergougnoux_et_al:LIPIcs.IPEC.2025.31,
  author =	{Bergougnoux, Benjamin and Jaffke, Lars},
  title =	{{Hamiltonicity Parameterized by Mim-Width Is (Indeed) Para-NP-Hard}},
  booktitle =	{20th International Symposium on Parameterized and Exact Computation (IPEC 2025)},
  pages =	{31:1--31:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-407-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{358},
  editor =	{Agrawal, Akanksha and van Leeuwen, Erik Jan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2025.31},
  URN =		{urn:nbn:de:0030-drops-251631},
  doi =		{10.4230/LIPIcs.IPEC.2025.31},
  annote =	{Keywords: Hamiltonian Path, Hamiltonian Cycle, Mim-Width, Para-NP-Hardness}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2025.43
A Finer View of the Parameterized Landscape of Labeled Graph Contractions

Authors: Yashaswini Mathur and Prafullkumar Tale

Published in: LIPIcs, Volume 360, 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025)

Abstract
We study the Labeled Contractibility problem, where the input consists of two vertex-labeled graphs G and H, and the goal is to determine whether H can be obtained from G via a sequence of edge contractions. Lafond and Marchand [WADS 2025] initiated the parameterized complexity study of this problem, showing it to be W[1]-hard when parameterized by the number k of allowed contractions. They also proved that the problem is fixed-parameter tractable when parameterized by the tree-width tw of G, via an application of Courcelle’s theorem resulting in a non-constructive algorithm. In this work, we present a constructive fixed-parameter algorithm for Labeled Contractibility with running time 2^{𝒪(tw²)} ⋅ |V(G)|^{𝒪(1)}. We also prove that unless the Exponential Time Hypothesis ({ETH}) fails, it does not admit an algorithm running in time 2^{o(tw²)} ⋅ |V(G)|^{𝒪(1)}. This result adds Labeled Contractibility to a small list of problems that admit such a lower bound and matching algorithm. We further strengthen existing hardness results by showing that the problem remains NP-complete even when both input graphs have bounded maximum degree. We also investigate parameterizations by (k + δ(G)) where δ(G) denotes the degeneracy of G, and rule out the existence of subexponential-time algorithms. This answers question raised in Lafond and Marchand [WADS 2025]. We additionally provide an improved FPT algorithm with better dependence on (k + δ(G)) than previously known. Finally, we analyze a brute-force algorithm for Labeled Contractibility with running time |V(H)|^{𝒪(|V(G)|)}, and show that this running time is optimal under {ETH}.
Cite as

Yashaswini Mathur and Prafullkumar Tale. A Finer View of the Parameterized Landscape of Labeled Graph Contractions. In 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 360, pp. 43:1-43:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{mathur_et_al:LIPIcs.FSTTCS.2025.43,
  author =	{Mathur, Yashaswini and Tale, Prafullkumar},
  title =	{{A Finer View of the Parameterized Landscape of Labeled Graph Contractions}},
  booktitle =	{45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025)},
  pages =	{43:1--43:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-406-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{360},
  editor =	{Aiswarya, C. and Mehta, Ruta and Roy, Subhajit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2025.43},
  URN =		{urn:nbn:de:0030-drops-251237},
  doi =		{10.4230/LIPIcs.FSTTCS.2025.43},
  annote =	{Keywords: Labeled Contraction, ETH Lower-bound, Treewidth, NP-hard}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2025.31
Token Sliding Independent Set Reconfiguration on Block Graphs

Authors: Mathew C. Francis and Veena Prabhakaran

Published in: LIPIcs, Volume 360, 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025)

Abstract
Let S be an independent set of a simple undirected graph G. Suppose that each vertex of S has a token placed on it. The tokens are allowed to be moved, one at a time, by sliding along the edges of G while maintaining the property that after each move, the vertices having tokens always form an independent set of G. We would like to determine whether the tokens can be eventually brought to stay on the vertices of another independent set S' of G in this manner. In other words, we would like to decide if we can transform S into S' through a sequence of steps, each of which involves substituting a vertex in the current independent set with one of its neighbours to obtain another independent set. This problem of determining if one independent set of a graph "is reachable" from another independent set of it is known to be PSPACE-hard even for split graphs, planar graphs, and graphs of bounded treewidth. Polynomial time algorithms have been obtained for certain graph classes like trees, interval graphs, claw-free graphs, and bipartite permutation graphs. We present a polynomial time algorithm for the problem on block graphs, which are the graphs in which every maximal 2-connected subgraph is a clique. Our algorithm is the first generalization of the known polynomial time algorithm for trees to a larger class of graphs.
Cite as

Mathew C. Francis and Veena Prabhakaran. Token Sliding Independent Set Reconfiguration on Block Graphs. In 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 360, pp. 31:1-31:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{francis_et_al:LIPIcs.FSTTCS.2025.31,
  author =	{Francis, Mathew C. and Prabhakaran, Veena},
  title =	{{Token Sliding Independent Set Reconfiguration on Block Graphs}},
  booktitle =	{45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025)},
  pages =	{31:1--31:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-406-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{360},
  editor =	{Aiswarya, C. and Mehta, Ruta and Roy, Subhajit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2025.31},
  URN =		{urn:nbn:de:0030-drops-251120},
  doi =		{10.4230/LIPIcs.FSTTCS.2025.31},
  annote =	{Keywords: Token sliding independent set reconfiguration, block graphs, polynomial time algorithm}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2025.39
Reachability of Independent Sets and Vertex Covers Under Extended Reconfiguration Rules

Authors: Shuichi Hirahara, Naoto Ohsaka, Tatsuhiro Suga, Akira Suzuki, Yuma Tamura, and Xiao Zhou

Published in: LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025)

Abstract
In reconfiguration problems, we are given two feasible solutions to a graph problem and asked whether one can be transformed into the other via a sequence of feasible intermediate solutions under a given reconfiguration rule. While earlier work focused on modifying a single element at a time, recent studies have started examining how different rules impact computational complexity. Motivated by recent progress, we study Independent Set Reconfiguration (ISR) and Vertex Cover Reconfiguration (VCR) under the k-Token Jumping (k-TJ) and k-Token Sliding (k-TS) models. In k-TJ, up to k vertices may be replaced, while k-TS additionally requires a perfect matching between removed and added vertices. It is known that the complexity of ISR crucially depends on k, ranging from PSPACE-complete and NP-complete to polynomial-time solvable. In this paper, we further explore the gradient of computational complexity of the problems. We first show that ISR under k-TJ with k = |I| - μ remains NP-hard when μ is any fixed positive integer and the input graph is restricted to graphs of maximum degree 3 or planar graphs of maximum degree 4, where |I| is the size of feasible solutions. In addition, we prove that the problem belongs to NP not only for μ = O(1) but also for μ = O(log |I|). In contrast, we show that VCR under k-TJ is in XP when parameterized by μ = |S| - k, where |S| is the size of feasible solutions. Furthermore, we establish the PSPACE-completeness of ISR and VCR under both k-TJ and k-TS on several graph classes, for fixed k as well as superconstant k relative to the size of feasible solutions.
Cite as

Shuichi Hirahara, Naoto Ohsaka, Tatsuhiro Suga, Akira Suzuki, Yuma Tamura, and Xiao Zhou. Reachability of Independent Sets and Vertex Covers Under Extended Reconfiguration Rules. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 39:1-39:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{hirahara_et_al:LIPIcs.ISAAC.2025.39,
  author =	{Hirahara, Shuichi and Ohsaka, Naoto and Suga, Tatsuhiro and Suzuki, Akira and Tamura, Yuma and Zhou, Xiao},
  title =	{{Reachability of Independent Sets and Vertex Covers Under Extended Reconfiguration Rules}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{39:1--39:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-408-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{359},
  editor =	{Chen, Ho-Lin and Hon, Wing-Kai and Tsai, Meng-Tsung},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.39},
  URN =		{urn:nbn:de:0030-drops-249474},
  doi =		{10.4230/LIPIcs.ISAAC.2025.39},
  annote =	{Keywords: combinatorial reconfiguration, extended reconfiguration rule, independent set reconfiguration, vertex cover reconfiguration, PSPACE-completeness, NP-completeness}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2025.33
Coloring Reconfiguration Under Color Swapping

Authors: Janosch Fuchs, Rin Saito, Tatsuhiro Suga, Takahiro Suzuki, and Yuma Tamura

Published in: LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025)

Abstract
In the Coloring Reconfiguration problem, we are given two proper k-colorings of a graph and asked to decide whether one can be transformed into the other by repeatedly applying a specified recoloring rule, while maintaining a proper coloring throughout. For this problem, two recoloring rules have been widely studied: single-vertex recoloring and Kempe chain recoloring. In this paper, we introduce a new rule, called color swapping, where two adjacent vertices may exchange their colors, so that the resulting coloring remains proper, and study the computational complexity of the problem under this rule. We first establish a complexity dichotomy with respect to k: the problem is solvable in polynomial time for k ≤ 2, and is PSPACE-complete for k ≥ 3. We further show that the problem remains PSPACE-complete even on restricted graph classes, including bipartite graphs, split graphs, and planar graphs of bounded degree. In contrast, we present polynomial-time algorithms for several graph classes: for paths when k = 3, for split graphs when k is fixed, and for cographs when k is arbitrary.
Cite as

Janosch Fuchs, Rin Saito, Tatsuhiro Suga, Takahiro Suzuki, and Yuma Tamura. Coloring Reconfiguration Under Color Swapping. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 33:1-33:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{fuchs_et_al:LIPIcs.ISAAC.2025.33,
  author =	{Fuchs, Janosch and Saito, Rin and Suga, Tatsuhiro and Suzuki, Takahiro and Tamura, Yuma},
  title =	{{Coloring Reconfiguration Under Color Swapping}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{33:1--33:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-408-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{359},
  editor =	{Chen, Ho-Lin and Hon, Wing-Kai and Tsai, Meng-Tsung},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.33},
  URN =		{urn:nbn:de:0030-drops-249411},
  doi =		{10.4230/LIPIcs.ISAAC.2025.33},
  annote =	{Keywords: Combinatorial reconfiguration, graph coloring, PSPACE-complete, graph algorithm}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.10
Connected Partitions via Connected Dominating Sets

Authors: Aikaterini Niklanovits, Kirill Simonov, Shaily Verma, and Ziena Zeif

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
The classical theorem due to Győri and Lovász states that any k-connected graph G admits a partition into k connected subgraphs, where each subgraph has a prescribed size and contains a prescribed vertex, as long as the total size of target subgraphs is equal to the size of G. However, this result is notoriously evasive in terms of efficient constructions, and it is still unknown whether such a partition can be computed in polynomial time, even for k = 5. We make progress towards an efficient constructive version of the Győri-Lovász theorem by considering a natural strengthening of the k-connectivity requirement. Specifically, we show that the desired connected partition can be found in polynomial time, if G contains k disjoint connected dominating sets. As a consequence of this result, we give several efficient approximate and exact constructive versions of the original Győri-Lovász theorem: - On general graphs, a Győri-Lovász partition with k parts can be computed in polynomial time when the input graph has connectivity Ω(k ⋅ log² n); - On convex bipartite graphs, connectivity of 4k is sufficient; - On biconvex graphs and interval graphs, connectivity of k is sufficient, meaning that our algorithm gives a "true" constructive version of the theorem on these graph classes.
Cite as

Aikaterini Niklanovits, Kirill Simonov, Shaily Verma, and Ziena Zeif. Connected Partitions via Connected Dominating Sets. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 10:1-10:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{niklanovits_et_al:LIPIcs.ESA.2025.10,
  author =	{Niklanovits, Aikaterini and Simonov, Kirill and Verma, Shaily and Zeif, Ziena},
  title =	{{Connected Partitions via Connected Dominating Sets}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{10:1--10:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian 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.2025.10},
  URN =		{urn:nbn:de:0030-drops-244785},
  doi =		{10.4230/LIPIcs.ESA.2025.10},
  annote =	{Keywords: Gy\H{o}ri-Lov\'{a}sz theorem, connected dominating sets, graph classes}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.29
The Tape Reconfiguration Problem and Its Consequences for Dominating Set Reconfiguration

Authors: Nicolas Bousquet, Quentin Deschamps, Arnaud Mary, Amer E. Mouawad, and Théo Pierron

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
A dominating set of a graph G = (V,E) is a set of vertices D ⊆ V whose closed neighborhood is V, i.e., N[D] = V. We view a dominating set as a collection of tokens placed on the vertices of D. In the token sliding variant of the Dominating Set Reconfiguration problem (TS-DSR), we seek to transform a source dominating set into a target dominating set in G by sliding tokens along edges, and while maintaining a dominating set all along the transformation. TS-DSR is known to be PSPACE-complete even restricted to graphs of pathwidth w, for some non-explicit constant w and to be XL-complete parameterized by the size k of the solution. The first contribution of this article consists in using a novel approach to provide the first explicit constant for which the TS-DSR problem is PSPACE-complete, a question that was left open in the literature. From a parameterized complexity perspective, the token jumping variant of DSR, i.e., where tokens can jump to arbitrary vertices, is known to be FPT when parameterized by the size of the dominating sets on nowhere dense classes of graphs. But, in contrast, no non-trivial result was known about TS-DSR. We prove that DSR is actually much harder in the sliding model since it is XL-complete when restricted to bounded pathwidth graphs and even when parameterized by k plus the feedback vertex set number of the graph. This gives, for the first time, a difference of behavior between the complexity under token sliding and token jumping for some problem on graphs of bounded treewidth. All our results are obtained using a brand new method, based on the hardness of the so-called Tape Reconfiguration problem, a problem we believe to be of independent interest. We complement these hardness results with a positive result showing that DSR (parameterized by k) in the sliding model is FPT on planar graphs, also answering an open problem from the literature.
Cite as

Nicolas Bousquet, Quentin Deschamps, Arnaud Mary, Amer E. Mouawad, and Théo Pierron. The Tape Reconfiguration Problem and Its Consequences for Dominating Set Reconfiguration. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 29:1-29:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bousquet_et_al:LIPIcs.ESA.2025.29,
  author =	{Bousquet, Nicolas and Deschamps, Quentin and Mary, Arnaud and Mouawad, Amer E. and Pierron, Th\'{e}o},
  title =	{{The Tape Reconfiguration Problem and Its Consequences for Dominating Set Reconfiguration}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{29:1--29:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian 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.2025.29},
  URN =		{urn:nbn:de:0030-drops-244974},
  doi =		{10.4230/LIPIcs.ESA.2025.29},
  annote =	{Keywords: combinatorial reconfiguration, parameterized complexity, structural graph parameters, treewidth, dominating set}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.16
On Algorithmic Applications of ℱ-Branchwidth

Authors: Benjamin Bergougnoux, Thekla Hamm, Lars Jaffke, and Paloma T. Lima

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
F-branchwidth is a framework for width measures of graphs, recently introduced by Eiben et al. [ITCS 2022], that captures tree-width, co-tree-width, clique-width, and mim-width, and several of their generalizations and interpolations. In this work, we search for algorithmic applications of F-branchwidth measures that do not have an equivalent counterpart in the literature so far. Our first contribution is a minimal set of eleven F-branchwidth measures such that each of the infinitely many F-branchwidth measures is equivalent to one of the eleven. We observe that for the FO Model Checking problem, each F-branchwidth is either equivalent to clique-width (and therefore has an FPT-algorithm by formula length plus the width) or the problem remains as hard as on general graphs even on graphs of constant width. Next, we study the number of equivalence classes of the neighborhood equivalence in a decomposition, which upper bounds the run time of the model checking algorithm for ACDN logic recently introduced by Bergougnoux et al. [SODA 2023]. We give structural lower bounds that show that for each F-branchwidth, an efficient model checking algorithm was already known or cannot be obtained via this method. Lastly, we classify the complexity of Independent Set parameterized by any F-branchwidth except for one open case. Also here, our contributions are lower bounds. In this context, we also prove that Independent Set on graphs of mim-width w cannot be solved in time n^o(w) unless the Exponential Time Hypothesis fails, answering an open question in the literature.
Cite as

Benjamin Bergougnoux, Thekla Hamm, Lars Jaffke, and Paloma T. Lima. On Algorithmic Applications of ℱ-Branchwidth. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 16:1-16:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bergougnoux_et_al:LIPIcs.ESA.2025.16,
  author =	{Bergougnoux, Benjamin and Hamm, Thekla and Jaffke, Lars and Lima, Paloma T.},
  title =	{{On Algorithmic Applications of ℱ-Branchwidth}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{16:1--16:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian 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.2025.16},
  URN =		{urn:nbn:de:0030-drops-244849},
  doi =		{10.4230/LIPIcs.ESA.2025.16},
  annote =	{Keywords: Graph width parameters, parameterized complexity, F-branchwidth, tree-width, clique-width, rank-width, mim-width, FO model checking, DN logic, Independent Set, ETH}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2025.65
Parameterized Spanning Tree Congestion

Authors: Michael Lampis, Valia Mitsou, Edouard Nemery, Yota Otachi, Manolis Vasilakis, and Daniel Vaz

Published in: LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)

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

Michael Lampis, Valia Mitsou, Edouard Nemery, Yota Otachi, Manolis Vasilakis, and Daniel Vaz. Parameterized Spanning Tree Congestion. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 65:1-65:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{lampis_et_al:LIPIcs.MFCS.2025.65,
  author =	{Lampis, Michael and Mitsou, Valia and Nemery, Edouard and Otachi, Yota and Vasilakis, Manolis and Vaz, Daniel},
  title =	{{Parameterized Spanning Tree Congestion}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{65:1--65:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-388-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{345},
  editor =	{Gawrychowski, Pawe{\l} and Mazowiecki, Filip and Skrzypczak, Micha{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.65},
  URN =		{urn:nbn:de:0030-drops-241724},
  doi =		{10.4230/LIPIcs.MFCS.2025.65},
  annote =	{Keywords: Parameterized Complexity, Treewidth, Graph Width Parameters}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.25
Mim-Width Is paraNP-Complete

Authors: Benjamin Bergougnoux, Édouard Bonnet, and Julien Duron

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
We show that it is NP-hard to distinguish graphs of linear mim-width at most 1211 from graphs of sim-width at least 1216. This implies that Mim-Width, Sim-Width, One-Sided Mim-Width, and their linear counterparts are all paraNP-complete, i.e., NP-complete to compute even when upper bounded by a constant. A key intermediate problem that we introduce and show NP-complete, Linear Degree Balancing, inputs an edge-weighted graph G and an integer τ, and asks whether V(G) can be linearly ordered such that every vertex of G has weighted backward and forward degrees at most τ.
Cite as

Benjamin Bergougnoux, Édouard Bonnet, and Julien Duron. Mim-Width Is paraNP-Complete. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 25:1-25:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bergougnoux_et_al:LIPIcs.ICALP.2025.25,
  author =	{Bergougnoux, Benjamin and Bonnet, \'{E}douard and Duron, Julien},
  title =	{{Mim-Width Is paraNP-Complete}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{25:1--25:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l 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.2025.25},
  URN =		{urn:nbn:de:0030-drops-234020},
  doi =		{10.4230/LIPIcs.ICALP.2025.25},
  annote =	{Keywords: Mim-width, lower bounds, parameterized complexity, ordered graphs}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.39
Sampling with a Black Box: Faster Parameterized Approximation Algorithms for Vertex Deletion Problems

Authors: Barış Can Esmer and Ariel Kulik

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
In this paper, we present Sampling with a Black Box, a unified framework for the design of parameterized approximation algorithms for vertex deletion problems (e.g., Vertex Cover, Feedback Vertex Set, etc.). The framework relies on two components: - A Sampling Step. A polynomial-time randomized algorithm that, given a graph G, returns a random vertex v such that the optimum of G⧵ {v} is smaller by 1 than the optimum of G, with some prescribed probability q. We show that such algorithms exist for multiple vertex deletion problems. - A Black Box algorithm which is either an exact parameterized algorithm, a polynomial-time approximation algorithm, or a parameterized-approximation algorithm. The framework combines these two components together. The sampling step is applied iteratively to remove vertices from the input graph, and then the solution is extended using the black box algorithm. The process is repeated sufficiently many times so that the target approximation ratio is attained with a constant probability. We use the technique to derive parameterized approximation algorithms for several vertex deletion problems, including Feedback Vertex Set, d-Hitting Set and 𝓁-Path Vertex Cover. In particular, for every approximation ratio 1 < β < 2, we attain a parameterized β-approximation for Feedback Vertex Set, which is faster than the parameterized β-approximation of [Jana, Lokshtanov, Mandal, Rai and Saurabh, MFCS 23']. Furthermore, our algorithms are always faster than the algorithms attained using Fidelity Preserving Transformations [Fellows, Kulik, Rosamond, and Shachnai, JCSS 18'].
Cite as

Barış Can Esmer and Ariel Kulik. Sampling with a Black Box: Faster Parameterized Approximation Algorithms for Vertex Deletion Problems. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 39:1-39:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{canesmer_et_al:LIPIcs.ICALP.2025.39,
  author =	{Can Esmer, Bar{\i}\c{s} and Kulik, Ariel},
  title =	{{Sampling with a Black Box: Faster Parameterized Approximation Algorithms for Vertex Deletion Problems}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{39:1--39:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l 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.2025.39},
  URN =		{urn:nbn:de:0030-drops-234165},
  doi =		{10.4230/LIPIcs.ICALP.2025.39},
  annote =	{Keywords: Parameterized Approximation Algorithms, Random Sampling}
}
Document
DOI: 10.4230/LIPIcs.STACS.2025.5
Parameterized Saga of First-Fit and Last-Fit Coloring

Authors: Akanksha Agrawal, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, and Shaily Verma

Published in: LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)

Abstract
The classic greedy coloring algorithm considers the vertices of an input graph G in a given order and assigns the first available color to each vertex v in G. In the Grundy Coloring problem, the task is to find an ordering of the vertices that will force the greedy algorithm to use as many colors as possible. In the Partial Grundy Coloring, the task is also to color the graph using as many colors as possible. This time, however, we may select both the ordering in which the vertices are considered and which color to assign the vertex. The only constraint is that the color assigned to a vertex v is a color previously used for another vertex if such a color is available. Whether Grundy Coloring and Partial Grundy Coloring admit fixed-parameter tractable (FPT) algorithms, algorithms with running time f(k)n^O(1), where k is the number of colors, was posed as an open problem by Zaker and by Effantin et al., respectively. Recently, Aboulker et al. (STACS 2020 and Algorithmica 2022) resolved the question for Grundy Coloring in the negative by showing that the problem is W[1]-hard. For Partial Grundy Coloring, they obtain an FPT algorithm on graphs that do not contain K_{i,j} as a subgraph (a.k.a. K_{i,j}-free graphs). Aboulker et al. re-iterate the question of whether there exists an FPT algorithm for Partial Grundy Coloring on general graphs and also asks whether Grundy Coloring admits an FPT algorithm on K_{i,j}-free graphs. We give FPT algorithms for Partial Grundy Coloring on general graphs and for Grundy Coloring on K_{i,j}-free graphs, resolving both the questions in the affirmative. We believe that our new structural theorems for partial Grundy coloring and "representative-family" like sets for K_{i,j}-free graphs that we use in obtaining our results may have wider algorithmic applications.
Cite as

Akanksha Agrawal, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, and Shaily Verma. Parameterized Saga of First-Fit and Last-Fit Coloring. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 327, pp. 5:1-5:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{agrawal_et_al:LIPIcs.STACS.2025.5,
  author =	{Agrawal, Akanksha and Lokshtanov, Daniel and Panolan, Fahad and Saurabh, Saket and Verma, Shaily},
  title =	{{Parameterized Saga of First-Fit and Last-Fit Coloring}},
  booktitle =	{42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)},
  pages =	{5:1--5:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-365-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{327},
  editor =	{Beyersdorff, Olaf and Pilipczuk, Micha{\l} and Pimentel, Elaine and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2025.5},
  URN =		{urn:nbn:de:0030-drops-228304},
  doi =		{10.4230/LIPIcs.STACS.2025.5},
  annote =	{Keywords: Grundy Coloring, Partial Grundy Coloring, FPT Algorithm, K\underline\{i,j\}-free graphs}
}
Document
DOI: 10.4230/LIPIcs.STACS.2025.36
MaxMin Separation Problems: FPT Algorithms for st-Separator and Odd Cycle Transversal

Authors: Ajinkya Gaikwad, Hitendra Kumar, Soumen Maity, Saket Saurabh, and Roohani Sharma

Published in: LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)

Abstract
In this paper, we study the parameterized complexity of the MaxMin versions of two fundamental separation problems: Maximum Minimal st-Separator and Maximum Minimal Odd Cycle Transversal (OCT), both parameterized by the solution size. In the Maximum Minimal st-Separator problem, given a graph G, two distinct vertices s and t and a positive integer k, the goal is to determine whether there exists a minimal st-separator in G of size at least k. Similarly, the Maximum Minimal OCT problem seeks to determine if there exists a minimal set of vertices whose deletion results in a bipartite graph, and whose size is at least k. We demonstrate that both problems are fixed-parameter tractable parameterized by k. Our FPT algorithm for Maximum Minimal st-Separator answers the open question by Hanaka, Bodlaender, van der Zanden & Ono [TCS 2019]. One unique insight from this work is the following. We use the meta-result of Lokshtanov, Ramanujan, Saurabh & Zehavi [ICALP 2018] that enables us to reduce our problems to highly unbreakable graphs. This is interesting, as an explicit use of the recursive understanding and randomized contractions framework of Chitnis, Cygan, Hajiaghayi, Pilipczuk & Pilipczuk [SICOMP 2016] to reduce to the highly unbreakable graphs setting (which is the result that Lokshtanov et al. tries to abstract out in their meta-theorem) does not seem obvious because certain "extension" variants of our problems are W[1]-hard.
Cite as

Ajinkya Gaikwad, Hitendra Kumar, Soumen Maity, Saket Saurabh, and Roohani Sharma. MaxMin Separation Problems: FPT Algorithms for st-Separator and Odd Cycle Transversal. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 327, pp. 36:1-36:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{gaikwad_et_al:LIPIcs.STACS.2025.36,
  author =	{Gaikwad, Ajinkya and Kumar, Hitendra and Maity, Soumen and Saurabh, Saket and Sharma, Roohani},
  title =	{{MaxMin Separation Problems: FPT Algorithms for st-Separator and Odd Cycle Transversal}},
  booktitle =	{42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)},
  pages =	{36:1--36:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-365-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{327},
  editor =	{Beyersdorff, Olaf and Pilipczuk, Micha{\l} and Pimentel, Elaine and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2025.36},
  URN =		{urn:nbn:de:0030-drops-228622},
  doi =		{10.4230/LIPIcs.STACS.2025.36},
  annote =	{Keywords: Parameterized Complexity, FPT, MaxMin problems, Maximum Minimal st-separator, Maximum Minimal Odd Cycle Transversal, Unbreakable Graphs, CMSO, Long Induced Odd Cycles, Sunflower Lemma}
}
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}
}
  • Refine by Type
  • 20 Document/PDF
  • 14 Document/HTML

  • Refine by Publication Year
  • 1 2026
  • 13 2025
  • 1 2022
  • 1 2020
  • 1 2019
  • Show More...

  • Refine by Author
  • 7 Lampis, Michael
  • 5 Belmonte, Rémy
  • 4 Mitsou, Valia
  • 4 Otachi, Yota
  • 3 Bergougnoux, Benjamin
  • Show More...

  • Refine by Series/Journal
  • 20 LIPIcs

  • Refine by Classification
  • 8 Theory of computation → Parameterized complexity and exact algorithms
  • 7 Mathematics of computing → Graph algorithms
  • 4 Theory of computation → Fixed parameter tractability
  • 4 Theory of computation → Graph algorithms analysis
  • 3 Theory of computation → Problems, reductions and completeness
  • Show More...

  • Refine by Keyword
  • 6 Treewidth
  • 4 parameterized complexity
  • 3 Parameterized Complexity
  • 2 Grundy Coloring
  • 2 Independent Set
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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