Document

**Published in:** LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)

A tournament is a directed graph in which there is a single arc between every pair of distinct vertices. Given a tournament T on n vertices, we explore the classical and parameterized complexity of the problems of determining if T has a cycle packing (a set of pairwise arc-disjoint cycles) of size k and a triangle packing (a set of pairwise arc-disjoint triangles) of size k. We refer to these problems as Arc-disjoint Cycles in Tournaments (ACT) and Arc-disjoint Triangles in Tournaments (ATT), respectively. Although the maximization version of ACT can be seen as the linear programming dual of the well-studied problem of finding a minimum feedback arc set (a set of arcs whose deletion results in an acyclic graph) in tournaments, surprisingly no algorithmic results seem to exist for ACT. We first show that ACT and ATT are both NP-complete. Then, we show that the problem of determining if a tournament has a cycle packing and a feedback arc set of the same size is NP-complete. Next, we prove that ACT and ATT are fixed-parameter tractable, they can be solved in 2^{O(k log k)} n^{O(1)} time and 2^{O(k)} n^{O(1)} time respectively. Moreover, they both admit a kernel with O(k) vertices. We also prove that ACT and ATT cannot be solved in 2^{o(sqrt{k})} n^{O(1)} time under the Exponential-Time Hypothesis.

Stéphane Bessy, Marin Bougeret, R. Krithika, Abhishek Sahu, Saket Saurabh, Jocelyn Thiebaut, and Meirav Zehavi. Packing Arc-Disjoint Cycles in Tournaments. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 27:1-27:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{bessy_et_al:LIPIcs.MFCS.2019.27, author = {Bessy, St\'{e}phane and Bougeret, Marin and Krithika, R. and Sahu, Abhishek and Saurabh, Saket and Thiebaut, Jocelyn and Zehavi, Meirav}, title = {{Packing Arc-Disjoint Cycles in Tournaments}}, booktitle = {44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)}, pages = {27:1--27:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-117-7}, ISSN = {1868-8969}, year = {2019}, volume = {138}, editor = {Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.27}, URN = {urn:nbn:de:0030-drops-109714}, doi = {10.4230/LIPIcs.MFCS.2019.27}, annote = {Keywords: arc-disjoint cycle packing, tournaments, parameterized algorithms, kernelization} }

Document

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

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].

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

**Published in:** LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017)

Given a tournament T and a positive integer k, the C_3-Packing-T asks if there exists a least k (vertex-)disjoint directed 3-cycles in T. This is the dual problem in tournaments of the classical minimal feedback vertex set problem. Surprisingly C_3-Packing-T did not receive a lot of attention in the literature. We show that it does not admit a PTAS unless P=NP, even if we restrict the considered instances to sparse tournaments, that is tournaments with a feedback arc set (FAS) being a matching. Focusing on sparse tournaments we provide a (1+6/(c-1)) approximation algorithm for sparse tournaments having a linear representation where all the backward arcs have "length" at least c. Concerning kernelization, we show that C_3-Packing-T admits a kernel with O(m) vertices, where m is the size of a given feedback arc set. In particular, we derive a O(k) vertices kernel for C_3-Packing-T when restricted to sparse instances. On the negative size, we show that C_3-Packing-T does not admit a kernel of (total bit) size O(k^{2-epsilon}) unless NP is a subset of coNP / Poly. The existence of a kernel in O(k) vertices for C_3-Packing-T remains an open question.

Stéphane Bessy, Marin Bougeret, and Jocelyn Thiebaut. Triangle Packing in (Sparse) Tournaments: Approximation and Kernelization. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 14:1-14:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{bessy_et_al:LIPIcs.ESA.2017.14, author = {Bessy, St\'{e}phane and Bougeret, Marin and Thiebaut, Jocelyn}, title = {{Triangle Packing in (Sparse) Tournaments: Approximation and Kernelization}}, booktitle = {25th Annual European Symposium on Algorithms (ESA 2017)}, pages = {14:1--14:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-049-1}, ISSN = {1868-8969}, year = {2017}, volume = {87}, editor = {Pruhs, Kirk and Sohler, Christian}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.14}, URN = {urn:nbn:de:0030-drops-78622}, doi = {10.4230/LIPIcs.ESA.2017.14}, annote = {Keywords: Tournament Triangle packing, Feedback arc set, Approximation algorithms, Parameterized algorithms} }

X

Feedback for Dagstuhl Publishing

Feedback submitted

Please try again later or send an E-mail