Search Results

Documents authored by Lopes, Raul

Document
DOI: 10.4230/LIPIcs.ESA.2023.30
New Menger-Like Dualities in Digraphs and Applications to Half-Integral Linkages

Authors: Victor Campos, Jonas Costa, Raul Lopes, and Ignasi Sau

Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)

Abstract
We present new min-max relations in digraphs between the number of paths satisfying certain conditions and the order of the corresponding cuts. We define these objects in order to capture, in the context of solving the half-integral linkage problem, the essential properties needed for reaching a large bramble of congestion two (or any other constant) from the terminal set. This strategy has been used ad-hoc in several articles, usually with lengthy technical proofs, and our objective is to abstract it to make it applicable in a simpler and unified way. We provide two proofs of the min-max relations, one consisting in applying Menger’s Theorem on appropriately defined auxiliary digraphs, and an alternative simpler one using matroids, however with worse polynomial running time. As an application, we manage to simplify and improve several results of Edwards et al. [ESA 2017] and of Giannopoulou et al. [SODA 2022] about finding half-integral linkages in digraphs. Concerning the former, besides being simpler, our proof provides an almost optimal bound on the strong connectivity of a digraph for it to be half-integrally feasible under the presence of a large bramble of congestion two (or equivalently, if the directed tree-width is large, which is the hard case). Concerning the latter, our proof uses brambles as rerouting objects instead of cylindrical grids, hence yielding much better bounds and being somehow independent of a particular topology. We hope that our min-max relations will find further applications as, in our opinion, they are simple, robust, and versatile to be easily applicable to different types of routing problems in digraphs.
Cite as

Victor Campos, Jonas Costa, Raul Lopes, and Ignasi Sau. New Menger-Like Dualities in Digraphs and Applications to Half-Integral Linkages. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 30:1-30:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{campos_et_al:LIPIcs.ESA.2023.30,
  author =	{Campos, Victor and Costa, Jonas and Lopes, Raul and Sau, Ignasi},
  title =	{{New Menger-Like Dualities in Digraphs and Applications to Half-Integral Linkages}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{30:1--30:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.30},
  URN =		{urn:nbn:de:0030-drops-186838},
  doi =		{10.4230/LIPIcs.ESA.2023.30},
  annote =	{Keywords: directed graphs, min-max relation, half-integral linkage, directed disjoint paths, bramble, parameterized complexity, matroids}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2022.9
Twin-Width VIII: Delineation and Win-Wins

Authors: Édouard Bonnet, Dibyayan Chakraborty, Eun Jung Kim, Noleen Köhler, Raul Lopes, and Stéphan Thomassé

Published in: LIPIcs, Volume 249, 17th International Symposium on Parameterized and Exact Computation (IPEC 2022)

Abstract
We introduce the notion of delineation. A graph class C is said delineated by twin-width (or simply, delineated) if for every hereditary closure D of a subclass of C, it holds that D has bounded twin-width if and only if D is monadically dependent. An effective strengthening of delineation for a class C implies that tractable FO model checking on C is perfectly understood: On hereditary closures of subclasses D of C, FO model checking on D is fixed-parameter tractable (FPT) exactly when D has bounded twin-width. Ordered graphs [BGOdMSTT, STOC '22] and permutation graphs [BKTW, JACM '22] are effectively delineated, while subcubic graphs are not. On the one hand, we prove that interval graphs, and even, rooted directed path graphs are delineated. On the other hand, we observe or show that segment graphs, directed path graphs (with arbitrarily many roots), and visibility graphs of simple polygons are not delineated. In an effort to draw the delineation frontier between interval graphs (that are delineated) and axis-parallel two-lengthed segment graphs (that are not), we investigate the twin-width of restricted segment intersection classes. It was known that (triangle-free) pure axis-parallel unit segment graphs have unbounded twin-width [BGKTW, SODA '21]. We show that K_{t,t}-free segment graphs, and axis-parallel H_t-free unit segment graphs have bounded twin-width, where H_t is the half-graph or ladder of height t. In contrast, axis-parallel H₄-free two-lengthed segment graphs have unbounded twin-width. We leave as an open question whether unit segment graphs are delineated. More broadly, we explore which structures (large bicliques, half-graphs, or independent sets) are responsible for making the twin-width large on the main classes of intersection and visibility graphs. Our new results, combined with the FPT algorithm for first-order model checking on graphs given with O(1)-sequences [BKTW, JACM '22], give rise to a variety of algorithmic win-win arguments. They all fall in the same framework: If p is an FO definable graph parameter that effectively functionally upperbounds twin-width on a class C, then p(G) ⩾ k can be decided in FPT time f(k) ⋅ |V(G)|^O(1). For instance, we readily derive FPT algorithms for k-Ladder on visibility graphs of 1.5D terrains, and k-Independent Set on visibility graphs of simple polygons. This showcases that the theory of twin-width can serve outside of classes of bounded twin-width.
Cite as

Édouard Bonnet, Dibyayan Chakraborty, Eun Jung Kim, Noleen Köhler, Raul Lopes, and Stéphan Thomassé. Twin-Width VIII: Delineation and Win-Wins. In 17th International Symposium on Parameterized and Exact Computation (IPEC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 249, pp. 9:1-9:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bonnet_et_al:LIPIcs.IPEC.2022.9,
  author =	{Bonnet, \'{E}douard and Chakraborty, Dibyayan and Kim, Eun Jung and K\"{o}hler, Noleen and Lopes, Raul and Thomass\'{e}, St\'{e}phan},
  title =	{{Twin-Width VIII: Delineation and Win-Wins}},
  booktitle =	{17th International Symposium on Parameterized and Exact Computation (IPEC 2022)},
  pages =	{9:1--9:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-260-0},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{249},
  editor =	{Dell, Holger and Nederlof, Jesper},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2022.9},
  URN =		{urn:nbn:de:0030-drops-173650},
  doi =		{10.4230/LIPIcs.IPEC.2022.9},
  annote =	{Keywords: Twin-width, intersection graphs, visibility graphs, monadic dependence and stability, first-order model checking}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2020.68
A Relaxation of the Directed Disjoint Paths Problem: A Global Congestion Metric Helps

Authors: Raul Lopes and Ignasi Sau

Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)

Abstract
In the Directed Disjoint Paths problem, we are given a digraph D and a set of requests {(s₁, t₁), …, (s_k, t_k)}, and the task is to find a collection of pairwise vertex-disjoint paths {P₁, …, P_k} such that each P_i is a path from s_i to t_i in D. This problem is NP-complete for fixed k = 2 and W[1]-hard with parameter k in DAGs. A few positive results are known under restrictions on the input digraph, such as being planar or having bounded directed tree-width, or under relaxations of the problem, such as allowing for vertex congestion. Good news are scarce, however, for general digraphs. In this article we propose a novel global congestion metric for the problem: we only require the paths to be "disjoint enough", in the sense that they must behave properly not in the whole graph, but in an unspecified large part of it. Namely, in the Disjoint Enough Directed Paths problem, given an n-vertex digraph D, a set of k requests, and non-negative integers d and s, the task is to find a collection of paths connecting the requests such that at least d vertices of D occur in at most s paths of the collection. We study the parameterized complexity of this problem for a number of choices of the parameter, including the directed tree-width of D. Among other results, we show that the problem is W[1]-hard in DAGs with parameter d and, on the positive side, we give an algorithm in time 𝒪(n^{d+2} ⋅ k^{d⋅ s}) and a kernel of size d ⋅ 2^{k-s}⋅ binom(k,s) + 2k in general digraphs. This latter result has consequences for the Steiner Network problem: we show that it is FPT parameterized by the number k of terminals and d, where d = n - c and c is the size of the solution.
Cite as

Raul Lopes and Ignasi Sau. A Relaxation of the Directed Disjoint Paths Problem: A Global Congestion Metric Helps. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 68:1-68:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{lopes_et_al:LIPIcs.MFCS.2020.68,
  author =	{Lopes, Raul and Sau, Ignasi},
  title =	{{A Relaxation of the Directed Disjoint Paths Problem: A Global Congestion Metric Helps}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{68:1--68:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Esparza, Javier and Kr\'{a}l', Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.68},
  URN =		{urn:nbn:de:0030-drops-127378},
  doi =		{10.4230/LIPIcs.MFCS.2020.68},
  annote =	{Keywords: Parameterized complexity, directed disjoint paths, congestion, dual parameterization, kernelization, directed tree-width}
}
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