33 Search Results for "Sikora, Florian"

Document
DOI: 10.4230/LIPIcs.CPM.2026.27
Exploring the Gap Between LCS and LCStr

Authors: Shay Golan, Matan Kraus, Ely Porat, and B. Riva Shalom

Published in: LIPIcs, Volume 369, 37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026)

Abstract
The Longest Common Subsequence (LCS) problem and the Longest Common Substring (LCStr) problem are classical string problems with broad theoretical and practical significance. The former has a quadratic conditional lower bound [FOCS, 2015], while the latter admits a linear-time solution. In this paper, we study a natural variation of these problems, the Longest Common Subsequence-Substring (LCSS) problem. The LCSS problem seeks the longest string that is simultaneously a subsequence of one input string and a substring of the other. This variant bridges LCS and LCStr, raising intriguing algorithmic questions: Does the complexity of computing LCSS interpolate between the linear time of LCStr and the quadratic time of LCS? What about approximability? We also examine a natural extension of LCSS to multiple strings, parameterizing the balance between subsequence and substring requirements. Our results reveal several insights. First, under the SETH conjecture, the inherent complexity of LCSS is quadratic, similar to LCS. In contrast, we provide a linear-time approximation for LCSS. Finally, for the multi-string variant, unlike both problems, we design a quadratic-time algorithm, uncovering deeper structural properties of the problem. By studying the complexity of the LCSS problem, we aim to gain some understanding of what influences whether a variant of the LCS problem behaves more like the standard LCS or like LCStr. Our findings suggest that hybrid constraints can create computational "sweet spots," where problems become more tractable than their pure counterparts. This opens a broader research direction in constraint-mediated algorithm design. Beyond LCSS itself, our work highlights unexpected connections between subsequence and substring constraints, advancing the theoretical understanding of string problems and laying the foundation for new algorithmic techniques and complexity-theoretic insights in the rich space between classical string comparison paradigms.
Cite as

Shay Golan, Matan Kraus, Ely Porat, and B. Riva Shalom. Exploring the Gap Between LCS and LCStr. In 37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 369, pp. 27:1-27:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{golan_et_al:LIPIcs.CPM.2026.27,
  author =	{Golan, Shay and Kraus, Matan and Porat, Ely and Shalom, B. Riva},
  title =	{{Exploring the Gap Between LCS and LCStr}},
  booktitle =	{37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026)},
  pages =	{27:1--27:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-420-8},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{369},
  editor =	{Bille, Philip and Prezza, Nicola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2026.27},
  URN =		{urn:nbn:de:0030-drops-259535},
  doi =		{10.4230/LIPIcs.CPM.2026.27},
  annote =	{Keywords: Longest Common Subsequence, Longest Common Substring, Conditional Lower Bound}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2026.20
Near-Linear and Parameterized Approximations for Maximum Cliques in Disk Graphs

Authors: Jie Gao, Paweł Gawrychowski, Panos Giannopoulos, Wolfgang Mulzer, Satyam Singh, Frank Staals, and Meirav Zehavi

Published in: LIPIcs, Volume 370, 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)

Abstract
A disk graph is the intersection graph of (closed) disks in the plane. We consider the classic problem of finding a maximum clique in a disk graph. For general disk graphs, the complexity of this problem is still open, but for unit disk graphs, it is well known to be in P. The currently fastest algorithm runs in time O(n^{7/3+ o(1)}), where n denotes the number of disks [Jared Espenant et al., 2023; J. Mark Keil and Debajyoti Mondal, 2025]. Moreover, for the case of disk graphs with t distinct radii, the problem has also recently been shown to be in XP. More specifically, it is solvable in time O^*(n^{2t}) [J. Mark Keil and Debajyoti Mondal, 2025]. In this paper, we present algorithms with improved running times by allowing for approximate solutions and by using randomization: [(i)] 1) for unit disk graphs, we give an algorithm that, with constant success probability, computes a (1-ε)-approximate maximum clique in expected time Õ(n/ε²); and 2) for disk graphs with t distinct radii, we give a parameterized approximation scheme that, with a constant success probability, computes a (1-ε)-approximate maximum clique in expected time Õ(f(t)⋅ (1/ε)^{O(t)} ⋅ n), for some (exponential) function f(t).
Cite as

Jie Gao, Paweł Gawrychowski, Panos Giannopoulos, Wolfgang Mulzer, Satyam Singh, Frank Staals, and Meirav Zehavi. Near-Linear and Parameterized Approximations for Maximum Cliques in Disk Graphs. In 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 370, pp. 20:1-20:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{gao_et_al:LIPIcs.SWAT.2026.20,
  author =	{Gao, Jie and Gawrychowski, Pawe{\l} and Giannopoulos, Panos and Mulzer, Wolfgang and Singh, Satyam and Staals, Frank and Zehavi, Meirav},
  title =	{{Near-Linear and Parameterized Approximations for Maximum Cliques in Disk Graphs}},
  booktitle =	{20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)},
  pages =	{20:1--20:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-421-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{370},
  editor =	{Fraigniaud, Pierre},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2026.20},
  URN =		{urn:nbn:de:0030-drops-260563},
  doi =		{10.4230/LIPIcs.SWAT.2026.20},
  annote =	{Keywords: Maximum Clique, Disk Graphs, Unit Disk Graphs, FPT Approximation}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2026.25
Parameterized Critical Node Cut Revisited

Authors: Dušan Knop, Nikolaos Melissinos, and Manolis Vasilakis

Published in: LIPIcs, Volume 370, 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)

Abstract
We study how to sparsify connectivity in graphs under a tight deletion budget. Given a graph G and integers k,x ≥ 0, Critical Node Cut (CNC) asks whether we can delete at most k vertices so that the number of remaining unordered pairs of connected vertices is at most x. CNC generalizes Vertex Cover (the case x = 0) and models tasks in network design, epidemiology, and social network analysis. We comprehensively map the structural parameterized complexity landscape for Critical Node Cut. First, we prove W[1]-hardness for the combined parameter k + fes + Δ + pw, where fes is the feedback edge set number, Δ the maximum degree, and pw the pathwidth of the input graph, respectively. This significantly improves over the known W[1]-hardness for k+tw, where tw denotes the treewidth, and is tight in that tree-depth together with maximum degree trivially yields FPT. Second, we give new positive results. Specifically, we identify three structural parameters-max-leaf number, vertex integrity, and modular-width-that render the problem fixed-parameter tractable, and develop a polynomial-time algorithm for graphs of constant clique-width. Third, leveraging a technique introduced by Lampis [ICALP '14], we develop an FPT approximation scheme that, for any ε > 0, computes a (1+ε)-approximate solution in time (tw / ε)^{𝒪(tw)} n^{𝒪(1)}. Finally, we show that CNC admits no polynomial kernel when parameterized by vertex cover number, unless standard assumptions fail. Together, these results substantially sharpen the known complexity landscape for CNC.
Cite as

Dušan Knop, Nikolaos Melissinos, and Manolis Vasilakis. Parameterized Critical Node Cut Revisited. In 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 370, pp. 25:1-25:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{knop_et_al:LIPIcs.SWAT.2026.25,
  author =	{Knop, Du\v{s}an and Melissinos, Nikolaos and Vasilakis, Manolis},
  title =	{{Parameterized Critical Node Cut Revisited}},
  booktitle =	{20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)},
  pages =	{25:1--25:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-421-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{370},
  editor =	{Fraigniaud, Pierre},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2026.25},
  URN =		{urn:nbn:de:0030-drops-260617},
  doi =		{10.4230/LIPIcs.SWAT.2026.25},
  annote =	{Keywords: Critical Node Cut, Parameterized Complexity, Treewidth}
}
Document
DOI: 10.4230/LIPIcs.FORC.2026.10
Packing Compact Subgraphs with Applications to Districting

Authors: Ho-Lin Chen, Po-Yu Chou, Prathamesh Dharangutte, Jie Gao, Shang-En Huang, and Fang-Yi Yu

Published in: LIPIcs, Volume 368, 7th Symposium on Foundations of Responsible Computing (FORC 2026)

Abstract
Packing disjoint subgraphs in a given graph is a fundamental problem with many applications. Motivated by political districting, we focus on connected subgraphs that are compact (e.g., having constant radius from a single center vertex) and that satisfy additional composition requirements, such as a minimum population/weight threshold or balanced weight types (e.g., political affiliations). We aim to maximize coverage by disjoint districts that meet these requirements. In this work, we present new results that substantially improve the previously known bounds on balanced star districts for planar and minor-free graphs [Prathamesh Dharangutte et al., 2025]. In particular, we improve the approximation factor from O(log n) to O(1) for packing balanced star districts using the exact same algorithm, but with a refined analysis. We also extend the results beyond planar graphs to minor-free graphs and an even broader family of graphs of bounded expansion. Additionally, we obtain an O(1) approximation for packing radius-k districts (with a constant k) in planar and apex-minor-free graphs. In order to get a (1+ε) approximation on the max coverage, we show that this can be achieved if we allow a slight relaxation of the balancedness parameters (by a factor that can be made arbitrarily close to 1), for bounded radius-k districts on planar and apex-minor-free graphs. We show that all of these results can also be obtained if we enforce a minimum weight threshold for each district as the composition requirement, rather than balancedness. We present various results on hardness and hardness of approximation for this variant, by graph and district types.
Cite as

Ho-Lin Chen, Po-Yu Chou, Prathamesh Dharangutte, Jie Gao, Shang-En Huang, and Fang-Yi Yu. Packing Compact Subgraphs with Applications to Districting. In 7th Symposium on Foundations of Responsible Computing (FORC 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 368, pp. 10:1-10:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.FORC.2026.10,
  author =	{Chen, Ho-Lin and Chou, Po-Yu and Dharangutte, Prathamesh and Gao, Jie and Huang, Shang-En and Yu, Fang-Yi},
  title =	{{Packing Compact Subgraphs with Applications to Districting}},
  booktitle =	{7th Symposium on Foundations of Responsible Computing (FORC 2026)},
  pages =	{10:1--10:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-419-2},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{368},
  editor =	{Lin, Huijia (Rachel)},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FORC.2026.10},
  URN =		{urn:nbn:de:0030-drops-259820},
  doi =		{10.4230/LIPIcs.FORC.2026.10},
  annote =	{Keywords: Approximation algorithms, algorithmic fairness}
}
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/DagMan.11.1.19
Conversational Agents: A Framework for Evaluation (CAFE) (Dagstuhl Perspectives Workshop 24352)

Authors: Christine Bauer, Li Chen, Nicola Ferro, Norbert Fuhr, Avishek Anand, Timo Breuer, Guglielmo Faggioli, Ophir Frieder, Hideo Joho, Jussi Karlgren, Johannes Kiesel, Bart P. Knijnenburg, Aldo Lipani, Lien Michiels, Andrea Papenmeier, Maria Soledad Pera, Mark Sanderson, Scott Sanner, Benno Stein, Johanne R. Trippas, Karin Verspoor, and Martijn C. Willemsen

Published in: Dagstuhl Manifestos, Volume 11, Issue 1 (2025)

Abstract
During the workshop, we deeply discussed what CONversational Information ACcess (CONIAC) is and its unique features, proposing a world model abstracting it, and defined the Conversational Agents Framework for Evaluation (CAFE) for the evaluation of CONIAC systems, consisting of six major components: 1) goals of the system’s stakeholders, 2) user tasks to be studied in the evaluation, 3) aspects of the users carrying out the tasks, 4) evaluation criteria to be considered, 5) evaluation methodology to be applied, and 6) measures for the quantitative criteria chosen.
Cite as

Christine Bauer, Li Chen, Nicola Ferro, Norbert Fuhr, Avishek Anand, Timo Breuer, Guglielmo Faggioli, Ophir Frieder, Hideo Joho, Jussi Karlgren, Johannes Kiesel, Bart P. Knijnenburg, Aldo Lipani, Lien Michiels, Andrea Papenmeier, Maria Soledad Pera, Mark Sanderson, Scott Sanner, Benno Stein, Johanne R. Trippas, Karin Verspoor, and Martijn C. Willemsen. Conversational Agents: A Framework for Evaluation (CAFE) (Dagstuhl Perspectives Workshop 24352). In Dagstuhl Manifestos, Volume 11, Issue 1, pp. 19-67, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@Article{bauer_et_al:DagMan.11.1.19,
  author =	{Bauer, Christine and Chen, Li and Ferro, Nicola and Fuhr, Norbert and Anand, Avishek and Breuer, Timo and Faggioli, Guglielmo and Frieder, Ophir and Joho, Hideo and Karlgren, Jussi and Kiesel, Johannes and Knijnenburg, Bart P. and Lipani, Aldo and Michiels, Lien and Papenmeier, Andrea and Pera, Maria Soledad and Sanderson, Mark and Sanner, Scott and Stein, Benno and Trippas, Johanne R. and Verspoor, Karin and Willemsen, Martijn C.},
  title =	{{Conversational Agents: A Framework for Evaluation (CAFE) (Dagstuhl Perspectives Workshop 24352)}},
  pages =	{19--67},
  journal =	{Dagstuhl Manifestos},
  ISSN =	{2193-2433},
  year =	{2025},
  volume =	{11},
  number =	{1},
  editor =	{Bauer, Christine and Chen, Li and Ferro, Nicola and Fuhr, Norbert and Anand, Avishek and Breuer, Timo and Faggioli, Guglielmo and Frieder, Ophir and Joho, Hideo and Karlgren, Jussi and Kiesel, Johannes and Knijnenburg, Bart P. and Lipani, Aldo and Michiels, Lien and Papenmeier, Andrea and Pera, Maria Soledad and Sanderson, Mark and Sanner, Scott and Stein, Benno and Trippas, Johanne R. and Verspoor, Karin and Willemsen, Martijn C.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagMan.11.1.19},
  URN =		{urn:nbn:de:0030-drops-252722},
  doi =		{10.4230/DagMan.11.1.19},
  annote =	{Keywords: Conversational Agents, Evaluation, Information Access}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2025.32
The PACE 2025 Parameterized Algorithms and Computational Experiments Challenge: Dominating Set and Hitting Set

Authors: Mario Grobler and Sebastian Siebertz

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

Abstract
The 10th iteration of the of the Parameterized Algorithms and Computational Experiments challenge (PACE) 2025 was devoted to engineer algorithms solving the Dominating Set problem as well as the Hitting Set problem. In contrast to the last iterations, these problems are (under standard assumptions) not fixed-parameter tractable (fpt) in general. However, restricting the structure of the input (e.g. to planar graphs or degenerate graphs for Dominating Set, or to set systems with sets of bounded size for Hitting Set) renders these problems fpt. Following the spirit of the last iterations of the PACE challenge, there is an exact track and a heuristic track for each problem; each track coming with a benchmark set of 100 public instances and 100 private instances. Overall, the PACE 2025 had 71 participants from 25 teams, 13 countries, and 3 continents. In this report, we briefly describe the setup of the challenge, the selection of benchmark instances, as well as the ranking of the participating teams. We also briefly outline the approaches used in the submitted solvers.
Cite as

Mario Grobler and Sebastian Siebertz. The PACE 2025 Parameterized Algorithms and Computational Experiments Challenge: Dominating Set and Hitting Set. In 20th International Symposium on Parameterized and Exact Computation (IPEC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 358, pp. 32:1-32:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{grobler_et_al:LIPIcs.IPEC.2025.32,
  author =	{Grobler, Mario and Siebertz, Sebastian},
  title =	{{The PACE 2025 Parameterized Algorithms and Computational Experiments Challenge: Dominating Set and Hitting Set}},
  booktitle =	{20th International Symposium on Parameterized and Exact Computation (IPEC 2025)},
  pages =	{32:1--32:17},
  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.32},
  URN =		{urn:nbn:de:0030-drops-251644},
  doi =		{10.4230/LIPIcs.IPEC.2025.32},
  annote =	{Keywords: PACE 2025 Report, Dominating Set, Hitting Set, Algorithm Engineering, FPT, Heuristics}
}
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.DISC.2025.10
Amnesiac Flooding: Easy to Break, Hard to Escape

Authors: Henry Austin, Maximilien Gadouleau, George B. Mertzios, and Amitabh Trehan

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract
Broadcast is a central problem in distributed computing. Recently, Hussak and Trehan [PODC'19/ STACS'20/DC'23] proposed a stateless broadcasting protocol (Amnesiac Flooding), which was surprisingly proven to terminate in asymptotically optimal time (linear in the diameter of the network). However, it remains unclear: (i) Are there other stateless terminating broadcast algorithms with the desirable properties of Amnesiac Flooding, (ii) How robust is Amnesiac Flooding with respect to faults? In this paper we make progress on both of these fronts. Under a reasonable restriction (obliviousness to message content) additional to the fault-free synchronous model, we prove that Amnesiac Flooding is the only strictly stateless deterministic protocol that can achieve terminating broadcast. We achieve this by identifying four natural properties of a terminating broadcast protocol that Amnesiac Flooding uniquely satisfies. In contrast, we prove that even minor relaxations of any of these four criteria allow the construction of other terminating broadcast protocols. On the other hand, we prove that Amnesiac Flooding can become non-terminating or non-broadcasting, even if we allow just one node to drop a single message on a single edge in a single round. As a tool for proving this, we focus on the set of all configurations of transmissions between nodes in the network, and obtain a dichotomy characterizing the configurations, starting from which, Amnesiac Flooding terminates. Additionally, we characterise the structure of sets of Byzantine agents capable of forcing non-termination or non-broadcast of the protocol on arbitrary networks.
Cite as

Henry Austin, Maximilien Gadouleau, George B. Mertzios, and Amitabh Trehan. Amnesiac Flooding: Easy to Break, Hard to Escape. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 10:1-10:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{austin_et_al:LIPIcs.DISC.2025.10,
  author =	{Austin, Henry and Gadouleau, Maximilien and Mertzios, George B. and Trehan, Amitabh},
  title =	{{Amnesiac Flooding: Easy to Break, Hard to Escape}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{10:1--10:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.10},
  URN =		{urn:nbn:de:0030-drops-248273},
  doi =		{10.4230/LIPIcs.DISC.2025.10},
  annote =	{Keywords: Amnesiac flooding, Terminating protocol, Algorithm state, Stateless protocol, Flooding algorithm, Network algorithms, Graph theory, Termination, Communication, Broadcast}
}
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.TQC.2025.6
Quantum SAT Problems with Finite Sets of Projectors Are Complete for a Plethora of Classes

Authors: Ricardo Rivera Cardoso, Alex Meiburg, and Daniel Nagaj

Published in: LIPIcs, Volume 350, 20th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2025)

Abstract
Previously, all known variants of the Quantum Satisfiability (QSAT) problem - consisting of determining whether a k-local (k-body) Hamiltonian is frustration-free - could be classified as being either in 𝖯; or complete for NP, MA, or QMA₁. Here, we present new qubit variants of this problem that are complete for BQP₁, coRP, QCMA, PI(coRP,NP), PI(BQP₁,NP), PI(BQP₁,MA), SoPU(coRP,NP), SoPU(BQP₁,NP), and SoPU(BQP₁,MA). Our result implies that a complete classification of quantum constraint satisfaction problems (QCSPs), analogous to Schaefer’s dichotomy theorem for classical CSPs, must either include these 13 classes, or otherwise show that some are equal. Additionally, our result showcases two new types of QSAT problems that can be decided efficiently, as well as the first nontrivial BQP₁-complete problem. We first construct QSAT problems on qudits that are complete for BQP₁, coRP, and QCMA. These are made by restricting the finite set of Hamiltonians to consist of elements similar to H_{init}, H_{prop}, and H_{out}, seen in the circuit-to-Hamiltonian transformation. Usually, these are used to demonstrate hardness of QSAT and Local Hamiltonian problems, and so our proofs of hardness are simple. The difficulty lies in ensuring that all Hamiltonians generated with these three elements can be decided in their respective classes. For this, we build our Hamiltonian terms with high-dimensional data and clock qudits, ternary logic, and either monogamy of entanglement or specific clock encodings. We then show how to express these problems in terms of qubits, by proving that any QCSP can be reduced to a qubit problem while maintaining the same complexity - something not believed possible classically. The remaining six problems are obtained by considering "sums" and "products" of some of the QSAT problems mentioned here. Before this work, the QSAT problems generated in this way resulted in complete problems for PI and SoPU classes that were trivially equal to NP, MA, or QMA₁. We thus commence the study of these new and seemingly nontrivial classes. While [Meiburg, 2021] first sought to prove completeness for coRP, BQP₁, and QCMA, we note that those constructions are flawed. Here, we rework them, provide correct proofs, and obtain improvements on the required qudit dimensionality.
Cite as

Ricardo Rivera Cardoso, Alex Meiburg, and Daniel Nagaj. Quantum SAT Problems with Finite Sets of Projectors Are Complete for a Plethora of Classes. In 20th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 350, pp. 6:1-6:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{riveracardoso_et_al:LIPIcs.TQC.2025.6,
  author =	{Rivera Cardoso, Ricardo and Meiburg, Alex and Nagaj, Daniel},
  title =	{{Quantum SAT Problems with Finite Sets of Projectors Are Complete for a Plethora of Classes}},
  booktitle =	{20th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2025)},
  pages =	{6:1--6:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-392-8},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{350},
  editor =	{Fefferman, Bill},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2025.6},
  URN =		{urn:nbn:de:0030-drops-240557},
  doi =		{10.4230/LIPIcs.TQC.2025.6},
  annote =	{Keywords: Quantum complexity theory, quantum satisfiability, circuit-to-Hamiltonian, pairwise union of classes, pairwise intersection of classes}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2025.74
Subcoloring of (Unit) Disk Graphs

Authors: Malory Marin and Rémi Watrigant

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

Abstract
A subcoloring of a graph is a partition of its vertex set into subsets (called colors), each inducing a disjoint union of cliques. It is a natural generalization of the classical proper coloring, in which each color must instead induce an independent set. Similarly to proper coloring, we define the subchromatic number of a graph as the minimum integer k such that it admits a subcoloring with k colors, and the corresponding problem k-Subcoloring which asks whether a graph has subchromatic number at most k. In this paper, we initiate the study of the subcoloring of (unit) disk graphs. One motivation stems from the fact that disk graphs can be seen as a dense generalization of planar graphs where, intuitively, each vertex can be blown into a large clique-much like subcoloring generalizes proper coloring. Interestingly, it can be observed that every unit disk graph admits a subcoloring with at most 7 colors. We first prove that the subchromatic number can be 3-approximated in polynomial-time in unit disk graphs. We then present several hardness results for special cases of unit disk graphs which somehow prevents the use of classical approaches for improving this result. We show in particular that 2-Subcoloring remains NP-hard in triangle-free unit disk graphs, as well as in unit disk graphs representable within a strip of bounded height. We also solve an open question of Broersma, Fomin, Nešetřil, and Woeginger (2002) by proving that 3-Subcoloring remains NP-hard in co-comparability graphs (which contain unit disk graphs representable within a strip of height √3/2). Finally, we prove that every n-vertex disk graph admits a subcoloring with at most O(log³(n)) colors and present a O(log²(n))-approximation algorithm for computing the subchromatic number of such graphs. This is achieved by defining a decomposition and a special type of co-comparability disk graph, called Δ-disk graphs, which might be of independent interest.
Cite as

Malory Marin and Rémi Watrigant. Subcoloring of (Unit) Disk Graphs. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 74:1-74:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{marin_et_al:LIPIcs.MFCS.2025.74,
  author =	{Marin, Malory and Watrigant, R\'{e}mi},
  title =	{{Subcoloring of (Unit) Disk Graphs}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{74:1--74:17},
  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.74},
  URN =		{urn:nbn:de:0030-drops-241811},
  doi =		{10.4230/LIPIcs.MFCS.2025.74},
  annote =	{Keywords: subcoloring, algorithms, disk graphs, unit disk graphs}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2025.16
Isometric-Universal Graphs for Trees

Authors: Edgar Baucher, François Dross, and Cyril Gavoille

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

Abstract
We consider the problem of finding the smallest graph that contains two input trees each with at most n vertices preserving their distances. In other words, we look for an isometric-universal graph with the minimum number of vertices for two given trees. We prove that this problem can be solved in time O(n^{5/2}log{n}). We extend this result to forests instead of trees, and propose an algorithm with running time O(n^{7/2}log{n}). As a key ingredient, we show that a smallest isometric-universal graph of two trees essentially is a tree. Furthermore, we prove that these results cannot be extended. Firstly, we show that deciding whether there exists an isometric-universal graph with t vertices for three forests is NP-complete. Secondly, we show that any smallest isometric-universal graph cannot be a tree for some families of three trees. This latter result has implications for greedy strategies solving the smallest isometric-universal graph problem.
Cite as

Edgar Baucher, François Dross, and Cyril Gavoille. Isometric-Universal Graphs for Trees. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 16:1-16:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{baucher_et_al:LIPIcs.MFCS.2025.16,
  author =	{Baucher, Edgar and Dross, Fran\c{c}ois and Gavoille, Cyril},
  title =	{{Isometric-Universal Graphs for Trees}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{16:1--16:16},
  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.16},
  URN =		{urn:nbn:de:0030-drops-241237},
  doi =		{10.4230/LIPIcs.MFCS.2025.16},
  annote =	{Keywords: tree, forest, isometric subgraph, universal graph, distance-preserving}
}
  • Refine by Type
  • 32 Document/PDF
  • 20 Document/HTML
  • 1 Artifact

  • Refine by Publication Year
  • 5 2026
  • 17 2025
  • 2 2024
  • 1 2023
  • 1 2021
  • Show More...

  • Refine by Author
  • 9 Sikora, Florian
  • 4 Bonnet, Édouard
  • 3 Kim, Eun Jung
  • 2 Ardévol Martínez, Virginia
  • 2 Bousquet, Nicolas
  • Show More...

  • Refine by Series/Journal
  • 31 LIPIcs
  • 1 DagMan

  • Refine by Classification
  • 10 Theory of computation → Graph algorithms analysis
  • 8 Theory of computation → Parameterized complexity and exact algorithms
  • 5 Theory of computation → Design and analysis of algorithms
  • 4 Mathematics of computing → Graph algorithms
  • 4 Theory of computation → Fixed parameter tractability
  • Show More...

  • Refine by Keyword
  • 3 Parameterized Complexity
  • 3 parameterized complexity
  • 2 Disk Graphs
  • 2 FPT
  • 2 Interval graphs
  • 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