Search Results

Documents authored by Bougeret, Marin

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.33
Kernelization Dichotomies for Hitting Subgraphs Under Structural Parameterizations

Authors: Marin Bougeret, Bart M. P. Jansen, and Ignasi Sau

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
For a fixed graph H, the H-Subgraph Hitting problem consists in deleting the minimum number of vertices from an input graph to obtain a graph without any occurrence of H as a subgraph. This problem can be seen as a generalization of Vertex Cover, which corresponds to the case H = K₂. We initiate a study of H-Subgraph Hitting from the point of view of characterizing structural parameterizations that allow for polynomial kernels, within the recently active framework of taking as the parameter the number of vertex deletions to obtain a graph in a "simple" class 𝒞. Our main contribution is to identify graph parameters that, when H-Subgraph Hitting is parameterized by the vertex-deletion distance to a class 𝒞 where any of these parameters is bounded, and assuming standard complexity assumptions and that H is biconnected, allow us to prove the following sharp dichotomy: the problem admits a polynomial kernel if and only if H is a clique. These new graph parameters are inspired by the notion of 𝒞-elimination distance introduced by Bulian and Dawar [Algorithmica 2016], and generalize it in two directions. Our results also apply to the version of the problem where one wants to hit H as an induced subgraph, and imply in particular, that the problems of hitting minors and hitting (induced) subgraphs have a substantially different behavior with respect to the existence of polynomial kernels under structural parameterizations.
Cite as

Marin Bougeret, Bart M. P. Jansen, and Ignasi Sau. Kernelization Dichotomies for Hitting Subgraphs Under Structural Parameterizations. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 33:1-33:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bougeret_et_al:LIPIcs.ICALP.2024.33,
  author =	{Bougeret, Marin and Jansen, Bart M. P. and Sau, Ignasi},
  title =	{{Kernelization Dichotomies for Hitting Subgraphs Under Structural Parameterizations}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{33:1--33:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.33},
  URN =		{urn:nbn:de:0030-drops-201766},
  doi =		{10.4230/LIPIcs.ICALP.2024.33},
  annote =	{Keywords: hitting subgraphs, hitting induced subgraphs, parameterized complexity, polynomial kernel, complexity dichotomy, elimination distance}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2024.11
Subexponential Algorithms in Geometric Graphs via the Subquadratic Grid Minor Property: The Role of Local Radius

Authors: Gaétan Berthe, Marin Bougeret, Daniel Gonçalves, and Jean-Florent Raymond

Published in: LIPIcs, Volume 294, 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)

Abstract
We investigate the existence in geometric graph classes of subexponential parameterized algorithms for cycle-hitting problems like Triangle Hitting (TH), Feedback Vertex Set (FVS) or Odd Cycle Transversal (OCT). These problems respectively ask for the existence in a graph G of a set X of at most k vertices such that G-X is triangle-free, acyclic, or bipartite. It is know that subexponential FPT algorithms of the form 2^o(k)n^𝒪(1) exist in planar and even H-minor free graphs from bidimensionality theory [Demaine et al. 2005], and there is a recent line of work lifting these results to geometric graph classes consisting of intersection of similarly sized "fat" objects ([Fomin et al. 2012], [Grigoriev et al. 2014], or disk graphs [Lokshtanov et al. 2022], [An et al. 2023]). In this paper we first identify sufficient conditions, for any graph class 𝒞 included in string graphs, to admit subexponential FPT algorithms for any problem in 𝒫, a family of bidimensional problems where one has to find a set of size at most k hitting a fixed family of graphs, containing in particular FVS. Informally, these conditions boil down to the fact that for any G ∈ 𝒞, the local radius of G (a new parameter introduced in [Lokshtanov et al. 2023]) is polynomial in the clique number of G and in the maximum matching in the neighborhood of a vertex. To demonstrate the applicability of this generic result, we bound the local radius for two special classes: intersection graphs of axis-parallel squares and of contact graphs of segments in the plane. This implies that any problem Π ∈ 𝒫 (in particular, FVS) can be solved in: - 2^𝒪(k^{3/4}log k) n^𝒪(1)-time in contact segment graphs, - 2^𝒪(k^{9/10}log k) n^𝒪(1) in intersection graphs of axis-parallel squares On the positive side, we also provide positive results for TH by solving it in: - 2^𝒪(k^{3/4}log k) n^𝒪(1)-time in contact segment graphs, - 2^𝒪(√dt²(log t)k^{2/3}log k) n^𝒪(1)-time in K_{t,t}-free d-DIR graphs (intersection of segments with d slopes) On the negative side, assuming the ETH we rule out the existence of algorithms solving: - TH and OCT in time 2^o(n) in 2-DIR graphs and more generally in time 2^o(√{Δn}) in 2-DIR graphs with maximum degree Δ, and - TH, FVS, and OCT in time 2^o(√n) in K_{2,2}-free contact-2-DIR graphs of maximum degree 6. Observe that together, these results show that the absence of large K_{t,t} is a necessary and sufficient condition for the existence of subexponential FPT algorithms for TH in 2-DIR.
Cite as

Gaétan Berthe, Marin Bougeret, Daniel Gonçalves, and Jean-Florent Raymond. Subexponential Algorithms in Geometric Graphs via the Subquadratic Grid Minor Property: The Role of Local Radius. In 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 294, pp. 11:1-11:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{berthe_et_al:LIPIcs.SWAT.2024.11,
  author =	{Berthe, Ga\'{e}tan and Bougeret, Marin and Gon\c{c}alves, Daniel and Raymond, Jean-Florent},
  title =	{{Subexponential Algorithms in Geometric Graphs via the Subquadratic Grid Minor Property: The Role of Local Radius}},
  booktitle =	{19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)},
  pages =	{11:1--11:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-318-8},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{294},
  editor =	{Bodlaender, Hans L.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2024.11},
  URN =		{urn:nbn:de:0030-drops-200519},
  doi =		{10.4230/LIPIcs.SWAT.2024.11},
  annote =	{Keywords: geometric intersection graphs, subexponential FPT algorithms, cycle-hitting problems, bidimensionality}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2021.4
A New Framework for Kernelization Lower Bounds: The Case of Maximum Minimal Vertex Cover

Authors: Júlio Araújo, Marin Bougeret, Victor Campos, and Ignasi Sau

Published in: LIPIcs, Volume 214, 16th International Symposium on Parameterized and Exact Computation (IPEC 2021)

Abstract
In the Maximum Minimal Vertex Cover (MMVC) problem, we are given a graph G and a positive integer k, and the objective is to decide whether G contains a minimal vertex cover of size at least k. Motivated by the kernelization of MMVC with parameter k, our main contribution is to introduce a simple general framework to obtain lower bounds on the degrees of a certain type of polynomial kernels for vertex-optimization problems, which we call {lop-kernels}. Informally, this type of kernels is required to preserve large optimal solutions in the reduced instance, and captures the vast majority of existing kernels in the literature. As a consequence of this framework, we show that the trivial quadratic kernel for MMVC is essentially optimal, answering a question of Boria et al. [Discret. Appl. Math. 2015], and that the known cubic kernel for Maximum Minimal Feedback Vertex Set is also essentially optimal. On the positive side, given the (plausible) non-existence of subquadratic kernels for MMVC on general graphs, we provide subquadratic kernels on H-free graphs for several graphs H, such as the bull, the paw, or the complete graphs, by making use of the Erdős-Hajnal property in order to find an appropriate decomposition. Finally, we prove that MMVC does not admit polynomial kernels parameterized by the size of a minimum vertex cover of the input graph, even on bipartite graphs, unless NP ⊆ coNP / poly. This indicates that parameters smaller than the solution size are unlike to yield polynomial kernels for MMVC.
Cite as

Júlio Araújo, Marin Bougeret, Victor Campos, and Ignasi Sau. A New Framework for Kernelization Lower Bounds: The Case of Maximum Minimal Vertex Cover. In 16th International Symposium on Parameterized and Exact Computation (IPEC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 214, pp. 4:1-4:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{araujo_et_al:LIPIcs.IPEC.2021.4,
  author =	{Ara\'{u}jo, J\'{u}lio and Bougeret, Marin and Campos, Victor and Sau, Ignasi},
  title =	{{A New Framework for Kernelization Lower Bounds: The Case of Maximum Minimal Vertex Cover}},
  booktitle =	{16th International Symposium on Parameterized and Exact Computation (IPEC 2021)},
  pages =	{4:1--4:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-216-7},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{214},
  editor =	{Golovach, Petr A. and Zehavi, Meirav},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2021.4},
  URN =		{urn:nbn:de:0030-drops-153879},
  doi =		{10.4230/LIPIcs.IPEC.2021.4},
  annote =	{Keywords: Maximum minimal vertex cover, parameterized complexity, polynomial kernel, kernelization lower bound, Erd\H{o}s-Hajnal property, induced subgraphs}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2020.16
Bridge-Depth Characterizes Which Structural Parameterizations of Vertex Cover Admit a Polynomial Kernel

Authors: Marin Bougeret, Bart M. P. Jansen, and Ignasi Sau

Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

Abstract
We study the kernelization complexity of structural parameterizations of the Vertex Cover problem. Here, the goal is to find a polynomial-time preprocessing algorithm that can reduce any instance (G,k) of the Vertex Cover problem to an equivalent one, whose size is polynomial in the size of a pre-determined complexity parameter of G. A long line of previous research deals with parameterizations based on the number of vertex deletions needed to reduce G to a member of a simple graph class ℱ, such as forests, graphs of bounded tree-depth, and graphs of maximum degree two. We set out to find the most general graph classes ℱ for which Vertex Cover parameterized by the vertex-deletion distance of the input graph to ℱ, admits a polynomial kernelization. We give a complete characterization of the minor-closed graph families ℱ for which such a kernelization exists. We introduce a new graph parameter called bridge-depth, and prove that a polynomial kernelization exists if and only if ℱ has bounded bridge-depth. The proof is based on an interesting connection between bridge-depth and the size of minimal blocking sets in graphs, which are vertex sets whose removal decreases the independence number.
Cite as

Marin Bougeret, Bart M. P. Jansen, and Ignasi Sau. Bridge-Depth Characterizes Which Structural Parameterizations of Vertex Cover Admit a Polynomial Kernel. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 16:1-16:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{bougeret_et_al:LIPIcs.ICALP.2020.16,
  author =	{Bougeret, Marin and Jansen, Bart M. P. and Sau, Ignasi},
  title =	{{Bridge-Depth Characterizes Which Structural Parameterizations of Vertex Cover Admit a Polynomial Kernel}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{16:1--16:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.16},
  URN =		{urn:nbn:de:0030-drops-124238},
  doi =		{10.4230/LIPIcs.ICALP.2020.16},
  annote =	{Keywords: vertex cover, parameterized complexity, polynomial kernel, structural parameterization, bridge-depth}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2019.2
Width Parameterizations for Knot-Free Vertex Deletion on Digraphs

Authors: Stéphane Bessy, Marin Bougeret, Alan D. A. Carneiro, Fábio Protti, and Uéverton S. Souza

Published in: LIPIcs, Volume 148, 14th International Symposium on Parameterized and Exact Computation (IPEC 2019)

Abstract
A knot in a directed graph G is a strongly connected subgraph Q of G with at least two vertices, such that no vertex in V(Q) is an in-neighbor of a vertex in V(G)\V(Q). Knots are important graph structures, because they characterize the existence of deadlocks in a classical distributed computation model, the so-called OR-model. Deadlock detection is correlated with the recognition of knot-free graphs as well as deadlock resolution is closely related to the Knot-Free Vertex Deletion (KFVD) problem, which consists of determining whether an input graph G has a subset S subseteq V(G) of size at most k such that G[V\S] contains no knot. Because of natural applications in deadlock resolution, KFVD is closely related to Directed Feedback Vertex Set. In this paper we focus on graph width measure parameterizations for KFVD. First, we show that: (i) KFVD parameterized by the size of the solution k is W[1]-hard even when p, the length of a longest directed path of the input graph, as well as kappa, its Kenny-width, are bounded by constants, and we remark that KFVD is para-NP-hard even considering many directed width measures as parameters, but in FPT when parameterized by clique-width; (ii) KFVD can be solved in time 2^{O(tw)} x n, but assuming ETH it cannot be solved in 2^{o(tw)} x n^{O(1)}, where tw is the treewidth of the underlying undirected graph. Finally, since the size of a minimum directed feedback vertex set (dfv) is an upper bound for the size of a minimum knot-free vertex deletion set, we investigate parameterization by dfv and we show that (iii) KFVD can be solved in FPT-time parameterized by either dfv+kappa or dfv+p. Results of (iii) cannot be improved when replacing dfv by k due to (i).
Cite as

Stéphane Bessy, Marin Bougeret, Alan D. A. Carneiro, Fábio Protti, and Uéverton S. Souza. Width Parameterizations for Knot-Free Vertex Deletion on Digraphs. In 14th International Symposium on Parameterized and Exact Computation (IPEC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 148, pp. 2:1-2:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{bessy_et_al:LIPIcs.IPEC.2019.2,
  author =	{Bessy, St\'{e}phane and Bougeret, Marin and Carneiro, Alan D. A. and Protti, F\'{a}bio and Souza, U\'{e}verton S.},
  title =	{{Width Parameterizations for Knot-Free Vertex Deletion on Digraphs}},
  booktitle =	{14th International Symposium on Parameterized and Exact Computation (IPEC 2019)},
  pages =	{2:1--2:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-129-0},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{148},
  editor =	{Jansen, Bart M. P. and Telle, Jan Arne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2019.2},
  URN =		{urn:nbn:de:0030-drops-114631},
  doi =		{10.4230/LIPIcs.IPEC.2019.2},
  annote =	{Keywords: Knot, deadlock, width measure, FPT, W\lbrack1\rbrack-hard, directed feedback vertex set}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2019.27
Packing Arc-Disjoint Cycles in Tournaments

Authors: Stéphane Bessy, Marin Bougeret, R. Krithika, Abhishek Sahu, Saket Saurabh, Jocelyn Thiebaut, and Meirav Zehavi

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

Abstract
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.
Cite as

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
DOI: 10.4230/LIPIcs.IPEC.2017.10
How Much Does a Treedepth Modulator Help to Obtain Polynomial Kernels Beyond Sparse Graphs?

Authors: Marin Bougeret and Ignasi Sau

Published in: LIPIcs, Volume 89, 12th International Symposium on Parameterized and Exact Computation (IPEC 2017)

Abstract
In the last years, kernelization with structural parameters has been an active area of research within the field of parameterized complexity. As a relevant example, Gajarsky et al. [ESA 2013] proved that every graph problem satisfying a property called finite integer index admits a linear kernel on graphs of bounded expansion and an almost linear kernel on nowhere dense graphs, parameterized by the size of a c-treedepth modulator, which is a vertex set whose removal results in a graph of treedepth at most c for a fixed integer c>0. The authors left as further research to investigate this parameter on general graphs, and in particular to find problems that, while admitting polynomial kernels on sparse graphs, behave differently on general graphs. In this article we answer this question by finding two very natural such problems: we prove that VERTEX COVER admits a polynomial kernel on general graphs for any integer c>0, and that DOMINATING SET does not for any integer c>1 even on degenerate graphs, unless NP is a subset of coNP/poly. For the positive result, we build on the techniques of Jansen and Bodlaender [STACS 2011], and for the negative result we use a polynomial parameter transformation for c>2 and an OR-cross-composition for c=2. As existing results imply that DOMINATING SET admits a polynomial kernel on degenerate graphs for c=1, our result provides a dichotomy about the existence of polynomial problems for DOMINATING SET on degenerate graphs with this parameter.
Cite as

Marin Bougeret and Ignasi Sau. How Much Does a Treedepth Modulator Help to Obtain Polynomial Kernels Beyond Sparse Graphs?. In 12th International Symposium on Parameterized and Exact Computation (IPEC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 89, pp. 10:1-10:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{bougeret_et_al:LIPIcs.IPEC.2017.10,
  author =	{Bougeret, Marin and Sau, Ignasi},
  title =	{{How Much Does a Treedepth Modulator Help to Obtain Polynomial Kernels Beyond Sparse Graphs?}},
  booktitle =	{12th International Symposium on Parameterized and Exact Computation (IPEC 2017)},
  pages =	{10:1--10:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-051-4},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{89},
  editor =	{Lokshtanov, Daniel and Nishimura, Naomi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2017.10},
  URN =		{urn:nbn:de:0030-drops-85564},
  doi =		{10.4230/LIPIcs.IPEC.2017.10},
  annote =	{Keywords: parameterized complexity, polynomial kernels, structural parameters, treedepth, treewidth, sparse graphs}
}
Document
DOI: 10.4230/LIPIcs.ESA.2017.14
Triangle Packing in (Sparse) Tournaments: Approximation and Kernelization

Authors: Stéphane Bessy, Marin Bougeret, and Jocelyn Thiebaut

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

Abstract
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.
Cite as

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}
}
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