156 Search Results for "Bodlaender, Hans L."

Volume

LIPIcs, Volume 294

19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)

SWAT 2024, June 12-14, 2024, Helsinki, Finland

Editors: Hans L. Bodlaender

Volume

LIPIcs, Volume 83

42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)

MFCS 2017, August 21-25, 2017, Aalborg, Denmark

Editors: Kim G. Larsen, Hans L. Bodlaender, and Jean-Francois Raskin

Document
DOI: 10.4230/LIPIcs.ISAAC.2024.47
Complexity Framework for Forbidden Subgraphs II: Edge Subdivision and the "H"-Graphs

Authors: Vadim Lozin, Barnaby Martin, Sukanya Pandey, Daniël Paulusma, Mark Siggers, Siani Smith, and Erik Jan van Leeuwen

Published in: LIPIcs, Volume 322, 35th International Symposium on Algorithms and Computation (ISAAC 2024)

Abstract
For a fixed set H of graphs, a graph G is H-subgraph-free if G does not contain any H ∈ H as a (not necessarily induced) subgraph. A recent framework gives a complete classification on H-subgraph-free graphs (for finite sets H) for problems that are solvable in polynomial time on graph classes of bounded treewidth, NP-complete on subcubic graphs, and whose NP-hardness is preserved under edge subdivision. While a lot of problems satisfy these conditions, there are also many problems that do not satisfy all three conditions and for which the complexity in H-subgraph-free graphs is unknown. We study problems for which only the first two conditions of the framework hold (they are solvable in polynomial time on classes of bounded treewidth and NP-complete on subcubic graphs, but NP-hardness is not preserved under edge subdivision). In particular, we make inroads into the classification of the complexity of four such problems: Hamilton Cycle, k-Induced Disjoint Paths, C₅-Colouring and Star 3-Colouring. Although we do not complete the classifications, we show that the boundary between polynomial time and NP-complete differs among our problems and also from problems that do satisfy all three conditions of the framework, in particular when we forbid certain subdivisions of the "H"-graph (the graph that looks like the letter "H"). Hence, we exhibit a rich complexity landscape among problems for H-subgraph-free graph classes.
Cite as

Vadim Lozin, Barnaby Martin, Sukanya Pandey, Daniël Paulusma, Mark Siggers, Siani Smith, and Erik Jan van Leeuwen. Complexity Framework for Forbidden Subgraphs II: Edge Subdivision and the "H"-Graphs. In 35th International Symposium on Algorithms and Computation (ISAAC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 322, pp. 47:1-47:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{lozin_et_al:LIPIcs.ISAAC.2024.47,
  author =	{Lozin, Vadim and Martin, Barnaby and Pandey, Sukanya and Paulusma, Dani\"{e}l and Siggers, Mark and Smith, Siani and van Leeuwen, Erik Jan},
  title =	{{Complexity Framework for Forbidden Subgraphs II: Edge Subdivision and the "H"-Graphs}},
  booktitle =	{35th International Symposium on Algorithms and Computation (ISAAC 2024)},
  pages =	{47:1--47:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-354-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{322},
  editor =	{Mestre, Juli\'{a}n and Wirth, Anthony},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2024.47},
  URN =		{urn:nbn:de:0030-drops-221747},
  doi =		{10.4230/LIPIcs.ISAAC.2024.47},
  annote =	{Keywords: forbidden subgraph, complexity dichotomy, edge subdivision, treewidth}
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2024.135
A Finite Presentation of Graphs of Treewidth at Most Three

Authors: Amina Doumane, Samuel Humeau, and Damien Pous

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

Abstract
We provide a finite equational presentation of graphs of treewidth at most three, solving an instance of an open problem by Courcelle and Engelfriet. We use a syntax generalising series-parallel expressions, denoting graphs with a small interface. We introduce appropriate notions of connectivity for such graphs (components, cutvertices, separation pairs). We use those concepts to analyse the structure of graphs of treewidth at most three, showing how they can be decomposed recursively, first canonically into connected parallel components, and then non-deterministically. The main difficulty consists in showing that all non-deterministic choices can be related using only finitely many equational axioms.
Cite as

Amina Doumane, Samuel Humeau, and Damien Pous. A Finite Presentation of Graphs of Treewidth at Most Three. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 135:1-135:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{doumane_et_al:LIPIcs.ICALP.2024.135,
  author =	{Doumane, Amina and Humeau, Samuel and Pous, Damien},
  title =	{{A Finite Presentation of Graphs of Treewidth at Most Three}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{135:1--135:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.135},
  URN =		{urn:nbn:de:0030-drops-202787},
  doi =		{10.4230/LIPIcs.ICALP.2024.135},
  annote =	{Keywords: Graphs, treewidth, connectedness, axiomatisation, series-parallel expressions}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.SWAT.2024
LIPIcs, Volume 294, SWAT 2024, Complete Volume

Authors: Hans L. Bodlaender

Published in: LIPIcs, Volume 294, 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)

Abstract
LIPIcs, Volume 294, SWAT 2024, Complete Volume
Cite as

19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 294, pp. 1-686, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@Proceedings{bodlaender:LIPIcs.SWAT.2024,
  title =	{{LIPIcs, Volume 294, SWAT 2024, Complete Volume}},
  booktitle =	{19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)},
  pages =	{1--686},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-318-8},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{294},
  editor =	{Bodlaender, Hans L.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2024},
  URN =		{urn:nbn:de:0030-drops-200397},
  doi =		{10.4230/LIPIcs.SWAT.2024},
  annote =	{Keywords: LIPIcs, Volume 294, SWAT 2024, Complete Volume}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.SWAT.2024.0
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Hans L. Bodlaender

Published in: LIPIcs, Volume 294, 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)

Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as

19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 294, pp. 0:i-0:xvi, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bodlaender:LIPIcs.SWAT.2024.0,
  author =	{Bodlaender, Hans L.},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)},
  pages =	{0:i--0:xvi},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-318-8},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{294},
  editor =	{Bodlaender, Hans L.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2024.0},
  URN =		{urn:nbn:de:0030-drops-200400},
  doi =		{10.4230/LIPIcs.SWAT.2024.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2024.1
Eliminating Crossings in Ordered Graphs

Authors: Akanksha Agrawal, Sergio Cabello, Michael Kaufmann, Saket Saurabh, Roohani Sharma, Yushi Uno, and Alexander Wolff

Published in: LIPIcs, Volume 294, 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)

Abstract
Drawing a graph in the plane with as few crossings as possible is one of the central problems in graph drawing and computational geometry. Another option is to remove the smallest number of vertices or edges such that the remaining graph can be drawn without crossings. We study both problems in a book-embedding setting for ordered graphs, that is, graphs with a fixed vertex order. In this setting, the vertices lie on a straight line, called the spine, in the given order, and each edge must be drawn on one of several pages of a book such that every edge has at most a fixed number of crossings. In book embeddings, there is another way to reduce or avoid crossings; namely by using more pages. The minimum number of pages needed to draw an ordered graph without any crossings is its (fixed-vertex-order) page number. We show that the page number of an ordered graph with n vertices and m edges can be computed in 2^m ⋅ n^𝒪(1) time. An 𝒪(log n)-approximation of this number can be computed efficiently. We can decide in 2^𝒪(d √k log (d+k)) ⋅ n^𝒪(1) time whether it suffices to delete k edges of an ordered graph to obtain a d-planar layout (where every edge crosses at most d other edges) on one page. As an additional parameter, we consider the size h of a hitting set, that is, a set of points on the spine such that every edge, seen as an open interval, contains at least one of the points. For h = 1, we can efficiently compute the minimum number of edges whose deletion yields fixed-vertex-order page number p. For h > 1, we give an XP algorithm with respect to h+p. Finally, we consider spine+t-track drawings, where some but not all vertices lie on the spine. The vertex order on the spine is given; we must map every vertex that does not lie on the spine to one of t tracks, each of which is a straight line on a separate page, parallel to the spine. In this setting, we can minimize in 2ⁿ ⋅ n^𝒪(1) time either the number of crossings or, if we disallow crossings, the number of tracks.
Cite as

Akanksha Agrawal, Sergio Cabello, Michael Kaufmann, Saket Saurabh, Roohani Sharma, Yushi Uno, and Alexander Wolff. Eliminating Crossings in Ordered Graphs. In 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 294, pp. 1:1-1:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{agrawal_et_al:LIPIcs.SWAT.2024.1,
  author =	{Agrawal, Akanksha and Cabello, Sergio and Kaufmann, Michael and Saurabh, Saket and Sharma, Roohani and Uno, Yushi and Wolff, Alexander},
  title =	{{Eliminating Crossings in Ordered Graphs}},
  booktitle =	{19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)},
  pages =	{1:1--1:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-318-8},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{294},
  editor =	{Bodlaender, Hans L.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2024.1},
  URN =		{urn:nbn:de:0030-drops-200417},
  doi =		{10.4230/LIPIcs.SWAT.2024.1},
  annote =	{Keywords: Ordered graphs, book embedding, edge deletion, d-planar, hitting set}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2024.2
Local Spanners Revisited

Authors: Stav Ashur and Sariel Har-Peled

Published in: LIPIcs, Volume 294, 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)

Abstract
For a set P ⊆ ℝ² of points and a family ℱ of regions, a local t-spanner of P is a sparse graph G over P, such that for any region r ∈ ℱ the subgraph restricted to r, denoted by G ∩ r, is a t-spanner for all the points of r ∩ P. We present algorithms for the construction of local spanners with respect to several families of regions such as homothets of a convex region. Unfortunately, the number of edges in the resulting graph depends logarithmically on the spread of the input point set. We prove that this dependency cannot be removed, thus settling an open problem raised by Abam and Borouny. We also show improved constructions (with no dependency on the spread) of local spanners for fat triangles, and regular k-gons. In particular, this improves over the known construction for axis-parallel squares. We also study notions of weaker local spanners where one is allowed to shrink the region a "bit". Surprisingly, we show a near linear-size construction of a weak spanner for axis-parallel rectangles, where the shrinkage is multiplicative. Any spanner is a weak local spanner if the shrinking is proportional to the diameter of the region.
Cite as

Stav Ashur and Sariel Har-Peled. Local Spanners Revisited. In 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 294, pp. 2:1-2:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{ashur_et_al:LIPIcs.SWAT.2024.2,
  author =	{Ashur, Stav and Har-Peled, Sariel},
  title =	{{Local Spanners Revisited}},
  booktitle =	{19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)},
  pages =	{2:1--2:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-318-8},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{294},
  editor =	{Bodlaender, Hans L.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2024.2},
  URN =		{urn:nbn:de:0030-drops-200420},
  doi =		{10.4230/LIPIcs.SWAT.2024.2},
  annote =	{Keywords: Geometric graphs, Fault-tolerant spanners}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2024.3
Pairwise Rearrangement is Fixed-Parameter Tractable in the Single Cut-and-Join Model

Authors: Lora Bailey, Heather Smith Blake, Garner Cochran, Nathan Fox, Michael Levet, Reem Mahmoud, Inne Singgih, Grace Stadnyk, and Alexander Wiedemann

Published in: LIPIcs, Volume 294, 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)

Abstract
Genome rearrangement is a common model for molecular evolution. In this paper, we consider the Pairwise Rearrangement problem, which takes as input two genomes and asks for the number of minimum-length sequences of permissible operations transforming the first genome into the second. In the Single Cut-and-Join model (Bergeron, Medvedev, & Stoye, J. Comput. Biol. 2010), Pairwise Rearrangement is #P-complete (Bailey, et. al., COCOON 2023), which implies that exact sampling is intractable. In order to cope with this intractability, we investigate the parameterized complexity of this problem. We exhibit a fixed-parameter tractable algorithm with respect to the number of components in the adjacency graph that are not cycles of length 2 or paths of length 1. As a consequence, we obtain that Pairwise Rearrangement in the Single Cut-and-Join model is fixed-parameter tractable by distance. Our results suggest that the number of nontrivial components in the adjacency graph serves as the key obstacle for efficient sampling.
Cite as

Lora Bailey, Heather Smith Blake, Garner Cochran, Nathan Fox, Michael Levet, Reem Mahmoud, Inne Singgih, Grace Stadnyk, and Alexander Wiedemann. Pairwise Rearrangement is Fixed-Parameter Tractable in the Single Cut-and-Join Model. In 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 294, pp. 3:1-3:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bailey_et_al:LIPIcs.SWAT.2024.3,
  author =	{Bailey, Lora and Blake, Heather Smith and Cochran, Garner and Fox, Nathan and Levet, Michael and Mahmoud, Reem and Singgih, Inne and Stadnyk, Grace and Wiedemann, Alexander},
  title =	{{Pairwise Rearrangement is Fixed-Parameter Tractable in the Single Cut-and-Join Model}},
  booktitle =	{19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)},
  pages =	{3:1--3:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-318-8},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{294},
  editor =	{Bodlaender, Hans L.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2024.3},
  URN =		{urn:nbn:de:0030-drops-200436},
  doi =		{10.4230/LIPIcs.SWAT.2024.3},
  annote =	{Keywords: Genome Rearrangement, Phylogenetics, Single Cut-and-Join, Computational Complexity}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2024.4
Succinct Data Structure for Chordal Graphs with Bounded Vertex Leafage

Authors: Girish Balakrishnan, Sankardeep Chakraborty, N. S. Narayanaswamy, and Kunihiko Sadakane

Published in: LIPIcs, Volume 294, 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)

Abstract
Chordal graphs is a well-studied large graph class that is also a strict super-class of path graphs. Munro and Wu (ISAAC 2018) have given an (n²/4+o(n²))-bit succinct representation for n-vertex unlabeled chordal graphs. A chordal graph G = (V,E) is the intersection graph of sub-trees of a tree T. Based on this characterization, the two parameters of chordal graphs which we consider in this work are leafage, introduced by Lin, McKee and West (Discussiones Mathematicae Graph Theory 1998) and vertex leafage, introduced by Chaplick and Stacho (Discret. Appl. Math. 2014). Leafage is the minimum number of leaves in any possible tree T characterizing G. Let L(u) denote the number of leaves of the sub-tree in T corresponding to u ∈ V and k = max_{u ∈ V} L(u). The smallest k for which there exists a tree T for G is called its vertex leafage. In this work, we improve the worst-case information theoretic lower bound of Munro and Wu (ISAAC 2018) for n-vertex unlabeled chordal graphs when vertex leafage is bounded and leafage is unbounded. The class of unlabeled k-vertex leafage chordal graphs that consists of all chordal graphs with vertex leafage at most k and unbounded leafage, denoted 𝒢_k, is introduced for the first time. For k > 0 in o(n^c), c > 0, we obtain a lower bound of ((k-1)n log n -kn log k - O(log n))-bits on the size of any data structure that encodes a graph in 𝒢_k. Further, for every k-vertex leafage chordal graph G and k > 1 in o(n^c), c > 0, we present a ((k-1)n log n + o(kn log n))-bit succinct data structure, constructed using the succinct data structure for path graphs with (k-1)n vertices. Our data structure supports adjacency query in O(k log n) time and using additional 2n log n bits, an O(k² d_v log n + log² n) time neighbourhood query where d_v is degree of v ∈ V.
Cite as

Girish Balakrishnan, Sankardeep Chakraborty, N. S. Narayanaswamy, and Kunihiko Sadakane. Succinct Data Structure for Chordal Graphs with Bounded Vertex Leafage. In 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 294, pp. 4:1-4:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{balakrishnan_et_al:LIPIcs.SWAT.2024.4,
  author =	{Balakrishnan, Girish and Chakraborty, Sankardeep and Narayanaswamy, N. S. and Sadakane, Kunihiko},
  title =	{{Succinct Data Structure for Chordal Graphs with Bounded Vertex Leafage}},
  booktitle =	{19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)},
  pages =	{4:1--4:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-318-8},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{294},
  editor =	{Bodlaender, Hans L.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2024.4},
  URN =		{urn:nbn:de:0030-drops-200446},
  doi =		{10.4230/LIPIcs.SWAT.2024.4},
  annote =	{Keywords: succinct data structure, chordal graphs, leafage, vertex leafage, path graphs}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2024.5
Recognition and Proper Coloring of Unit Segment Intersection Graphs

Authors: Robert D. Barish and Tetsuo Shibuya

Published in: LIPIcs, Volume 294, 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)

Abstract
In this work, we concern ourselves with the fine-grained complexity of recognition and proper coloring problems on highly restricted classes of geometric intersection graphs of "thin" objects (i.e., objects with unbounded aspect ratios). As a point of motivation, we remark that there has been significant interest in finding algorithmic lower bounds for classic decision and optimization problems on these types of graphs, as they appear to escape the net of known planar or geometric separator theorems for "fat" objects (i.e., objects with bounded aspect ratios). In particular, letting n be the order of a geometric intersection graph, and assuming a geometric ply bound, per what is known as the "square root phenomenon", these separator theorems often imply the existence of 𝒪(2^√n) algorithms for problems ranging from finding proper colorings to finding Hamiltonian cycles. However, in contrast, it is known for instance that no 2^o(n) time algorithm can exist under the Exponential Time Hypothesis (ETH) for proper 6-coloring intersection graphs of line segments embedded in the plane (Biró et. al.; J. Comput. Geom. 9(2); pp. 47-80; 2018). We begin by establishing algorithmic lower bounds for proper k-coloring and recognition problems of intersection graphs of line segments embedded in the plane under the most stringent constraints possible that allow either problem to be non-trivial. In particular, we consider the class UNIT-PURE-k-DIR of unit segment geometric intersection graphs, in which segments are constrained to lie in at most k directions in the plane, and no two parallel segments are permitted to intersect. Here, under the ETH, we show for every k ≥ 3 that no 2^o(√{n/k}) time algorithm can exist for either recognizing or proper k-coloring UNIT-PURE-k-DIR graphs of order n. In addition, for every k ≥ 4, we establish the same algorithmic lower bound under the ETH for the problem of proper (k-1)-coloring UNIT-PURE-k-DIR graphs when provided a list of segment coordinates specified using 𝒪(n ⋅ k) bits witnessing graph class membership. As a consequence of our approach, we are also able to show that the problem of properly 3-coloring an arbitrary graph on m edges can be reduced in 𝒪(m²) time to the problem of properly (k-1)-coloring a UNIT-PURE-k-DIR graph. Finally, we consider a slightly less constrained class of geometric intersection graphs of lines (of unbounded length) in which line-line intersections must occur on any one of (r = 3) parallel planes in ℝ³. In this context, for every k ≥ 3, we show that no 2^o(n/k) time algorithm can exist for proper k-coloring these graphs unless the ETH is false.
Cite as

Robert D. Barish and Tetsuo Shibuya. Recognition and Proper Coloring of Unit Segment Intersection Graphs. In 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 294, pp. 5:1-5:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{barish_et_al:LIPIcs.SWAT.2024.5,
  author =	{Barish, Robert D. and Shibuya, Tetsuo},
  title =	{{Recognition and Proper Coloring of Unit Segment Intersection Graphs}},
  booktitle =	{19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)},
  pages =	{5:1--5:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-318-8},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{294},
  editor =	{Bodlaender, Hans L.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2024.5},
  URN =		{urn:nbn:de:0030-drops-200452},
  doi =		{10.4230/LIPIcs.SWAT.2024.5},
  annote =	{Keywords: graph class recognition, proper coloring, geometric intersection graph, segment intersection graph, fine-grained complexity, Exponential Time Hypothesis}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2024.6
Destroying Densest Subgraphs Is Hard

Authors: Cristina Bazgan, André Nichterlein, and Sofia Vazquez Alferez

Published in: LIPIcs, Volume 294, 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)

Abstract
We analyze the computational complexity of the following computational problems called Bounded-Density Edge Deletion and Bounded-Density Vertex Deletion: Given a graph G, a budget k and a target density τ_ρ, are there k edges (k vertices) whose removal from G results in a graph where the densest subgraph has density at most τ_ρ? Here, the density of a graph is the number of its edges divided by the number of its vertices. We prove that both problems are polynomial-time solvable on trees and cliques but are NP-complete on planar bipartite graphs and split graphs. From a parameterized point of view, we show that both problems are fixed-parameter tractable with respect to the vertex cover number but W[1]-hard with respect to the solution size. Furthermore, we prove that Bounded-Density Edge Deletion is W[1]-hard with respect to the feedback edge number, demonstrating that the problem remains hard on very sparse graphs.
Cite as

Cristina Bazgan, André Nichterlein, and Sofia Vazquez Alferez. Destroying Densest Subgraphs Is Hard. In 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 294, pp. 6:1-6:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bazgan_et_al:LIPIcs.SWAT.2024.6,
  author =	{Bazgan, Cristina and Nichterlein, Andr\'{e} and Vazquez Alferez, Sofia},
  title =	{{Destroying Densest Subgraphs Is Hard}},
  booktitle =	{19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)},
  pages =	{6:1--6:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-318-8},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{294},
  editor =	{Bodlaender, Hans L.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2024.6},
  URN =		{urn:nbn:de:0030-drops-200461},
  doi =		{10.4230/LIPIcs.SWAT.2024.6},
  annote =	{Keywords: Graph modification problems, NP-hardness, fixed-parameter tractability, W-hardness, special graph classes}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2024.7
The Simultaneous Interval Number: A New Width Parameter that Measures the Similarity to Interval Graphs

Authors: Jesse Beisegel, Nina Chiarelli, Ekkehard Köhler, Martin Milanič, Peter Muršič, and Robert Scheffler

Published in: LIPIcs, Volume 294, 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)

Abstract
We propose a novel way of generalizing the class of interval graphs, via a graph width parameter called simultaneous interval number. This parameter is related to the simultaneous representation problem for interval graphs and defined as the smallest number d of labels such that the graph admits a d-simultaneous interval representation, that is, an assignment of intervals and label sets to the vertices such that two vertices are adjacent if and only if the corresponding intervals, as well as their label sets, intersect. We show that this parameter is NP-hard to compute and give several bounds for the parameter, showing in particular that it is sandwiched between pathwidth and linear mim-width. For classes of graphs with bounded parameter values, assuming that the graph is equipped with a simultaneous interval representation with a constant number of labels, we give FPT algorithms for the clique, independent set, and dominating set problems, and hardness results for the independent dominating set and coloring problems. The FPT results for independent set and dominating set are for the simultaneous interval number plus solution size. In contrast, both problems are known to be 𝖶[1]-hard for linear mim-width plus solution size.
Cite as

Jesse Beisegel, Nina Chiarelli, Ekkehard Köhler, Martin Milanič, Peter Muršič, and Robert Scheffler. The Simultaneous Interval Number: A New Width Parameter that Measures the Similarity to Interval Graphs. In 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 294, pp. 7:1-7:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{beisegel_et_al:LIPIcs.SWAT.2024.7,
  author =	{Beisegel, Jesse and Chiarelli, Nina and K\"{o}hler, Ekkehard and Milani\v{c}, Martin and Mur\v{s}i\v{c}, Peter and Scheffler, Robert},
  title =	{{The Simultaneous Interval Number: A New Width Parameter that Measures the Similarity to Interval Graphs}},
  booktitle =	{19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)},
  pages =	{7:1--7:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-318-8},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{294},
  editor =	{Bodlaender, Hans L.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2024.7},
  URN =		{urn:nbn:de:0030-drops-200470},
  doi =		{10.4230/LIPIcs.SWAT.2024.7},
  annote =	{Keywords: Interval graph, simultaneous representation, width parameter, algorithm, parameterized complexity}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2024.8
Correlation Clustering with Vertex Splitting

Authors: Matthias Bentert, Alex Crane, Pål Grønås Drange, Felix Reidl, and Blair D. Sullivan

Published in: LIPIcs, Volume 294, 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)

Abstract
We explore CLUSTER EDITING and its generalization CORRELATION CLUSTERING with a new operation called permissive vertex splitting which addresses finding overlapping clusters in the face of uncertain information. We determine that both problems are NP-hard, yet they exhibit significant differences in terms of parameterized complexity and approximability. For CLUSTER EDITING WITH PERMISSIVE VERTEX SPLITTING, we show a polynomial kernel when parameterized by the solution size and develop a polynomial-time 7-approximation. In the case of CORRELATION CLUSTERING, we establish para-NP-hardness when parameterized by the solution size and demonstrate that computing an n^{1-ε}-approximation is NP-hard for any constant ε > 0. Additionally, we extend an established link between CORRELATION CLUSTERING and MULTICUT to the setting with permissive vertex splits.
Cite as

Matthias Bentert, Alex Crane, Pål Grønås Drange, Felix Reidl, and Blair D. Sullivan. Correlation Clustering with Vertex Splitting. In 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 294, pp. 8:1-8:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bentert_et_al:LIPIcs.SWAT.2024.8,
  author =	{Bentert, Matthias and Crane, Alex and Drange, P\r{a}l Gr{\o}n\r{a}s and Reidl, Felix and Sullivan, Blair D.},
  title =	{{Correlation Clustering with Vertex Splitting}},
  booktitle =	{19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)},
  pages =	{8:1--8:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-318-8},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{294},
  editor =	{Bodlaender, Hans L.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2024.8},
  URN =		{urn:nbn:de:0030-drops-200483},
  doi =		{10.4230/LIPIcs.SWAT.2024.8},
  annote =	{Keywords: graph modification, cluster editing, overlapping clustering, approximation, parameterized complexity}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2024.9
Daisy Bloom Filters

Authors: Ioana O. Bercea, Jakob Bæk Tejs Houen, and Rasmus Pagh

Published in: LIPIcs, Volume 294, 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)

Abstract
A filter is a widely used data structure for storing an approximation of a given set S of elements from some universe 𝒰 (a countable set). It represents a superset S' ⊇ S that is "close to S" in the sense that for x ∉ S, the probability that x ∈ S' is bounded by some ε > 0. The advantage of using a Bloom filter, when some false positives are acceptable, is that the space usage becomes smaller than what is required to store S exactly. Though filters are well-understood from a worst-case perspective, it is clear that state-of-the-art constructions may not be close to optimal for particular distributions of data and queries. Suppose, for instance, that some elements are in S with probability close to 1. Then it would make sense to always include them in S', saving space by not having to represent these elements in the filter. Questions like this have been raised in the context of Weighted Bloom filters (Bruck, Gao and Jiang, ISIT 2006) and Bloom filter implementations that make use of access to learned components (Vaidya, Knorr, Mitzenmacher, and Krask, ICLR 2021). In this paper, we present a lower bound for the expected space that such a filter requires. We also show that the lower bound is asymptotically tight by exhibiting a filter construction that executes queries and insertions in worst-case constant time, and has a false positive rate at most ε with high probability over input sets drawn from a product distribution. We also present a Bloom filter alternative, which we call the Daisy Bloom filter, that executes operations faster and uses significantly less space than the standard Bloom filter.
Cite as

Ioana O. Bercea, Jakob Bæk Tejs Houen, and Rasmus Pagh. Daisy Bloom Filters. In 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 294, pp. 9:1-9:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bercea_et_al:LIPIcs.SWAT.2024.9,
  author =	{Bercea, Ioana O. and Houen, Jakob B{\ae}k Tejs and Pagh, Rasmus},
  title =	{{Daisy Bloom Filters}},
  booktitle =	{19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)},
  pages =	{9:1--9:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-318-8},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{294},
  editor =	{Bodlaender, Hans L.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2024.9},
  URN =		{urn:nbn:de:0030-drops-200491},
  doi =		{10.4230/LIPIcs.SWAT.2024.9},
  annote =	{Keywords: Bloom filters, input distribution, learned data structures}
}
  • Refine by Author
  • 26 Bodlaender, Hans L.
  • 6 Groenland, Carla
  • 5 Pandey, Sukanya
  • 5 Paulusma, Daniël
  • 5 van Leeuwen, Erik Jan
  • Show More...

  • Refine by Classification

  • Refine by Keyword
  • 11 parameterized complexity
  • 7 treewidth
  • 5 Approximation Algorithms
  • 5 NP-completeness
  • 5 Treewidth
  • Show More...

  • Refine by Type
  • 154 document
  • 2 volume

  • Refine by Publication Year
  • 90 2017
  • 45 2024
  • 4 2022
  • 4 2023
  • 2 2011
  • Show More...

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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