DROPS

Document

DOI: 10.4230/LIPIcs.MFCS.2021.23

Reconfiguring Independent Sets on Interval Graphs

Authors: Marcin Briański, Stefan Felsner, Jędrzej Hodor, and Piotr Micek

Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)

Abstract

We study reconfiguration of independent sets in interval graphs under the token sliding rule. We show that if two independent sets of size k are reconfigurable in an n-vertex interval graph, then there is a reconfiguration sequence of length 𝒪(k⋅ n²). We also provide a construction in which the shortest reconfiguration sequence is of length Ω(k²⋅ n). As a counterpart to these results, we also establish that Independent Set Reconfiguration is PSPACE-hard on incomparability graphs, of which interval graphs are a special case.

Cite as

Marcin Briański, Stefan Felsner, Jędrzej Hodor, and Piotr Micek. Reconfiguring Independent Sets on Interval Graphs. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 23:1-23:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{brianski_et_al:LIPIcs.MFCS.2021.23,
  author =	{Bria\'{n}ski, Marcin and Felsner, Stefan and Hodor, J\k{e}drzej and Micek, Piotr},
  title =	{{Reconfiguring Independent Sets on Interval Graphs}},
  booktitle =	{46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
  pages =	{23:1--23:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-201-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{202},
  editor =	{Bonchi, Filippo and Puglisi, Simon J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.23},
  URN =		{urn:nbn:de:0030-drops-144633},
  doi =		{10.4230/LIPIcs.MFCS.2021.23},
  annote =	{Keywords: reconfiguration, independent sets, interval graphs}
}

Document

DOI: 10.4230/LIPIcs.SOCG.2015.630

On-line Coloring between Two Lines

Authors: Stefan Felsner, Piotr Micek, and Torsten Ueckerdt

Published in: LIPIcs, Volume 34, 31st International Symposium on Computational Geometry (SoCG 2015)

Abstract

We study on-line colorings of certain graphs given as intersection graphs of objects "between two lines", i.e., there is a pair of horizontal lines such that each object of the representation is a connected set contained in the strip between the lines and touches both. Some of the graph classes admitting such a representation are permutation graphs (segments), interval graphs (axis-aligned rectangles), trapezoid graphs (trapezoids) and cocomparability graphs (simple curves). We present an on-line algorithm coloring graphs given by convex sets between two lines that uses O(w^3) colors on graphs with maximum clique size w. In contrast intersection graphs of segments attached to a single line may force any on-line coloring algorithm to use an arbitrary number of colors even when w=2. The left-of relation makes the complement of intersection graphs of objects between two lines into a poset. As an aside we discuss the relation of the class C of posets obtained from convex sets between two lines with some other classes of posets: all 2-dimensional posets and all posets of height 2 are in C but there is a 3-dimensional poset of height 3 that does not belong to C. We also show that the on-line coloring problem for curves between two lines is as hard as the on-line chain partition problem for arbitrary posets.

Cite as

Stefan Felsner, Piotr Micek, and Torsten Ueckerdt. On-line Coloring between Two Lines. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 630-641, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{felsner_et_al:LIPIcs.SOCG.2015.630,
  author =	{Felsner, Stefan and Micek, Piotr and Ueckerdt, Torsten},
  title =	{{On-line Coloring between Two Lines}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{630--641},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-83-5},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{34},
  editor =	{Arge, Lars and Pach, J\'{a}nos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.630},
  URN =		{urn:nbn:de:0030-drops-50915},
  doi =		{10.4230/LIPIcs.SOCG.2015.630},
  annote =	{Keywords: intersection graphs, cocomparability graphs, on-line coloring}
}

Search Results

Documents authored by Micek, Piotr

Reconfiguring Independent Sets on Interval Graphs

Abstract

Cite as

On-line Coloring between Two Lines

Abstract

Cite as

Thanks for your feedback!

Could not send message