7 Search Results for "Stephan, Simon"


Document
Maximum Independent Set When Excluding an Induced Minor: K₁ + tK₂ and tC₃ ⊎ C₄

Authors: Édouard Bonnet, Julien Duron, Colin Geniet, Stéphan Thomassé, and Alexandra Wesolek

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


Abstract
Dallard, Milanič, and Štorgel [arXiv '22] ask if, for every class excluding a fixed planar graph H as an induced minor, Maximum Independent Set can be solved in polynomial time, and show that this is indeed the case when H is any planar complete bipartite graph, or the 5-vertex clique minus one edge, or minus two disjoint edges. A positive answer would constitute a far-reaching generalization of the state-of-the-art, when we currently do not know if a polynomial-time algorithm exists when H is the 7-vertex path. Relaxing tractability to the existence of a quasipolynomial-time algorithm, we know substantially more. Indeed, quasipolynomial-time algorithms were recently obtained for the t-vertex cycle, C_t [Gartland et al., STOC '21], and the disjoint union of t triangles, tC₃ [Bonamy et al., SODA '23]. We give, for every integer t, a polynomial-time algorithm running in n^O(t⁵) when H is the friendship graph K₁ + tK₂ (t disjoint edges plus a vertex fully adjacent to them), and a quasipolynomial-time algorithm running in n^{O(t² log n) + f(t)}, with f a single-exponential function, when H is tC₃ ⊎ C₄ (the disjoint union of t triangles and a 4-vertex cycle). The former generalizes the algorithm readily obtained from Alekseev’s structural result on graphs excluding tK₂ as an induced subgraph [Alekseev, DAM '07], while the latter extends Bonamy et al.’s result.

Cite as

Édouard Bonnet, Julien Duron, Colin Geniet, Stéphan Thomassé, and Alexandra Wesolek. Maximum Independent Set When Excluding an Induced Minor: K₁ + tK₂ and tC₃ ⊎ C₄. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 23:1-23:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{bonnet_et_al:LIPIcs.ESA.2023.23,
  author =	{Bonnet, \'{E}douard and Duron, Julien and Geniet, Colin and Thomass\'{e}, St\'{e}phan and Wesolek, Alexandra},
  title =	{{Maximum Independent Set When Excluding an Induced Minor: K₁ + tK₂ and tC₃ ⊎ C₄}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{23:1--23:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.23},
  URN =		{urn:nbn:de:0030-drops-186769},
  doi =		{10.4230/LIPIcs.ESA.2023.23},
  annote =	{Keywords: Maximum Independent Set, forbidden induced minors, quasipolynomial-time algorithms}
}
Document
Lossy Kernelization for (Implicit) Hitting Set Problems

Authors: Fedor V. Fomin, Tien-Nam Le, Daniel Lokshtanov, Saket Saurabh, Stéphan Thomassé, and Meirav Zehavi

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


Abstract
We re-visit the complexity of polynomial time pre-processing (kernelization) for the d-Hitting Set problem. This is one of the most classic problems in Parameterized Complexity by itself, and, furthermore, it encompasses several other of the most well-studied problems in this field, such as Vertex Cover, Feedback Vertex Set in Tournaments (FVST) and Cluster Vertex Deletion (CVD). In fact, d-Hitting Set encompasses any deletion problem to a hereditary property that can be characterized by a finite set of forbidden induced subgraphs. With respect to bit size, the kernelization complexity of d-Hitting Set is essentially settled: there exists a kernel with 𝒪(k^d) bits (𝒪(k^d) sets and 𝒪(k^{d-1}) elements) and this it tight by the result of Dell and van Melkebeek [STOC 2010, JACM 2014]. Still, the question of whether there exists a kernel for d-Hitting Set with fewer elements has remained one of the most major open problems in Kernelization. In this paper, we first show that if we allow the kernelization to be lossy with a qualitatively better loss than the best possible approximation ratio of polynomial time approximation algorithms, then one can obtain kernels where the number of elements is linear for every fixed d. Further, based on this, we present our main result: we show that there exist approximate Turing kernelizations for d-Hitting Set that even beat the established bit-size lower bounds for exact kernelizations - in fact, we use a constant number of oracle calls, each with "near linear" (𝒪(k^{1+ε})) bit size, that is, almost the best one could hope for. Lastly, for two special cases of implicit 3-Hitting set, namely, FVST and CVD, we obtain the "best of both worlds" type of results - (1+ε)-approximate kernelizations with a linear number of vertices. In terms of size, this substantially improves the exact kernels of Fomin et al. [SODA 2018, TALG 2019], with simpler arguments.

Cite as

Fedor V. Fomin, Tien-Nam Le, Daniel Lokshtanov, Saket Saurabh, Stéphan Thomassé, and Meirav Zehavi. Lossy Kernelization for (Implicit) Hitting Set Problems. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 49:1-49:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{fomin_et_al:LIPIcs.ESA.2023.49,
  author =	{Fomin, Fedor V. and Le, Tien-Nam and Lokshtanov, Daniel and Saurabh, Saket and Thomass\'{e}, St\'{e}phan and Zehavi, Meirav},
  title =	{{Lossy Kernelization for (Implicit) Hitting Set Problems}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{49:1--49:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.49},
  URN =		{urn:nbn:de:0030-drops-187020},
  doi =		{10.4230/LIPIcs.ESA.2023.49},
  annote =	{Keywords: Hitting Set, Lossy Kernelization}
}
Document
First Order Logic and Twin-Width in Tournaments

Authors: Colin Geniet and Stéphan Thomassé

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


Abstract
We characterise the classes of tournaments with tractable first-order model checking. For every hereditary class of tournaments T, first-order model checking either is fixed parameter tractable, or is AW[*]-hard. This dichotomy coincides with the fact that T has either bounded or unbounded twin-width, and that the growth of T is either at most exponential or at least factorial. From the model-theoretic point of view, we show that NIP classes of tournaments coincide with bounded twin-width. Twin-width is also characterised by three infinite families of obstructions: T has bounded twin-width if and only if it excludes at least one tournament from each family. This generalises results of Bonnet et al. on ordered graphs. The key for these results is a polynomial time algorithm which takes as input a tournament T and computes a linear order < on V(T) such that the twin-width of the birelation (T, <) is at most some function of the twin-width of T. Since approximating twin-width can be done in FPT time for an ordered structure (T, <), this provides a FPT approximation of twin-width for tournaments.

Cite as

Colin Geniet and Stéphan Thomassé. First Order Logic and Twin-Width in Tournaments. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 53:1-53:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{geniet_et_al:LIPIcs.ESA.2023.53,
  author =	{Geniet, Colin and Thomass\'{e}, St\'{e}phan},
  title =	{{First Order Logic and Twin-Width in Tournaments}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{53:1--53:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.53},
  URN =		{urn:nbn:de:0030-drops-187061},
  doi =		{10.4230/LIPIcs.ESA.2023.53},
  annote =	{Keywords: Tournaments, twin-width, first-order logic, model checking, NIP, small classes}
}
Document
Empirical Evidence for Concepts of Spatial Information as Cognitive Means for Interpreting and Using Maps

Authors: Enkhbold Nyamsuren, Eric J. Top, Haiqi Xu, Niels Steenbergen, and Simon Scheider

Published in: LIPIcs, Volume 240, 15th International Conference on Spatial Information Theory (COSIT 2022)


Abstract
Due to the increasing prevalence and relevance of geo-spatial data in the age of data science, Geographic Information Systems are enjoying wider interdisciplinary adoption by communities outside of GIScience. However, properly interpreting and analysing geo-spatial information is not a trivial task due to knowledge barriers. There is a need for a trans-disciplinary framework for sharing specialized geographical knowledge and expertise to overcome these barriers. The core concepts of spatial information were proposed as such a conceptual framework. These concepts, such as object and field, were proposed as cognitive lenses that can simplify understanding of and guide the processing of spatial information. However, there is a distinct lack of empirical evidence for the existence of such concepts in the human mind or whether such concepts can be indeed useful. In this study, we have explored for such empirical evidence using behavioral experiments with human participants. The experiment adopted a contrast model to investigate whether the participants can semantically distinguish between the object and field core concepts visualized as maps. The statistically significant positive results offer evidence supporting the existence of the two concepts or cognitive concepts closely resembling them. This gives credibility to the core concepts of spatial information as tools for sharing, teaching, or even automating the process of geographical information processing.

Cite as

Enkhbold Nyamsuren, Eric J. Top, Haiqi Xu, Niels Steenbergen, and Simon Scheider. Empirical Evidence for Concepts of Spatial Information as Cognitive Means for Interpreting and Using Maps. In 15th International Conference on Spatial Information Theory (COSIT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 240, pp. 7:1-7:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{nyamsuren_et_al:LIPIcs.COSIT.2022.7,
  author =	{Nyamsuren, Enkhbold and Top, Eric J. and Xu, Haiqi and Steenbergen, Niels and Scheider, Simon},
  title =	{{Empirical Evidence for Concepts of Spatial Information as Cognitive Means for Interpreting and Using Maps}},
  booktitle =	{15th International Conference on Spatial Information Theory (COSIT 2022)},
  pages =	{7:1--7:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-257-0},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{240},
  editor =	{Ishikawa, Toru and Fabrikant, Sara Irina and Winter, Stephan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.COSIT.2022.7},
  URN =		{urn:nbn:de:0030-drops-168926},
  doi =		{10.4230/LIPIcs.COSIT.2022.7},
  annote =	{Keywords: core concepts, cognition, map interpretation, spatial analysis}
}
Document
Short Paper
Transcepts: Connecting Entity Representations Across Conceptual Views on Spatial Information (Short Paper)

Authors: Eric J. Top and Simon Scheider

Published in: LIPIcs, Volume 240, 15th International Conference on Spatial Information Theory (COSIT 2022)


Abstract
Analysts interpret geographic and other spatial data to check the validity of methods in reaching an analytical goal. However, the meaning of data is elusive. The same data may constitute one concept in one view and another concept in another. For example, the same set of air pollution points may be regarded as field values if they are considered pollution measurements and objects if they are considered locations of measurement devices. In this work we adopt a framework of conceptual spaces and viewpoints and show how entity representations in one semantic interpretation may be related to entity representations in others in terms of what we call transcepts. A transcept captures which things represent the same entity. We define and use transcepts in the framework to explain how different views of geographic data may relate to one another.

Cite as

Eric J. Top and Simon Scheider. Transcepts: Connecting Entity Representations Across Conceptual Views on Spatial Information (Short Paper). In 15th International Conference on Spatial Information Theory (COSIT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 240, pp. 19:1-19:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{top_et_al:LIPIcs.COSIT.2022.19,
  author =	{Top, Eric J. and Scheider, Simon},
  title =	{{Transcepts: Connecting Entity Representations Across Conceptual Views on Spatial Information}},
  booktitle =	{15th International Conference on Spatial Information Theory (COSIT 2022)},
  pages =	{19:1--19:7},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-257-0},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{240},
  editor =	{Ishikawa, Toru and Fabrikant, Sara Irina and Winter, Stephan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.COSIT.2022.19},
  URN =		{urn:nbn:de:0030-drops-169048},
  doi =		{10.4230/LIPIcs.COSIT.2022.19},
  annote =	{Keywords: Transcept, Spatial Information, Knowledge Representation, Conceptual Space, View, Point Of View, Viewpoint, Object, Event, Network, Field, Relation}
}
Document
Molecular Simulation Study on the Influence of the Scratching Velocity on Nanoscopic Contact Processes

Authors: Sebastian Schmitt, Simon Stephan, Benjamin Kirsch, Jan C. Aurich, Eberhard Kerscher, Herbert M. Urbassek, and Hans Hasse

Published in: OASIcs, Volume 89, 2nd International Conference of the DFG International Research Training Group 2057 – Physical Modeling for Virtual Manufacturing (iPMVM 2020)


Abstract
The influence of the scratching velocity on mechanical and thermal properties of a nanoscopic contact process was studied by molecular dynamics simulations. Simulations with different scratching velocities were conducted in dry and lubricated systems. The contact process consisted of a lateral scratching of a spherical indenter on a planar substrate. All molecular interactions were described by the Lennard-Jones truncated and shifted potential. The forces on the indenter, the coefficient of friction and the work done by the indenter as well as the power applied on the indenter were sampled. Furthermore, an analysis of thermal properties was conducted: The change of the energy of the substrate, the indenter and the fluid was evaluated and the local temperature field was determined. The forces, the coefficient of friction and the work done by the indenter show practically no influence of the scratching velocity. The work done by the indenter was found to be the same for all velocities. As a consequence, the power supplied to the system depends linearly on the scratching velocity, which affects the temperature of the contact zone. As expected, the presence of a lubricant reduces the temperature of the substrate in the vicinity of the contact.

Cite as

Sebastian Schmitt, Simon Stephan, Benjamin Kirsch, Jan C. Aurich, Eberhard Kerscher, Herbert M. Urbassek, and Hans Hasse. Molecular Simulation Study on the Influence of the Scratching Velocity on Nanoscopic Contact Processes. In 2nd International Conference of the DFG International Research Training Group 2057 – Physical Modeling for Virtual Manufacturing (iPMVM 2020). Open Access Series in Informatics (OASIcs), Volume 89, pp. 17:1-17:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{schmitt_et_al:OASIcs.iPMVM.2020.17,
  author =	{Schmitt, Sebastian and Stephan, Simon and Kirsch, Benjamin and Aurich, Jan C. and Kerscher, Eberhard and Urbassek, Herbert M. and Hasse, Hans},
  title =	{{Molecular Simulation Study on the Influence of the Scratching Velocity on Nanoscopic Contact Processes}},
  booktitle =	{2nd International Conference of the DFG International Research Training Group 2057 – Physical Modeling for Virtual Manufacturing (iPMVM 2020)},
  pages =	{17:1--17:16},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-183-2},
  ISSN =	{2190-6807},
  year =	{2021},
  volume =	{89},
  editor =	{Garth, Christoph and Aurich, Jan C. and Linke, Barbara and M\"{u}ller, Ralf and Ravani, Bahram and Weber, Gunther H. and Kirsch, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.iPMVM.2020.17},
  URN =		{urn:nbn:de:0030-drops-137669},
  doi =		{10.4230/OASIcs.iPMVM.2020.17},
  annote =	{Keywords: Nanotribology, Friction, Scratching, Lubrication, Lennard-Jones Potential}
}
Document
A Unified Approach to Boundedness Properties in MSO

Authors: Lukasz Kaiser, Martin Lang, Simon Leßenich, and Christof Löding

Published in: LIPIcs, Volume 41, 24th EACSL Annual Conference on Computer Science Logic (CSL 2015)


Abstract
In the past years, extensions of monadic second-order logic (MSO) that can specify boundedness properties by the use of operators referring to the sizes of sets have been considered. In particular, the logics costMSO introduced by T. Colcombet and MSO+U by M. Bojanczyk were analyzed and connections to automaton models have been established to obtain decision procedures for these logics. In this work, we propose the logic quantitative counting MSO (qcMSO for short), which combines aspects from both costMSO and MSO+U. We show that both logics can be embedded into qcMSO in a natural way. Moreover, we provide a decidability proof for the theory of its weak variant (quantification only over finite sets) for the natural numbers with order and the infinite binary tree. These decidability results are obtained using a regular cost function extension of automatic structures called resource-automatic structures.

Cite as

Lukasz Kaiser, Martin Lang, Simon Leßenich, and Christof Löding. A Unified Approach to Boundedness Properties in MSO. In 24th EACSL Annual Conference on Computer Science Logic (CSL 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 41, pp. 441-456, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)


Copy BibTex To Clipboard

@InProceedings{kaiser_et_al:LIPIcs.CSL.2015.441,
  author =	{Kaiser, Lukasz and Lang, Martin and Le{\ss}enich, Simon and L\"{o}ding, Christof},
  title =	{{A Unified Approach to Boundedness Properties in MSO}},
  booktitle =	{24th EACSL Annual Conference on Computer Science Logic (CSL 2015)},
  pages =	{441--456},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-90-3},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{41},
  editor =	{Kreutzer, Stephan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2015.441},
  URN =		{urn:nbn:de:0030-drops-54309},
  doi =		{10.4230/LIPIcs.CSL.2015.441},
  annote =	{Keywords: quantitative logics, monadic second order logic, boundedness, automatic structures, tree automata}
}
  • Refine by Author
  • 3 Thomassé, Stéphan
  • 2 Geniet, Colin
  • 2 Scheider, Simon
  • 2 Top, Eric J.
  • 1 Aurich, Jan C.
  • Show More...

  • Refine by Classification
  • 1 Applied computing → Physical sciences and engineering
  • 1 Computing methodologies → Knowledge representation and reasoning
  • 1 Computing methodologies → Spatial and physical reasoning
  • 1 General and reference → Empirical studies
  • 1 Information systems → Geographic information systems
  • Show More...

  • Refine by Keyword
  • 1 Conceptual Space
  • 1 Event
  • 1 Field
  • 1 Friction
  • 1 Hitting Set
  • Show More...

  • Refine by Type
  • 7 document

  • Refine by Publication Year
  • 3 2023
  • 2 2022
  • 1 2015
  • 1 2021

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