3 Search Results for "Mc Inerney, Fionn"


Document
Sample Compression Schemes for Balls in Graphs

Authors: Jérémie Chalopin, Victor Chepoi, Fionn Mc Inerney, Sébastien Ratel, and Yann Vaxès

Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)


Abstract
One of the open problems in machine learning is whether any set-family of VC-dimension d admits a sample compression scheme of size O(d). In this paper, we study this problem for balls in graphs. For balls of arbitrary radius r, we design proper sample compression schemes of size 4 for interval graphs, of size 6 for trees of cycles, and of size 22 for cube-free median graphs. We also design approximate sample compression schemes of size 2 for balls of δ-hyperbolic graphs.

Cite as

Jérémie Chalopin, Victor Chepoi, Fionn Mc Inerney, Sébastien Ratel, and Yann Vaxès. Sample Compression Schemes for Balls in Graphs. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 31:1-31:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{chalopin_et_al:LIPIcs.MFCS.2022.31,
  author =	{Chalopin, J\'{e}r\'{e}mie and Chepoi, Victor and Mc Inerney, Fionn and Ratel, S\'{e}bastien and Vax\`{e}s, Yann},
  title =	{{Sample Compression Schemes for Balls in Graphs}},
  booktitle =	{47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
  pages =	{31:1--31:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-256-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{241},
  editor =	{Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.31},
  URN =		{urn:nbn:de:0030-drops-168298},
  doi =		{10.4230/LIPIcs.MFCS.2022.31},
  annote =	{Keywords: Proper Sample Compression Schemes, Balls, Graphs, VC-dimension}
}
Document
Metric Dimension Parameterized by Feedback Vertex Set and Other Structural Parameters

Authors: Esther Galby, Liana Khazaliya, Fionn Mc Inerney, Roohani Sharma, and Prafullkumar Tale

Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)


Abstract
For a graph G, a subset S ⊆ V(G) is called a resolving set if for any two vertices u,v ∈ V(G), there exists a vertex w ∈ S such that d(w,u) ≠ d(w,v). The Metric Dimension problem takes as input a graph G and a positive integer k, and asks whether there exists a resolving set of size at most k. This problem was introduced in the 1970s and is known to be NP-hard [GT 61 in Garey and Johnson’s book]. In the realm of parameterized complexity, Hartung and Nichterlein [CCC 2013] proved that the problem is W[2]-hard when parameterized by the natural parameter k. They also observed that it is FPT when parameterized by the vertex cover number and asked about its complexity under smaller parameters, in particular the feedback vertex set number. We answer this question by proving that Metric Dimension is W[1]-hard when parameterized by the feedback vertex set number. This also improves the result of Bonnet and Purohit [IPEC 2019] which states that the problem is W[1]-hard parameterized by the treewidth. Regarding the parameterization by the vertex cover number, we prove that Metric Dimension does not admit a polynomial kernel under this parameterization unless NP ⊆ coNP/poly. We observe that a similar result holds when the parameter is the distance to clique. On the positive side, we show that Metric Dimension is FPT when parameterized by either the distance to cluster or the distance to co-cluster, both of which are smaller parameters than the vertex cover number.

Cite as

Esther Galby, Liana Khazaliya, Fionn Mc Inerney, Roohani Sharma, and Prafullkumar Tale. Metric Dimension Parameterized by Feedback Vertex Set and Other Structural Parameters. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 51:1-51:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{galby_et_al:LIPIcs.MFCS.2022.51,
  author =	{Galby, Esther and Khazaliya, Liana and Mc Inerney, Fionn and Sharma, Roohani and Tale, Prafullkumar},
  title =	{{Metric Dimension Parameterized by Feedback Vertex Set and Other Structural Parameters}},
  booktitle =	{47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
  pages =	{51:1--51:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-256-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{241},
  editor =	{Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.51},
  URN =		{urn:nbn:de:0030-drops-168496},
  doi =		{10.4230/LIPIcs.MFCS.2022.51},
  annote =	{Keywords: Metric Dimension, Parameterized Complexity, Feedback Vertex Set}
}
Document
Study of a Combinatorial Game in Graphs Through Linear Programming

Authors: Nathann Cohen, Fionn Mc Inerney, Nicolas Nisse, and Stéphane Pérennes

Published in: LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017)


Abstract
In the Spy Game played on a graph G, a single spy travels the ertices of G at speed s, while multiple slow guards strive to have, at all times, one of them within distance d of that spy. In order to determine the smallest number of guards necessary for this task, we analyze the game through a Linear Programming formulation and the fractional strategies it yields for the guards. We then show the equivalence of fractional and integral strategies in trees. This allows us to design a polynomial-time algorithm for computing an optimal strategy in this class of graphs. Using duality in Linear Programming, we also provide non-trivial bounds on the fractional guardnumber of grids and torus. We believe that the approach using fractional relaxation and Linear Programming is promising to obtain new results in the field of combinatorial games.

Cite as

Nathann Cohen, Fionn Mc Inerney, Nicolas Nisse, and Stéphane Pérennes. Study of a Combinatorial Game in Graphs Through Linear Programming. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 22:1-22:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@InProceedings{cohen_et_al:LIPIcs.ISAAC.2017.22,
  author =	{Cohen, Nathann and Mc Inerney, Fionn and Nisse, Nicolas and P\'{e}rennes, St\'{e}phane},
  title =	{{Study of a Combinatorial Game in Graphs Through Linear Programming}},
  booktitle =	{28th International Symposium on Algorithms and Computation (ISAAC 2017)},
  pages =	{22:1--22:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-054-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{92},
  editor =	{Okamoto, Yoshio and Tokuyama, Takeshi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.22},
  URN =		{urn:nbn:de:0030-drops-82254},
  doi =		{10.4230/LIPIcs.ISAAC.2017.22},
  annote =	{Keywords: Turn-by-turn games in graphs, Graph algorithms, Linear Programming}
}
  • Refine by Author
  • 3 Mc Inerney, Fionn
  • 1 Chalopin, Jérémie
  • 1 Chepoi, Victor
  • 1 Cohen, Nathann
  • 1 Galby, Esther
  • Show More...

  • Refine by Classification
  • 1 Mathematics of computing → Graph algorithms
  • 1 Theory of computation → Machine learning theory
  • 1 Theory of computation → Parameterized complexity and exact algorithms

  • Refine by Keyword
  • 1 Balls
  • 1 Feedback Vertex Set
  • 1 Graph algorithms
  • 1 Graphs
  • 1 Linear Programming
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 2 2022
  • 1 2017

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