4 Search Results for "Vialette, Stéphane"

Document
DOI: 10.4230/LIPIcs.ISAAC.2023.8
Recognizing Unit Multiple Intervals Is Hard

Authors: Virginia Ardévol Martínez, Romeo Rizzi, Florian Sikora, and Stéphane Vialette

Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)

Abstract
Multiple interval graphs are a well-known generalization of interval graphs introduced in the 1970s to deal with situations arising naturally in scheduling and allocation. A d-interval is the union of d intervals on the real line, and a graph is a d-interval graph if it is the intersection graph of d-intervals. In particular, it is a unit d-interval graph if it admits a d-interval representation where every interval has unit length. Whereas it has been known for a long time that recognizing 2-interval graphs and other related classes such as 2-track interval graphs is NP-complete, the complexity of recognizing unit 2-interval graphs remains open. Here, we settle this question by proving that the recognition of unit 2-interval graphs is also NP-complete. Our proof technique uses a completely different approach from the other hardness results of recognizing related classes. Furthermore, we extend the result for unit d-interval graphs for any d ⩾ 2, which does not follow directly in graph recognition problems -as an example, it took almost 20 years to close the gap between d = 2 and d > 2 for the recognition of d-track interval graphs. Our result has several implications, including that recognizing (x, …, x) d-interval graphs and depth r unit 2-interval graphs is NP-complete for every x ⩾ 11 and every r ⩾ 4.
Cite as

Virginia Ardévol Martínez, Romeo Rizzi, Florian Sikora, and Stéphane Vialette. Recognizing Unit Multiple Intervals Is Hard. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 8:1-8:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{ardevolmartinez_et_al:LIPIcs.ISAAC.2023.8,
  author =	{Ard\'{e}vol Mart{\'\i}nez, Virginia and Rizzi, Romeo and Sikora, Florian and Vialette, St\'{e}phane},
  title =	{{Recognizing Unit Multiple Intervals Is Hard}},
  booktitle =	{34th International Symposium on Algorithms and Computation (ISAAC 2023)},
  pages =	{8:1--8:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-289-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{283},
  editor =	{Iwata, Satoru and Kakimura, Naonori},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.8},
  URN =		{urn:nbn:de:0030-drops-193102},
  doi =		{10.4230/LIPIcs.ISAAC.2023.8},
  annote =	{Keywords: Interval graphs, unit multiple interval graphs, recognition, NP-hardness}
}
Document
DOI: 10.4230/LIPIcs.CPM.2022.21
Permutation Pattern Matching for Doubly Partially Ordered Patterns

Authors: Laurent Bulteau, Guillaume Fertin, Vincent Jugé, and Stéphane Vialette

Published in: LIPIcs, Volume 223, 33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022)

Abstract
We study in this paper the Doubly Partially Ordered Pattern Matching (or DPOP Matching) problem, a natural extension of the Permutation Pattern Matching problem. Permutation Pattern Matching takes as input two permutations σ and π, and asks whether there exists an occurrence of σ in π; whereas DPOP Matching takes two partial orders P_v and P_p defined on the same set X and a permutation π, and asks whether there exist |X| elements in π whose values (resp., positions) are in accordance with P_v (resp., P_p). Posets P_v and P_p aim at relaxing the conditions formerly imposed by the permutation σ, since σ yields a total order on both positions and values. Our problem being NP-hard in general (as Permutation Pattern Matching is), we consider restrictions on several parameters/properties of the input, e.g., bounding the size of the pattern, assuming symmetry of the posets (i.e., P_v and P_p are identical), assuming that one partial order is a total (resp., weak) order, bounding the length of the longest chain/anti-chain in the posets, or forbidding specific patterns in π. For each such restriction, we provide results which together give a(n almost) complete landscape for the algorithmic complexity of the problem.
Cite as

Laurent Bulteau, Guillaume Fertin, Vincent Jugé, and Stéphane Vialette. Permutation Pattern Matching for Doubly Partially Ordered Patterns. In 33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 223, pp. 21:1-21:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bulteau_et_al:LIPIcs.CPM.2022.21,
  author =	{Bulteau, Laurent and Fertin, Guillaume and Jug\'{e}, Vincent and Vialette, St\'{e}phane},
  title =	{{Permutation Pattern Matching for Doubly Partially Ordered Patterns}},
  booktitle =	{33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022)},
  pages =	{21:1--21:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-234-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{223},
  editor =	{Bannai, Hideo and Holub, Jan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2022.21},
  URN =		{urn:nbn:de:0030-drops-161481},
  doi =		{10.4230/LIPIcs.CPM.2022.21},
  annote =	{Keywords: Partial orders, Permutations, Pattern Matching, Algorithmic Complexity, Parameterized Complexity}
}
Document
DOI: 10.4230/LIPIcs.CPM.2021.11
Disorders and Permutations

Authors: Laurent Bulteau, Samuele Giraudo, and Stéphane Vialette

Published in: LIPIcs, Volume 191, 32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021)

Abstract
The additive x-disorder of a permutation is the sum of the absolute differences of all pairs of consecutive elements. We show that the additive x-disorder of a permutation of S(n), n ≥ 2, ranges from n-1 to ⌊n²/2⌋ - 1, and we give a complete characterization of permutations having extreme such values. Moreover, for any positive integers n and d such that n ≥ 2 and n-1 ≤ d ≤ ⌊n²/2⌋ - 1, we propose a linear-time algorithm to compute a permutation π ∈ S(n) with additive x-disorder d.
Cite as

Laurent Bulteau, Samuele Giraudo, and Stéphane Vialette. Disorders and Permutations. In 32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 191, pp. 11:1-11:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{bulteau_et_al:LIPIcs.CPM.2021.11,
  author =	{Bulteau, Laurent and Giraudo, Samuele and Vialette, St\'{e}phane},
  title =	{{Disorders and Permutations}},
  booktitle =	{32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021)},
  pages =	{11:1--11:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-186-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{191},
  editor =	{Gawrychowski, Pawe{\l} and Starikovskaya, Tatiana},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2021.11},
  URN =		{urn:nbn:de:0030-drops-139628},
  doi =		{10.4230/LIPIcs.CPM.2021.11},
  annote =	{Keywords: Permutation, Algorithm}
}
Document
DOI: 10.4230/LIPIcs.CPM.2019.20
Finding a Small Number of Colourful Components

Authors: Laurent Bulteau, Konrad K. Dabrowski, Guillaume Fertin, Matthew Johnson, Daniël Paulusma, and Stéphane Vialette

Published in: LIPIcs, Volume 128, 30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019)

Abstract
A partition (V_1,...,V_k) of the vertex set of a graph G with a (not necessarily proper) colouring c is colourful if no two vertices in any V_i have the same colour and every set V_i induces a connected graph. The Colourful Partition problem, introduced by Adamaszek and Popa, is to decide whether a coloured graph (G,c) has a colourful partition of size at most k. This problem is related to the Colourful Components problem, introduced by He, Liu and Zhao, which is to decide whether a graph can be modified into a graph whose connected components form a colourful partition by deleting at most p edges. Despite the similarities in their definitions, we show that Colourful Partition and Colourful Components may have different complexities for restricted instances. We tighten known NP-hardness results for both problems by closing a number of complexity gaps. In addition, we prove new hardness and tractability results for Colourful Partition. In particular, we prove that deciding whether a coloured graph (G,c) has a colourful partition of size 2 is NP-complete for coloured planar bipartite graphs of maximum degree 3 and path-width 3, but polynomial-time solvable for coloured graphs of treewidth 2. Rather than performing an ad hoc study, we use our classical complexity results to guide us in undertaking a thorough parameterized study of Colourful Partition. We show that this leads to suitable parameters for obtaining FPT results and moreover prove that Colourful Components and Colourful Partition may have different parameterized complexities, depending on the chosen parameter.
Cite as

Laurent Bulteau, Konrad K. Dabrowski, Guillaume Fertin, Matthew Johnson, Daniël Paulusma, and Stéphane Vialette. Finding a Small Number of Colourful Components. In 30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 128, pp. 20:1-20:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{bulteau_et_al:LIPIcs.CPM.2019.20,
  author =	{Bulteau, Laurent and Dabrowski, Konrad K. and Fertin, Guillaume and Johnson, Matthew and Paulusma, Dani\"{e}l and Vialette, St\'{e}phane},
  title =	{{Finding a Small Number of Colourful Components}},
  booktitle =	{30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019)},
  pages =	{20:1--20:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-103-0},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{128},
  editor =	{Pisanti, Nadia and P. Pissis, Solon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2019.20},
  URN =		{urn:nbn:de:0030-drops-104914},
  doi =		{10.4230/LIPIcs.CPM.2019.20},
  annote =	{Keywords: Colourful component, colourful partition, tree, treewidth, vertex cover}
}
  • Refine by Author
  • 4 Vialette, Stéphane
  • 3 Bulteau, Laurent
  • 2 Fertin, Guillaume
  • 1 Ardévol Martínez, Virginia
  • 1 Dabrowski, Konrad K.
  • Show More...

  • Refine by Classification
  • 2 Mathematics of computing → Graph theory
  • 1 Mathematics of computing → Permutations and combinations
  • 1 Theory of computation → Design and analysis of algorithms
  • 1 Theory of computation → Problems, reductions and completeness

  • Refine by Keyword
  • 1 Algorithm
  • 1 Algorithmic Complexity
  • 1 Colourful component
  • 1 Interval graphs
  • 1 NP-hardness
  • Show More...

  • Refine by Type
  • 4 document

  • Refine by Publication Year
  • 1 2019
  • 1 2021
  • 1 2022
  • 1 2023

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-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact