14 Search Results for "Mouawad, Amer E."

Document
DOI: 10.4230/LIPIcs.IPEC.2023.9
Minimum Separator Reconfiguration

Authors: Guilherme C. M. Gomes, Clément Legrand-Duchesne, Reem Mahmoud, Amer E. Mouawad, Yoshio Okamoto, Vinicius F. dos Santos, and Tom C. van der Zanden

Published in: LIPIcs, Volume 285, 18th International Symposium on Parameterized and Exact Computation (IPEC 2023)

Abstract
We study the problem of reconfiguring one minimum s-t-separator A into another minimum s-t-separator B in some n-vertex graph G containing two non-adjacent vertices s and t. We consider several variants of the problem as we focus on both the token sliding and token jumping models. Our first contribution is a polynomial-time algorithm that computes (if one exists) a minimum-length sequence of slides transforming A into B. We additionally establish that the existence of a sequence of jumps (which need not be of minimum length) can be decided in polynomial time (by an algorithm that also outputs a witnessing sequence when one exists). In contrast, and somewhat surprisingly, we show that deciding if a sequence of at most 𝓁 jumps can transform A into B is an NP-complete problem. To complement this negative result, we investigate the parameterized complexity of what we believe to be the two most natural parameterized counterparts of the latter problem; in particular, we study the problem of computing a minimum-length sequence of jumps when parameterized by the size k of the minimum s-t-separators and when parameterized by the number 𝓁 of jumps. For the first parameterization, we show that the problem is fixed-parameter tractable, but does not admit a polynomial kernel unless NP ⊆ coNP/poly. We complete the picture by designing a kernel with 𝒪(𝓁²) vertices and edges for the length 𝓁 of the sequence as a parameter.
Cite as

Guilherme C. M. Gomes, Clément Legrand-Duchesne, Reem Mahmoud, Amer E. Mouawad, Yoshio Okamoto, Vinicius F. dos Santos, and Tom C. van der Zanden. Minimum Separator Reconfiguration. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 9:1-9:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{c.m.gomes_et_al:LIPIcs.IPEC.2023.9,
  author =	{C. M. Gomes, Guilherme and Legrand-Duchesne, Cl\'{e}ment and Mahmoud, Reem and Mouawad, Amer E. and Okamoto, Yoshio and F. dos Santos, Vinicius and C. van der Zanden, Tom},
  title =	{{Minimum Separator Reconfiguration}},
  booktitle =	{18th International Symposium on Parameterized and Exact Computation (IPEC 2023)},
  pages =	{9:1--9:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-305-8},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{285},
  editor =	{Misra, Neeldhara and Wahlstr\"{o}m, Magnus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.9},
  URN =		{urn:nbn:de:0030-drops-194288},
  doi =		{10.4230/LIPIcs.IPEC.2023.9},
  annote =	{Keywords: minimum separators, combinatorial reconfiguration, parameterized complexity, kernelization}
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2023.125
Indiscernibles and Flatness in Monadically Stable and Monadically NIP Classes

Authors: Jan Dreier, Nikolas Mählmann, Sebastian Siebertz, and Szymon Toruńczyk

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

Abstract
Monadically stable and monadically NIP classes of structures were initially studied in the context of model theory and defined in logical terms. They have recently attracted attention in the area of structural graph theory, as they generalize notions such as nowhere denseness, bounded cliquewidth, and bounded twinwidth. Our main result is the - to the best of our knowledge first - purely combinatorial characterization of monadically stable classes of graphs, in terms of a property dubbed flip-flatness. A class C of graphs is flip-flat if for every fixed radius r, every sufficiently large set of vertices of a graph G ∈ C contains a large subset of vertices with mutual distance larger than r, where the distance is measured in some graph G' that can be obtained from G by performing a bounded number of flips that swap edges and non-edges within a subset of vertices. Flip-flatness generalizes the notion of uniform quasi-wideness, which characterizes nowhere dense classes and had a key impact on the combinatorial and algorithmic treatment of nowhere dense classes. To obtain this result, we develop tools that also apply to the more general monadically NIP classes, based on the notion of indiscernible sequences from model theory. We show that in monadically stable and monadically NIP classes indiscernible sequences impose a strong combinatorial structure on their definable neighborhoods. All our proofs are constructive and yield efficient algorithms.
Cite as

Jan Dreier, Nikolas Mählmann, Sebastian Siebertz, and Szymon Toruńczyk. Indiscernibles and Flatness in Monadically Stable and Monadically NIP Classes. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 125:1-125:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{dreier_et_al:LIPIcs.ICALP.2023.125,
  author =	{Dreier, Jan and M\"{a}hlmann, Nikolas and Siebertz, Sebastian and Toru\'{n}czyk, Szymon},
  title =	{{Indiscernibles and Flatness in Monadically Stable and Monadically NIP Classes}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{125:1--125:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.125},
  URN =		{urn:nbn:de:0030-drops-181779},
  doi =		{10.4230/LIPIcs.ICALP.2023.125},
  annote =	{Keywords: stability, NIP, combinatorial characterization, first-order model checking}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2022.11
Combinatorial and Algorithmic Aspects of Monadic Stability

Authors: Jan Dreier, Nikolas Mählmann, Amer E. Mouawad, Sebastian Siebertz, and Alexandre Vigny

Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)

Abstract
Nowhere dense classes of graphs are classes of sparse graphs with rich structural and algorithmic properties, however, they fail to capture even simple classes of dense graphs. Monadically stable classes, originating from model theory, generalize nowhere dense classes and close them under transductions, i.e. transformations defined by colorings and simple first-order interpretations. In this work we aim to extend some combinatorial and algorithmic properties of nowhere dense classes to monadically stable classes of finite graphs. We prove the following results. - For every monadically stable class C and fixed integer s ≥ 3, the Ramsey numbers R_C(s,t) are bounded from above by 𝒪(t^{s-1-δ}) for some δ > 0, improving the bound R(s,t) ∈ 𝒪(t^{s-1}/(log t)^{s-1}) known for the class of all graphs and the bounds known for k-stable graphs when s ≤ k. - For every monadically stable class C and every integer r, there exists δ > 0 such that every graph G ∈ C that contains an r-subdivision of the biclique K_{t,t} as a subgraph also contains K_{t^δ,t^δ} as a subgraph. This generalizes earlier results for nowhere dense graph classes. - We obtain a stronger regularity lemma for monadically stable classes of graphs. - Finally, we show that we can compute polynomial kernels for the independent set and dominating set problems in powers of nowhere dense classes. Formerly, only fixed-parameter tractable algorithms were known for these problems on powers of nowhere dense classes.
Cite as

Jan Dreier, Nikolas Mählmann, Amer E. Mouawad, Sebastian Siebertz, and Alexandre Vigny. Combinatorial and Algorithmic Aspects of Monadic Stability. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 11:1-11:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{dreier_et_al:LIPIcs.ISAAC.2022.11,
  author =	{Dreier, Jan and M\"{a}hlmann, Nikolas and Mouawad, Amer E. and Siebertz, Sebastian and Vigny, Alexandre},
  title =	{{Combinatorial and Algorithmic Aspects of Monadic Stability}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{11:1--11:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-258-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{248},
  editor =	{Bae, Sang Won and Park, Heejin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.11},
  URN =		{urn:nbn:de:0030-drops-172961},
  doi =		{10.4230/LIPIcs.ISAAC.2022.11},
  annote =	{Keywords: Monadic Stability, Structural Graph Theory, Ramsey Numbers, Regularity, Kernels}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2022.39
On Finding Short Reconfiguration Sequences Between Independent Sets

Authors: Akanksha Agrawal, Soumita Hait, and Amer E. Mouawad

Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)

Abstract
Assume we are given a graph G, two independent sets S and T in G of size k ≥ 1, and a positive integer 𝓁 ≥ 1. The goal is to decide whether there exists a sequence ⟨ I₀, I₁, ..., I_𝓁 ⟩ of independent sets such that for all j ∈ {0,…,𝓁-1} the set I_j is an independent set of size k, I₀ = S, I_𝓁 = T, and I_{j+1} is obtained from I_j by a predetermined reconfiguration rule. We consider two reconfiguration rules, namely token sliding and token jumping. Intuitively, we view each independent set as a collection of tokens placed on the vertices of the graph. Then, the Token Sliding Optimization (TSO) problem asks whether there exists a sequence of at most 𝓁 steps that transforms S into T, where at each step we are allowed to slide one token from a vertex to an unoccupied neighboring vertex (while maintaining independence). In the Token Jumping Optimization (TJO) problem, at each step, we are allowed to jump one token from a vertex to any other unoccupied vertex of the graph (as long as we maintain independence). Both TSO and TJO are known to be fixed-parameter tractable when parameterized by 𝓁 on nowhere dense classes of graphs. In this work, we investigate the boundary of tractability for sparse classes of graphs. We show that both problems are fixed-parameter tractable for parameter k + 𝓁 + d on d-degenerate graphs as well as for parameter |M| + 𝓁 + Δ on graphs having a modulator M whose deletion leaves a graph of maximum degree Δ. We complement these result by showing that for parameter 𝓁 alone both problems become W[1]-hard already on 2-degenerate graphs. Our positive result makes use of the notion of independence covering families introduced by Lokshtanov et al. [Daniel Lokshtanov et al., 2020]. Finally, we show as a side result that using such families we can obtain a simpler and unified algorithm for the standard Token Jumping Reachability problem (a.k.a. Token Jumping) parameterized by k on both degenerate and nowhere dense classes of graphs.
Cite as

Akanksha Agrawal, Soumita Hait, and Amer E. Mouawad. On Finding Short Reconfiguration Sequences Between Independent Sets. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 39:1-39:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{agrawal_et_al:LIPIcs.ISAAC.2022.39,
  author =	{Agrawal, Akanksha and Hait, Soumita and Mouawad, Amer E.},
  title =	{{On Finding Short Reconfiguration Sequences Between Independent Sets}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{39:1--39:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-258-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{248},
  editor =	{Bae, Sang Won and Park, Heejin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.39},
  URN =		{urn:nbn:de:0030-drops-173244},
  doi =		{10.4230/LIPIcs.ISAAC.2022.39},
  annote =	{Keywords: Token sliding, token jumping, fixed-parameter tractability, combinatorial reconfiguration, shortest reconfiguration sequence}
}
Document
DOI: 10.4230/LIPIcs.ESA.2022.15
Galactic Token Sliding

Authors: Valentin Bartier, Nicolas Bousquet, and Amer E. Mouawad

Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)

Abstract
Given a graph G and two independent sets I_s and I_t of size k, the Independent Set Reconfiguration problem asks whether there exists a sequence of independent sets (each of size k) I_s = I₀, I₁, I₂, …, I_𝓁 = I_t such that each independent set is obtained from the previous one using a so-called reconfiguration step. Viewing each independent set as a collection of k tokens placed on the vertices of a graph G, the two most studied reconfiguration steps are token jumping and token sliding. In the Token Jumping variant of the problem, a single step allows a token to jump from one vertex to any other vertex in the graph. In the Token Sliding variant, a token is only allowed to slide from a vertex to one of its neighbors. Like the Independent Set problem, both of the aforementioned problems are known to be W[1]-hard on general graphs (for parameter k). A very fruitful line of research [Bodlaender, 1988; Grohe et al., 2017; Telle and Villanger, 2019; Pilipczuk and Siebertz, 2021] has showed that the Independent Set problem becomes fixed-parameter tractable when restricted to sparse graph classes, such as planar, bounded treewidth, nowhere-dense, and all the way to biclique-free graphs. Over a series of papers, the same was shown to hold for the Token Jumping problem [Ito et al., 2014; Lokshtanov et al., 2018; Siebertz, 2018; Bousquet et al., 2017]. As for the Token Sliding problem, which is mentioned in most of these papers, almost nothing is known beyond the fact that the problem is polynomial-time solvable on trees [Demaine et al., 2015] and interval graphs [Marthe Bonamy and Nicolas Bousquet, 2017]. We remedy this situation by introducing a new model for the reconfiguration of independent sets, which we call galactic reconfiguration. Using this new model, we show that (standard) Token Sliding is fixed-parameter tractable on graphs of bounded degree, planar graphs, and chordal graphs of bounded clique number. We believe that the galactic reconfiguration model is of independent interest and could potentially help in resolving the remaining open questions concerning the (parameterized) complexity of Token Sliding.
Cite as

Valentin Bartier, Nicolas Bousquet, and Amer E. Mouawad. Galactic Token Sliding. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 15:1-15:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bartier_et_al:LIPIcs.ESA.2022.15,
  author =	{Bartier, Valentin and Bousquet, Nicolas and Mouawad, Amer E.},
  title =	{{Galactic Token Sliding}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{15:1--15:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.15},
  URN =		{urn:nbn:de:0030-drops-169535},
  doi =		{10.4230/LIPIcs.ESA.2022.15},
  annote =	{Keywords: reconfiguration, independent set, galactic reconfiguration, sparse graphs, token sliding, parameterized complexity}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2020.24
On the Parameterized Complexity of Reconfiguration of Connected Dominating Sets

Authors: Daniel Lokshtanov, Amer E. Mouawad, Fahad Panolan, and Sebastian Siebertz

Published in: LIPIcs, Volume 180, 15th International Symposium on Parameterized and Exact Computation (IPEC 2020)

Abstract
In a reconfiguration version of a decision problem 𝒬 the input is an instance of 𝒬 and two feasible solutions S and T. The objective is to determine whether there exists a step-by-step transformation between S and T such that all intermediate steps also constitute feasible solutions. In this work, we study the parameterized complexity of the Connected Dominating Set Reconfiguration problem (CDS-R). It was shown in previous work that the Dominating Set Reconfiguration problem (DS-R) parameterized by k, the maximum allowed size of a dominating set in a reconfiguration sequence, is fixed-parameter tractable on all graphs that exclude a biclique K_{d,d} as a subgraph, for some constant d ≥ 1. We show that the additional connectivity constraint makes the problem much harder, namely, that CDS-R is W[1]-hard parameterized by k+𝓁, the maximum allowed size of a dominating set plus the length of the reconfiguration sequence, already on 5-degenerate graphs. On the positive side, we show that CDS-R parameterized by k is fixed-parameter tractable, and in fact admits a polynomial kernel on planar graphs.
Cite as

Daniel Lokshtanov, Amer E. Mouawad, Fahad Panolan, and Sebastian Siebertz. On the Parameterized Complexity of Reconfiguration of Connected Dominating Sets. In 15th International Symposium on Parameterized and Exact Computation (IPEC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 180, pp. 24:1-24:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{lokshtanov_et_al:LIPIcs.IPEC.2020.24,
  author =	{Lokshtanov, Daniel and Mouawad, Amer E. and Panolan, Fahad and Siebertz, Sebastian},
  title =	{{On the Parameterized Complexity of Reconfiguration of Connected Dominating Sets}},
  booktitle =	{15th International Symposium on Parameterized and Exact Computation (IPEC 2020)},
  pages =	{24:1--24:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-172-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{180},
  editor =	{Cao, Yixin and Pilipczuk, Marcin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2020.24},
  URN =		{urn:nbn:de:0030-drops-133276},
  doi =		{10.4230/LIPIcs.IPEC.2020.24},
  annote =	{Keywords: reconfiguration, parameterized complexity, connected dominating set, graph structure theory}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2020.44
On Girth and the Parameterized Complexity of Token Sliding and Token Jumping

Authors: Valentin Bartier, Nicolas Bousquet, Clément Dallard, Kyle Lomer, and Amer E. Mouawad

Published in: LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)

Abstract
In the Token Jumping problem we are given a graph G = (V,E) and two independent sets S and T of G, each of size k ≥ 1. The goal is to determine whether there exists a sequence of k-sized independent sets in G, 〈S_0, S_1, ..., S_𝓁〉, such that for every i, |S_i| = k, S_i is an independent set, S = S_0, S_𝓁 = T, and |S_i Δ S_i+1| = 2. In other words, if we view each independent set as a collection of tokens placed on a subset of the vertices of G, then the problem asks for a sequence of independent sets which transforms S to T by individual token jumps which maintain the independence of the sets. This problem is known to be PSPACE-complete on very restricted graph classes, e.g., planar bounded degree graphs and graphs of bounded bandwidth. A closely related problem is the Token Sliding problem, where instead of allowing a token to jump to any vertex of the graph we instead require that a token slides along an edge of the graph. Token Sliding is also known to be PSPACE-complete on the aforementioned graph classes. We investigate the parameterized complexity of both problems on several graph classes, focusing on the effect of excluding certain cycles from the input graph. In particular, we show that both Token Sliding and Token Jumping are fixed-parameter tractable on C_4-free bipartite graphs when parameterized by k. For Token Jumping, we in fact show that the problem admits a polynomial kernel on {C_3,C_4}-free graphs. In the case of Token Sliding, we also show that the problem admits a polynomial kernel on bipartite graphs of bounded degree. We believe both of these results to be of independent interest. We complement these positive results by showing that, for any constant p ≥ 4, both problems are W[1]-hard on {C_4, ..., C_p}-free graphs and Token Sliding remains W[1]-hard even on bipartite graphs.
Cite as

Valentin Bartier, Nicolas Bousquet, Clément Dallard, Kyle Lomer, and Amer E. Mouawad. On Girth and the Parameterized Complexity of Token Sliding and Token Jumping. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 44:1-44:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{bartier_et_al:LIPIcs.ISAAC.2020.44,
  author =	{Bartier, Valentin and Bousquet, Nicolas and Dallard, Cl\'{e}ment and Lomer, Kyle and Mouawad, Amer E.},
  title =	{{On Girth and the Parameterized Complexity of Token Sliding and Token Jumping}},
  booktitle =	{31st International Symposium on Algorithms and Computation (ISAAC 2020)},
  pages =	{44:1--44:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-173-3},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{181},
  editor =	{Cao, Yixin and Cheng, Siu-Wing and Li, Minming},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.44},
  URN =		{urn:nbn:de:0030-drops-133886},
  doi =		{10.4230/LIPIcs.ISAAC.2020.44},
  annote =	{Keywords: Combinatorial reconfiguration, Independent Set, Token Jumping, Token Sliding, Parameterized Complexity}
}
Document
DOI: 10.4230/LIPIcs.ESA.2019.42
Bisection of Bounded Treewidth Graphs by Convolutions

Authors: Eduard Eiben, Daniel Lokshtanov, and Amer E. Mouawad

Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)

Abstract
In the Bisection problem, we are given as input an edge-weighted graph G. The task is to find a partition of V(G) into two parts A and B such that ||A| - |B|| <= 1 and the sum of the weights of the edges with one endpoint in A and the other in B is minimized. We show that the complexity of the Bisection problem on trees, and more generally on graphs of bounded treewidth, is intimately linked to the (min, +)-Convolution problem. Here the input consists of two sequences (a[i])^{n-1}_{i = 0} and (b[i])^{n-1}_{i = 0}, the task is to compute the sequence (c[i])^{n-1}_{i = 0}, where c[k] = min_{i=0,...,k}(a[i] + b[k - i]). In particular, we prove that if (min, +)-Convolution can be solved in O(tau(n)) time, then Bisection of graphs of treewidth t can be solved in time O(8^t t^{O(1)} log n * tau(n)), assuming a tree decomposition of width t is provided as input. Plugging in the naive O(n^2) time algorithm for (min, +)-Convolution yields a O(8^t t^{O(1)} n^2 log n) time algorithm for Bisection. This improves over the (dependence on n of the) O(2^t n^3) time algorithm of Jansen et al. [SICOMP 2005] at the cost of a worse dependence on t. "Conversely", we show that if Bisection can be solved in time O(beta(n)) on edge weighted trees, then (min, +)-Convolution can be solved in O(beta(n)) time as well. Thus, obtaining a sub-quadratic algorithm for Bisection on trees is extremely challenging, and could even be impossible. On the other hand, for unweighted graphs of treewidth t, by making use of a recent algorithm for Bounded Difference (min, +)-Convolution of Chan and Lewenstein [STOC 2015], we obtain a sub-quadratic algorithm for Bisection with running time O(8^t t^{O(1)} n^{1.864} log n).
Cite as

Eduard Eiben, Daniel Lokshtanov, and Amer E. Mouawad. Bisection of Bounded Treewidth Graphs by Convolutions. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 42:1-42:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{eiben_et_al:LIPIcs.ESA.2019.42,
  author =	{Eiben, Eduard and Lokshtanov, Daniel and Mouawad, Amer E.},
  title =	{{Bisection of Bounded Treewidth Graphs by Convolutions}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{42:1--42:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-124-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{144},
  editor =	{Bender, Michael A. and Svensson, Ola and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.42},
  URN =		{urn:nbn:de:0030-drops-111639},
  doi =		{10.4230/LIPIcs.ESA.2019.42},
  annote =	{Keywords: bisection, convolution, treewidth, fine-grained analysis, hardness in P}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2018.34
On the Parameterized Complexity of [1,j]-Domination Problems

Authors: Mohsen Alambardar Meybodi, Fedor Fomin, Amer E. Mouawad, and Fahad Panolan

Published in: LIPIcs, Volume 122, 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)

Abstract
For a graph G, a set D subseteq V(G) is called a [1,j]-dominating set if every vertex in V(G) setminus D has at least one and at most j neighbors in D. A set D subseteq V(G) is called a [1,j]-total dominating set if every vertex in V(G) has at least one and at most j neighbors in D. In the [1,j]-(Total) Dominating Set problem we are given a graph G and a positive integer k. The objective is to test whether there exists a [1,j]-(total) dominating set of size at most k. The [1,j]-Dominating Set problem is known to be NP-complete, even for restricted classes of graphs such as chordal and planar graphs, but polynomial-time solvable on split graphs. The [1,2]-Total Dominating Set problem is known to be NP-complete, even for bipartite graphs. As both problems generalize the Dominating Set problem, both are W[1]-hard when parameterized by solution size. In this work, we study [1,j]-Dominating Set on sparse graph classes from the perspective of parameterized complexity and prove the following results when the problem is parameterized by solution size: - [1,j]-Dominating Set is W[1]-hard on d-degenerate graphs for d = j + 1; - [1,j]-Dominating Set is FPT on nowhere dense graphs. We also prove that the known algorithm for [1,j]-Dominating Set on split graphs is optimal under the Strong Exponential Time Hypothesis (SETH). Finally, assuming SETH, we provide a lower bound for the running time of any algorithm solving the [1,2]-Total Dominating Set problem parameterized by pathwidth.
Cite as

Mohsen Alambardar Meybodi, Fedor Fomin, Amer E. Mouawad, and Fahad Panolan. On the Parameterized Complexity of [1,j]-Domination Problems. In 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 122, pp. 34:1-34:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{alambardarmeybodi_et_al:LIPIcs.FSTTCS.2018.34,
  author =	{Alambardar Meybodi, Mohsen and Fomin, Fedor and Mouawad, Amer E. and Panolan, Fahad},
  title =	{{On the Parameterized Complexity of \lbrack1,j\rbrack-Domination Problems}},
  booktitle =	{38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)},
  pages =	{34:1--34:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-093-4},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{122},
  editor =	{Ganguly, Sumit and Pandya, Paritosh},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2018.34},
  URN =		{urn:nbn:de:0030-drops-99330},
  doi =		{10.4230/LIPIcs.FSTTCS.2018.34},
  annote =	{Keywords: \lbrack1, j\rbrack-dominating set, parameterized complexity, sparse graphs}
}
Document
DOI: 10.4230/LIPIcs.STACS.2018.29
Lossy Kernels for Connected Dominating Set on Sparse Graphs

Authors: Eduard Eiben, Mithilesh Kumar, Amer E. Mouawad, Fahad Panolan, and Sebastian Siebertz

Published in: LIPIcs, Volume 96, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)

Abstract
For alpha > 1, an alpha-approximate (bi-)kernel for a problem Q is a polynomial-time algorithm that takes as input an instance (I, k) of Q and outputs an instance (I',k') (of a problem Q') of size bounded by a function of k such that, for every c >= 1, a c-approximate solution for the new instance can be turned into a (c alpha)-approximate solution of the original instance in polynomial time. This framework of lossy kernelization was recently introduced by Lokshtanov et al. We study Connected Dominating Set (and its distance-r variant) parameterized by solution size on sparse graph classes like biclique-free graphs, classes of bounded expansion, and nowhere dense classes. We prove that for every alpha > 1, Connected Dominating Set admits a polynomial-size alpha-approximate (bi-)kernel on all the aforementioned classes. Our results are in sharp contrast to the kernelization complexity of Connected Dominating Set, which is known to not admit a polynomial kernel even on 2-degenerate graphs and graphs of bounded expansion, unless NP \subseteq coNP/poly. We complement our results by the following conditional lower bound. We show that if a class C is somewhere dense and closed under taking subgraphs, then for some value of r \in N there cannot exist an alpha-approximate bi-kernel for the (Connected) Distance-r Dominating Set problem on C for any alpha > 1 (assuming the Gap Exponential Time Hypothesis).
Cite as

Eduard Eiben, Mithilesh Kumar, Amer E. Mouawad, Fahad Panolan, and Sebastian Siebertz. Lossy Kernels for Connected Dominating Set on Sparse Graphs. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 29:1-29:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{eiben_et_al:LIPIcs.STACS.2018.29,
  author =	{Eiben, Eduard and Kumar, Mithilesh and Mouawad, Amer E. and Panolan, Fahad and Siebertz, Sebastian},
  title =	{{Lossy Kernels for Connected Dominating Set on Sparse Graphs}},
  booktitle =	{35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)},
  pages =	{29:1--29:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-062-0},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{96},
  editor =	{Niedermeier, Rolf and Vall\'{e}e, Brigitte},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2018.29},
  URN =		{urn:nbn:de:0030-drops-85027},
  doi =		{10.4230/LIPIcs.STACS.2018.29},
  annote =	{Keywords: Lossy Kernelization, Connected Dominating Set, Sparse Graph Classes}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2017.9
On the Parameterized Complexity of Simultaneous Deletion Problems

Authors: Akanksha Agrawal, R. Krithika, Daniel Lokshtanov, Amer E. Mouawad, and M. S. Ramanujan

Published in: LIPIcs, Volume 93, 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)

Abstract
For a family of graphs F, an n-vertex graph G, and a positive integer k, the F-Deletion problem asks whether we can delete at most k vertices from G to obtain a graph in F. F-Deletion generalizes many classical graph problems such as Vertex Cover, Feedback Vertex Set, and Odd Cycle Transversal. A (multi) graph G = (V, \cup_{i=1}^{\alpha} E_{i}), where the edge set of G is partitioned into \alpha color classes, is called an \alpha-edge-colored graph. A natural extension of the F-Deletion problem to edge-colored graphs is the Simultaneous (F_1, \ldots, F_\alpha)-Deletion problem. In the latter problem, we are given an \alpha-edge-colored graph G and the goal is to find a set S of at most k vertices such that each graph G_i - S, where G_i = (V, E_i) and 1 \leq i \leq \alpha, is in F_i. Recently, a subset of the authors considered the aforementioned problem with F_1 = \ldots = F_\alpha being the family of all forests. They showed that the problem is fixed-parameter tractable when parameterized by k and \alpha, and can be solved in O(2^{O(\alpha k)}n^{O(1)}) time. In this work, we initiate the investigation of the complexity of Simultaneous (F_1, \ldots, F_\alpha)-Deletion with different families of graphs. In the process, we obtain a complete characterization of the parameterized complexity of this problem when one or more of the F_i's is the class of bipartite graphs and the rest (if any) are forests. We show that if F_1 is the family of all bipartite graphs and each of F_2 = F_3 = \ldots = F_\alpha is the family of all forests then the problem is fixed-parameter tractable parameterized by k and \alpha. However, even when F_1 and F_2 are both the family of all bipartite graphs, then the Simultaneous (F_1, F_2)-Deletion} problem itself is already W[1]-hard.
Cite as

Akanksha Agrawal, R. Krithika, Daniel Lokshtanov, Amer E. Mouawad, and M. S. Ramanujan. On the Parameterized Complexity of Simultaneous Deletion Problems. In 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 93, pp. 9:1-9:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{agrawal_et_al:LIPIcs.FSTTCS.2017.9,
  author =	{Agrawal, Akanksha and Krithika, R. and Lokshtanov, Daniel and Mouawad, Amer E. and Ramanujan, M. S.},
  title =	{{On the Parameterized Complexity of Simultaneous Deletion Problems}},
  booktitle =	{37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)},
  pages =	{9:1--9:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-055-2},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{93},
  editor =	{Lokam, Satya and Ramanujam, R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2017.9},
  URN =		{urn:nbn:de:0030-drops-84128},
  doi =		{10.4230/LIPIcs.FSTTCS.2017.9},
  annote =	{Keywords: parameterized complexity, feedback vertex set, odd cycle transversal, edge-colored graphs, simultaneous deletion}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2017.71
Packing Cycles Faster Than Erdos-Posa

Authors: Daniel Lokshtanov, Amer E. Mouawad, Saket Saurabh, and Meirav Zehavi

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

Abstract
The Cycle Packing problem asks whether a given undirected graph G=(V,E) contains k vertex-disjoint cycles. Since the publication of the classic Erdos-Posa theorem in 1965, this problem received significant scientific attention in the fields of Graph Theory and Algorithm Design. In particular, this problem is one of the first problems studied in the framework of Parameterized Complexity. The non-uniform fixed-parameter tractability of Cycle Packing follows from the Robertson–Seymour theorem, a fact already observed by Fellows and Langston in the 1980s. In 1994, Bodlaender showed that Cycle Packing can be solved in time 2^{O(k^2)}|V| using exponential space. In case a solution exists, Bodlaender's algorithm also outputs a solution (in the same time). It has later become common knowledge that Cycle Packing admits a 2^{O(k\log^2 k)}|V|-time (deterministic) algorithm using exponential space, which is a consequence of the Erdos-Posa theorem. Nowadays, the design of this algorithm is given as an exercise in textbooks on Parameterized Complexity. Yet, no algorithm that runs in time 2^{o(k\log^2k)}|V|^{O(1)}, beating the bound 2^{O(k\log^2k)}\cdot |V|^{O(1)}, has been found. In light of this, it seems natural to ask whether the 2^{O(k\log^2k)}|V|^{O(1)}$ bound is essentially optimal. In this paper, we answer this question negatively by developing a 2^{O(k\log^2k/log log k})} |V|-time (deterministic) algorithm for Cycle Packing. In case a solution exists, our algorithm also outputs a solution (in the same time). Moreover, apart from beating the known bound, our algorithm runs in time linear in |V|, and its space complexity is polynomial in the input size.
Cite as

Daniel Lokshtanov, Amer E. Mouawad, Saket Saurabh, and Meirav Zehavi. Packing Cycles Faster Than Erdos-Posa. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 71:1-71:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{lokshtanov_et_al:LIPIcs.ICALP.2017.71,
  author =	{Lokshtanov, Daniel and Mouawad, Amer E. and Saurabh, Saket and Zehavi, Meirav},
  title =	{{Packing Cycles Faster Than Erdos-Posa}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{71:1--71:15},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.71},
  URN =		{urn:nbn:de:0030-drops-73857},
  doi =		{10.4230/LIPIcs.ICALP.2017.71},
  annote =	{Keywords: Parameterized Complexity, Graph Algorithms, Cycle Packing, Erd\"{o}s-P\'{o}sa Theorem}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2016.26
Kernelization of Cycle Packing with Relaxed Disjointness Constraints

Authors: Akanksha Agrawal, Daniel Lokshtanov, Diptapriyo Majumdar, Amer E. Mouawad, and Saket Saurabh

Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

Abstract
A key result in the field of kernelization, a subfield of parameterized complexity, states that the classic Disjoint Cycle Packing problem, i.e. finding k vertex disjoint cycles in a given graph G, admits no polynomial kernel unless NP subseteq coNP/poly. However, very little is known about this problem beyond the aforementioned kernelization lower bound (within the parameterized complexity framework). In the hope of clarifying the picture and better understanding the types of "constraints" that separate "kernelizable" from "non-kernelizable" variants of Disjoint Cycle Packing, we investigate two relaxations of the problem. The first variant, which we call Almost Disjoint Cycle Packing, introduces a "global" relaxation parameter t. That is, given a graph G and integers k and t, the goal is to find at least k distinct cycles such that every vertex of G appears in at most t of the cycles. The second variant, Pairwise Disjoint Cycle Packing, introduces a "local" relaxation parameter and we seek at least k distinct cycles such that every two cycles intersect in at most t vertices. While the Pairwise Disjoint Cycle Packing problem admits a polynomial kernel for all t >= 1, the kernelization complexity of Almost Disjoint Cycle Packing reveals an interesting spectrum of upper and lower bounds. In particular, for t = k/c, where c could be a function of k, we obtain a kernel of size O(2^{c^{2}}*k^{7+c}*log^3(k)) whenever c in o(sqrt(k))). Thus the kernel size varies from being sub-exponential when c in o(sqrt(k)), to quasipolynomial when c in o(log^l(k)), l in R_+, and polynomial when c in O(1). We complement these results for Almost Disjoint Cycle Packing by showing that the problem does not admit a polynomial kernel whenever t in O(k^{epsilon}), for any 0 <= epsilon < 1.
Cite as

Akanksha Agrawal, Daniel Lokshtanov, Diptapriyo Majumdar, Amer E. Mouawad, and Saket Saurabh. Kernelization of Cycle Packing with Relaxed Disjointness Constraints. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 26:1-26:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{agrawal_et_al:LIPIcs.ICALP.2016.26,
  author =	{Agrawal, Akanksha and Lokshtanov, Daniel and Majumdar, Diptapriyo and Mouawad, Amer E. and Saurabh, Saket},
  title =	{{Kernelization of Cycle Packing with Relaxed Disjointness Constraints}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{26:1--26:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.26},
  URN =		{urn:nbn:de:0030-drops-63053},
  doi =		{10.4230/LIPIcs.ICALP.2016.26},
  annote =	{Keywords: parameterized complexity, cycle packing, kernelization, relaxation}
}
Document
DOI: 10.4230/LIPIcs.STACS.2016.7
Simultaneous Feedback Vertex Set: A Parameterized Perspective

Authors: Akanksha Agrawal, Daniel Lokshtanov, Amer E. Mouawad, and Saket Saurabh

Published in: LIPIcs, Volume 47, 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)

Abstract
For a family of graphs F, a graph G, and a positive integer k, the F-DELETION problem asks whether we can delete at most k vertices from G to obtain a graph in F. F-DELETION generalizes many classical graph problems such as Vertex Cover, Feedback Vertex Set, and Odd Cycle Transversal. A graph G = (V, cup_{i=1}^{alpha} E_{i}), where the edge set of G is partitioned into alpha color classes, is called an alpha-edge-colored graph. A natural extension of the F-DELETION problem to edge-colored graphs is the alpha-SIMULTANEOUS F-DELETION problem. In the latter problem, we are given an alpha-edge-colored graph G and the goal is to find a set S of at most k vertices such that each graph G_i\S, where G_i = (V, E_i) and 1 <= i <= alpha, is in F. In this work, we study alpha-SIMULTANEOUS F-DELETION for F being the family of forests. In other words, we focus on the alpha-SIMULTANEOUS FEEDBACK VERTEX SET (alpha-SIMFVS) problem. Algorithmically, we show that, like its classical counterpart, alpha-SIMFVS parameterized by k is fixed-parameter tractable (FPT) and admits a polynomial kernel, for any fixed constant alpha. In particular, we give an algorithm running in 2^{O(alpha * k)} * n^{O(1)} time and a kernel with O(alpha * k^{3(alpha + 1)}) vertices. The running time of our algorithm implies that alpha-SIMFVS is FPT even when alpha in o(log(n)). We complement this positive result by showing that for alpha in O(log(n)), where n is the number of vertices in the input graph, alpha-SIMFVS becomes W[1]-hard. Our positive results answer one of the open problems posed by Cai and Ye (MFCS 2014).
Cite as

Akanksha Agrawal, Daniel Lokshtanov, Amer E. Mouawad, and Saket Saurabh. Simultaneous Feedback Vertex Set: A Parameterized Perspective. In 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 47, pp. 7:1-7:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{agrawal_et_al:LIPIcs.STACS.2016.7,
  author =	{Agrawal, Akanksha and Lokshtanov, Daniel and Mouawad, Amer E. and Saurabh, Saket},
  title =	{{Simultaneous Feedback Vertex Set: A Parameterized Perspective}},
  booktitle =	{33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)},
  pages =	{7:1--7:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-001-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{47},
  editor =	{Ollinger, Nicolas and Vollmer, Heribert},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2016.7},
  URN =		{urn:nbn:de:0030-drops-57084},
  doi =		{10.4230/LIPIcs.STACS.2016.7},
  annote =	{Keywords: parameterized complexity ,feedback vertex set, kernel, edge-colored graphs}
}
  • Refine by Author
  • 13 Mouawad, Amer E.
  • 6 Lokshtanov, Daniel
  • 4 Agrawal, Akanksha
  • 4 Siebertz, Sebastian
  • 3 Panolan, Fahad
  • Show More...

  • Refine by Classification
  • 3 Mathematics of computing → Graph algorithms
  • 3 Theory of computation → Parameterized complexity and exact algorithms
  • 2 Theory of computation → Design and analysis of algorithms
  • 2 Theory of computation → Graph algorithms analysis
  • 1 Mathematics of computing → Combinatoric problems
  • Show More...

  • Refine by Keyword
  • 6 parameterized complexity
  • 2 Parameterized Complexity
  • 2 combinatorial reconfiguration
  • 2 edge-colored graphs
  • 2 kernelization
  • Show More...

  • Refine by Type
  • 14 document

  • Refine by Publication Year
  • 3 2018
  • 3 2022
  • 2 2016
  • 2 2020
  • 2 2023
  • Show More...

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