Search Results

Documents authored by Barbero, Florian

Document
DOI: 10.4230/LIPIcs.IPEC.2018.10
On the Distance Identifying Set Meta-Problem and Applications to the Complexity of Identifying Problems on Graphs

Authors: Florian Barbero, Lucas Isenmann, and Jocelyn Thiebaut

Published in: LIPIcs, Volume 115, 13th International Symposium on Parameterized and Exact Computation (IPEC 2018)

Abstract
Numerous problems consisting in identifying vertices in graphs using distances are useful in domains such as network verification and graph isomorphism. Unifying them into a meta-problem may be of main interest. We introduce here a promising solution named Distance Identifying Set. The model contains Identifying Code (IC), Locating Dominating Set (LD) and their generalizations r-IC and r-LD where the closed neighborhood is considered up to distance r. It also contains Metric Dimension (MD) and its refinement r-MD in which the distance between two vertices is considered as infinite if the real distance exceeds r. Note that while IC = 1-IC and LD = 1-LD, we have MD = infty-MD; we say that MD is not local. In this article, we prove computational lower bounds for several problems included in Distance Identifying Set by providing generic reductions from (Planar) Hitting Set to the meta-problem. We focus on two families of problem from the meta-problem: the first one, called bipartite gifted local, contains r-IC, r-LD and r-MD for each positive integer r while the second one, called 1-layered, contains LD, MD and r-MD for each positive integer r. We have: - the 1-layered problems are NP-hard even in bipartite apex graphs, - the bipartite gifted local problems are NP-hard even in bipartite planar graphs, - assuming ETH, all these problems cannot be solved in 2^{o(sqrt{n})} when restricted to bipartite planar or apex graph, respectively, and they cannot be solved in 2^{o(n)} on bipartite graphs, - even restricted to bipartite graphs, they do not admit parameterized algorithms in 2^{O(k)} * n^{O(1)} except if W[0] = W[2]. Here k is the solution size of a relevant identifying set. In particular, Metric Dimension cannot be solved in 2^{o(n)} under ETH, answering a question of Hartung in [Sepp Hartung and André Nichterlein, 2013].
Cite as

Florian Barbero, Lucas Isenmann, and Jocelyn Thiebaut. On the Distance Identifying Set Meta-Problem and Applications to the Complexity of Identifying Problems on Graphs. In 13th International Symposium on Parameterized and Exact Computation (IPEC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 115, pp. 10:1-10:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{barbero_et_al:LIPIcs.IPEC.2018.10,
  author =	{Barbero, Florian and Isenmann, Lucas and Thiebaut, Jocelyn},
  title =	{{On the Distance Identifying Set Meta-Problem and Applications to the Complexity of Identifying Problems on Graphs}},
  booktitle =	{13th International Symposium on Parameterized and Exact Computation (IPEC 2018)},
  pages =	{10:1--10:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-084-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{115},
  editor =	{Paul, Christophe and Pilipczuk, Michal},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2018.10},
  URN =		{urn:nbn:de:0030-drops-102114},
  doi =		{10.4230/LIPIcs.IPEC.2018.10},
  annote =	{Keywords: identifying code, resolving set, metric dimension, distance identifying set, parameterized complexity, W-hierarchy, meta-problem, hitting set}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2017.70
Exploring the Complexity of Layout Parameters in Tournaments and Semi-Complete Digraphs

Authors: Florian Barbero, Christophe Paul, and Michal Pilipczuk

Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

Abstract
A simple digraph is semi-complete if for any two of its vertices u and v, at least one of the arcs (u,v) and (v,u) is present. We study the complexity of computing two layout parameters of semi-complete digraphs: cutwidth and optimal linear arrangement (OLA). We prove that: -Both parameters are NP-hard to compute and the known exact and parameterized algorithms for them have essentially optimal running times, assuming the Exponential Time Hypothesis. - The cutwidth parameter admits a quadratic Turing kernel, whereas it does not admit any polynomial kernel unless coNP/poly contains NP. By contrast, OLA admits a linear kernel. These results essentially complete the complexity analysis of computing cutwidth and OLA on semi-complete digraphs. Our techniques can be also used to analyze the sizes of minimal obstructions for having small cutwidth under the induced subdigraph relation.
Cite as

Florian Barbero, Christophe Paul, and Michal Pilipczuk. Exploring the Complexity of Layout Parameters in Tournaments and Semi-Complete Digraphs. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 70:1-70:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{barbero_et_al:LIPIcs.ICALP.2017.70,
  author =	{Barbero, Florian and Paul, Christophe and Pilipczuk, Michal},
  title =	{{Exploring the Complexity of Layout Parameters in Tournaments and Semi-Complete Digraphs}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{70:1--70:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.70},
  URN =		{urn:nbn:de:0030-drops-74537},
  doi =		{10.4230/LIPIcs.ICALP.2017.70},
  annote =	{Keywords: cutwidth, OLA, tournament, semi-complete digraph}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2015.43
Parameterized and Approximation Algorithms for the Load Coloring Problem

Authors: Florian Barbero, Gregory Gutin, Mark Jones, and Bin Sheng

Published in: LIPIcs, Volume 43, 10th International Symposium on Parameterized and Exact Computation (IPEC 2015)

Abstract
Let c, k be two positive integers. Given a graph G=(V,E), the c-Load Coloring problem asks whether there is a c-coloring varphi: V => [c] such that for every i in [c], there are at least k edges with both endvertices colored i. Gutin and Jones (IPL 2014) studied this problem with c=2. They showed 2-Load Coloring to be fixed-parameter tractable (FPT) with parameter k by obtaining a kernel with at most 7k vertices. In this paper, we extend the study to any fixed c by giving both a linear-vertex and a linear-edge kernel. In the particular case of c=2, we obtain a kernel with less than 4k vertices and less than 8k edges. These results imply that for any fixed c >= 2, c-Load Coloring is FPT and the optimization version of c-Load Coloring (where k is to be maximized) has an approximation algorithm with a constant ratio.
Cite as

Florian Barbero, Gregory Gutin, Mark Jones, and Bin Sheng. Parameterized and Approximation Algorithms for the Load Coloring Problem. In 10th International Symposium on Parameterized and Exact Computation (IPEC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 43, pp. 43-54, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{barbero_et_al:LIPIcs.IPEC.2015.43,
  author =	{Barbero, Florian and Gutin, Gregory and Jones, Mark and Sheng, Bin},
  title =	{{Parameterized and Approximation Algorithms for the Load Coloring Problem}},
  booktitle =	{10th International Symposium on Parameterized and Exact Computation (IPEC 2015)},
  pages =	{43--54},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-92-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{43},
  editor =	{Husfeldt, Thore and Kanj, Iyad},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2015.43},
  URN =		{urn:nbn:de:0030-drops-55703},
  doi =		{10.4230/LIPIcs.IPEC.2015.43},
  annote =	{Keywords: Load Coloring, fixed-parameter tractability, kernelization}
}
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 About DROPS Imprint Privacy Contact