Search Results

Documents authored by Rambaud, Clément

Document
DOI: 10.4230/LIPIcs.WG.2026.7
Making an Oriented Graph Acyclic Using Inversions of Bounded or Prescribed Size

Authors: Jørgen Bang-Jensen, Frédéric Havet, Florian Hörsch, Clément Rambaud, Amadeus Reinald, and Caroline Silva

Published in: LIPIcs, Volume 376, 52nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2026)

Abstract
Given an oriented graph D, the inversion of a subset X of vertices consists in reversing the orientation of all arcs with both endpoints in X. When the subset X is of size p (resp. at most p), this operation is called an (= p)-inversion (resp. (⩽ p)-inversion). Then, an oriented graph is (= p)-invertible if it can be made acyclic by a sequence of p-inversions. We observe that, for n = |V(D)|, deciding whether D is (= n-1)-invertible is equivalent to deciding whether D is acyclically pushable, and thus NP-complete. In all other cases, whenever p ≠ n-1, we construct a polynomial-time algorithm deciding (= p)-invertibility. We then consider the (= p)-inversion number, inv^{= p}(D) (resp. (⩽ p)-inversion number, inv^{⩽ p}(D)), defined as the minimum number of (= p)-inversions (resp. (⩽ p)-inversions) rendering D acyclic. We show that every (= p)-invertible digraph D satisfies inv^{= p}(D) ⩽ |A(D)| for every integer p ⩾ 2. When p is even, we moreover bound inv^{= p} by a (linear) function of the feedback arc set number, and rule out the existence of any bounding function for odd p. Finally, we study the complexity of deciding whether the (= p)-inversion number, or the (⩽ p)-inversion number, of a given oriented graph is at most a given integer k. For any fixed positive integer p ⩾ 2, when k is part of the input, we show that both problems are NP-hard even in tournaments. In general oriented graphs, we prove W[1]-hardness for both problems when parameterized by p, even for k = 1. In contrast, we exhibit polynomial kernels in p + k for both problems in tournaments.
Cite as

Jørgen Bang-Jensen, Frédéric Havet, Florian Hörsch, Clément Rambaud, Amadeus Reinald, and Caroline Silva. Making an Oriented Graph Acyclic Using Inversions of Bounded or Prescribed Size. In 52nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 376, pp. 7:1-7:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bangjensen_et_al:LIPIcs.WG.2026.7,
  author =	{Bang-Jensen, J{\o}rgen and Havet, Fr\'{e}d\'{e}ric and H\"{o}rsch, Florian and Rambaud, Cl\'{e}ment and Reinald, Amadeus and Silva, Caroline},
  title =	{{Making an Oriented Graph Acyclic Using Inversions of Bounded or Prescribed Size}},
  booktitle =	{52nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2026)},
  pages =	{7:1--7:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-430-7},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{376},
  editor =	{Goedgebeur, Jan and Rz\k{a}\.{z}ewski, Pawe{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WG.2026.7},
  URN =		{urn:nbn:de:0030-drops-261733},
  doi =		{10.4230/LIPIcs.WG.2026.7},
  annote =	{Keywords: digraph, inversion, orientation, NP-hardness, acyclic, reconfiguration}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2022.11
On the Parameterized Complexity of Symmetric Directed Multicut

Authors: Eduard Eiben, Clément Rambaud, and Magnus Wahlström

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

Abstract
We study the problem Symmetric Directed Multicut from a parameterized complexity perspective. In this problem, the input is a digraph D, a set of cut requests C = {(s₁,t₁),…,(s_l,t_l)} and an integer k, and the task is to find a set X ⊆ V(D) of size at most k such that for every 1 ≤ i ≤ l, X intersects either all (s_i,t_i)-paths or all (t_i,s_i)-paths. Equivalently, every strongly connected component of D-X contains at most one vertex out of s_i and t_i for every i. This problem is previously known from research in approximation algorithms, where it is known to have an O(log k log log k)-approximation. We note that the problem, parameterized by k, directly generalizes multiple interesting FPT problems such as (Undirected) Vertex Multicut and Directed Subset Feedback Vertex Set. We are not able to settle the existence of an FPT algorithm parameterized purely by k, but we give three partial results: An FPT algorithm parameterized by k+l; an FPT-time 2-approximation parameterized by k; and an FPT algorithm parameterized by k for the special case that the cut requests form a clique, Symmetric Directed Multiway Cut. The existence of an FPT algorithm parameterized purely by k remains an intriguing open possibility.
Cite as

Eduard Eiben, Clément Rambaud, and Magnus Wahlström. On the Parameterized Complexity of Symmetric Directed Multicut. In 17th International Symposium on Parameterized and Exact Computation (IPEC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 249, pp. 11:1-11:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{eiben_et_al:LIPIcs.IPEC.2022.11,
  author =	{Eiben, Eduard and Rambaud, Cl\'{e}ment and Wahlstr\"{o}m, Magnus},
  title =	{{On the Parameterized Complexity of Symmetric Directed Multicut}},
  booktitle =	{17th International Symposium on Parameterized and Exact Computation (IPEC 2022)},
  pages =	{11:1--11:17},
  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.11},
  URN =		{urn:nbn:de:0030-drops-173679},
  doi =		{10.4230/LIPIcs.IPEC.2022.11},
  annote =	{Keywords: Parameterized complexity, directed graphs, graph separation problems}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact