51 Search Results for "Kanj, Iyad"

Volume

LIPIcs, Volume 43

10th International Symposium on Parameterized and Exact Computation (IPEC 2015)

IPEC 2015, September 16-18, 2015, Patras, Greece

Editors: Thore Husfeldt and Iyad Kanj

Document
DOI: 10.4230/LIPIcs.SEA.2023.10
Solving Directed Feedback Vertex Set by Iterative Reduction to Vertex Cover

Authors: Sebastian Angrick, Ben Bals, Katrin Casel, Sarel Cohen, Tobias Friedrich, Niko Hastrich, Theresa Hradilak, Davis Issac, Otto Kißig, Jonas Schmidt, and Leo Wendt

Published in: LIPIcs, Volume 265, 21st International Symposium on Experimental Algorithms (SEA 2023)

Abstract
In the Directed Feedback Vertex Set (DFVS) problem, one is given a directed graph G = (V,E) and wants to find a minimum cardinality set S ⊆ V such that G-S is acyclic. DFVS is a fundamental problem in computer science and finds applications in areas such as deadlock detection. The problem was the subject of the 2022 PACE coding challenge. We develop a novel exact algorithm for the problem that is tailored to perform well on instances that are mostly bi-directed. For such instances, we adapt techniques from the well-researched vertex cover problem. Our core idea is an iterative reduction to vertex cover. To this end, we also develop a new reduction rule that reduces the number of not bi-directed edges. With the resulting algorithm, we were able to win third place in the exact track of the PACE challenge. We perform computational experiments and compare the running time to other exact algorithms, in particular to the winning algorithm in PACE. Our experiments show that we outpace the other algorithms on instances that have a low density of uni-directed edges.
Cite as

Sebastian Angrick, Ben Bals, Katrin Casel, Sarel Cohen, Tobias Friedrich, Niko Hastrich, Theresa Hradilak, Davis Issac, Otto Kißig, Jonas Schmidt, and Leo Wendt. Solving Directed Feedback Vertex Set by Iterative Reduction to Vertex Cover. In 21st International Symposium on Experimental Algorithms (SEA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 265, pp. 10:1-10:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{angrick_et_al:LIPIcs.SEA.2023.10,
  author =	{Angrick, Sebastian and Bals, Ben and Casel, Katrin and Cohen, Sarel and Friedrich, Tobias and Hastrich, Niko and Hradilak, Theresa and Issac, Davis and Ki{\ss}ig, Otto and Schmidt, Jonas and Wendt, Leo},
  title =	{{Solving Directed Feedback Vertex Set by Iterative Reduction to Vertex Cover}},
  booktitle =	{21st International Symposium on Experimental Algorithms (SEA 2023)},
  pages =	{10:1--10:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-279-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{265},
  editor =	{Georgiadis, Loukas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2023.10},
  URN =		{urn:nbn:de:0030-drops-183602},
  doi =		{10.4230/LIPIcs.SEA.2023.10},
  annote =	{Keywords: directed feedback vertex set, vertex cover, reduction rules}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2023.28
The Parameterized Complexity of Coordinated Motion Planning

Authors: Eduard Eiben, Robert Ganian, and Iyad Kanj

Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)

Abstract
In Coordinated Motion Planning (CMP), we are given a rectangular-grid on which k robots occupy k distinct starting gridpoints and need to reach k distinct destination gridpoints. In each time step, any robot may move to a neighboring gridpoint or stay in its current gridpoint, provided that it does not collide with other robots. The goal is to compute a schedule for moving the k robots to their destinations which minimizes a certain objective target - prominently the number of time steps in the schedule, i.e., the makespan, or the total length traveled by the robots. We refer to the problem arising from minimizing the former objective target as CMP-M and the latter as CMP-L. Both CMP-M and CMP-L are fundamental problems that were posed as the computational geometry challenge of SoCG 2021, and CMP also embodies the famous (n²-1)-puzzle as a special case. In this paper, we settle the parameterized complexity of CMP-M and CMP-L with respect to their two most fundamental parameters: the number of robots, and the objective target. We develop a new approach to establish the fixed-parameter tractability of both problems under the former parameterization that relies on novel structural insights into optimal solutions to the problem. When parameterized by the objective target, we show that CMP-L remains fixed-parameter tractable while CMP-M becomes para-NP-hard. The latter result is noteworthy, not only because it improves the previously-known boundaries of intractability for the problem, but also because the underlying reduction allows us to establish - as a simpler case - the NP-hardness of the classical Vertex Disjoint and Edge Disjoint Paths problems with constant path-lengths on grids.
Cite as

Eduard Eiben, Robert Ganian, and Iyad Kanj. The Parameterized Complexity of Coordinated Motion Planning. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 28:1-28:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{eiben_et_al:LIPIcs.SoCG.2023.28,
  author =	{Eiben, Eduard and Ganian, Robert and Kanj, Iyad},
  title =	{{The Parameterized Complexity of Coordinated Motion Planning}},
  booktitle =	{39th International Symposium on Computational Geometry (SoCG 2023)},
  pages =	{28:1--28:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-273-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{258},
  editor =	{Chambers, Erin W. and Gudmundsson, Joachim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.28},
  URN =		{urn:nbn:de:0030-drops-178784},
  doi =		{10.4230/LIPIcs.SoCG.2023.28},
  annote =	{Keywords: coordinated motion planning, multi-agent path finding, parameterized complexity, disjoint paths on grids}
}
Document
DOI: 10.4230/LIPIcs.ESA.2022.47
Finding a Cluster in Incomplete Data

Authors: Eduard Eiben, Robert Ganian, Iyad Kanj, Sebastian Ordyniak, and Stefan Szeider

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

Abstract
We study two variants of the fundamental problem of finding a cluster in incomplete data. In the problems under consideration, we are given a multiset of incomplete d-dimensional vectors over the binary domain and integers k and r, and the goal is to complete the missing vector entries so that the multiset of complete vectors either contains (i) a cluster of k vectors of radius at most r, or (ii) a cluster of k vectors of diameter at most r. We give tight characterizations of the parameterized complexity of the problems under consideration with respect to the parameters k, r, and a third parameter that captures the missing vector entries.
Cite as

Eduard Eiben, Robert Ganian, Iyad Kanj, Sebastian Ordyniak, and Stefan Szeider. Finding a Cluster in Incomplete Data. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 47:1-47:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{eiben_et_al:LIPIcs.ESA.2022.47,
  author =	{Eiben, Eduard and Ganian, Robert and Kanj, Iyad and Ordyniak, Sebastian and Szeider, Stefan},
  title =	{{Finding a Cluster in Incomplete Data}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{47:1--47: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.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.47},
  URN =		{urn:nbn:de:0030-drops-169858},
  doi =		{10.4230/LIPIcs.ESA.2022.47},
  annote =	{Keywords: Parameterized complexity, incomplete data, clustering}
}
Document
DOI: 10.4230/LIPIcs.STACS.2022.21
Near-Optimal Algorithms for Point-Line Covering Problems

Authors: Jianer Chen, Qin Huang, Iyad Kanj, and Ge Xia

Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)

Abstract
We study fundamental point-line covering problems in computational geometry, in which the input is a set S of points in the plane. The first is the Rich Lines problem, which asks for the set of all lines that each covers at least λ points from S, for a given integer parameter λ ≥ 2; this problem subsumes the 3-Points-on-Line problem and the Exact Fitting problem, which - the latter - asks for a line containing the maximum number of points. The second is the NP-hard problem Line Cover, which asks for a set of k lines that cover the points of S, for a given parameter k ∈ ℕ. Both problems have been extensively studied. In particular, the Rich Lines problem is a fundamental problem whose solution serves as a building block for several algorithms in computational geometry. For Rich Lines and Exact Fitting, we present a randomized Monte Carlo algorithm that achieves a lower running time than that of Guibas et al.’s algorithm [Computational Geometry 1996], for a wide range of the parameter λ. We derive lower-bound results showing that, for λ = Ω(√{n log n}), the upper bound on the running time of this randomized algorithm matches the lower bound that we derive on the time complexity of Rich Lines in the algebraic computation trees model. For Line Cover, we present two kernelization algorithms: a randomized Monte Carlo algorithm and a deterministic algorithm. Both algorithms improve the running time of existing kernelization algorithms for Line Cover. We derive lower-bound results showing that the running time of the randomized algorithm we present comes close to the lower bound we derive on the time complexity of kernelization algorithms for Line Cover in the algebraic computation trees model.
Cite as

Jianer Chen, Qin Huang, Iyad Kanj, and Ge Xia. Near-Optimal Algorithms for Point-Line Covering Problems. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 21:1-21:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.STACS.2022.21,
  author =	{Chen, Jianer and Huang, Qin and Kanj, Iyad and Xia, Ge},
  title =	{{Near-Optimal Algorithms for Point-Line Covering Problems}},
  booktitle =	{39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)},
  pages =	{21:1--21:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-222-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{219},
  editor =	{Berenbrink, Petra and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.21},
  URN =		{urn:nbn:de:0030-drops-158312},
  doi =		{10.4230/LIPIcs.STACS.2022.21},
  annote =	{Keywords: line cover, rich lines, exact fitting, kernelization, randomized algorithms, complexity lower bounds, algebraic computation trees}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2021.48
Streaming Algorithms for Graph k-Matching with Optimal or Near-Optimal Update Time

Authors: Jianer Chen, Qin Huang, Iyad Kanj, Qian Li, and Ge Xia

Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)

Abstract
We present streaming algorithms for the graph k-matching problem in both the insert-only and dynamic models. Our algorithms, while keeping the space complexity matching the best known upper bound, have optimal or near-optimal update time, significantly improving on previous results. More specifically, for the insert-only streaming model, we present a one-pass randomized algorithm that runs in optimal 𝒪(k²) space and has optimal 𝒪(1) update time, and that, w.h.p. (with high probability), computes a maximum weighted k-matching of a weighted graph. Previously, the best upper bound on the update time was 𝒪(log k), which was achieved by a deterministic streaming algorithm that however only works for unweighted graphs [Stefan Fafianie and Stefan Kratsch, 2014]. For the dynamic streaming model, we present a one-pass randomized algorithm that, w.h.p., computes a maximum weighted k-matching of a weighted graph in Õ(Wk²) space and with Õ(1) update time, where W is the number of distinct edge weights. Again the update time of our algorithm improves the previous best upper bound Õ(k²) [Rajesh Chitnis et al., 2016]. Moreover, we prove that in the dynamic streaming model, any randomized streaming algorithm for the problem requires k²⋅ Ω(W(log W+1)) bits of space. Hence, both the space and update-time complexities achieved by our algorithm in the dynamic model are near-optimal. A streaming approximation algorithm for k-matching is also presented, whose space complexity matches the best known upper bound with a significantly improved update time.
Cite as

Jianer Chen, Qin Huang, Iyad Kanj, Qian Li, and Ge Xia. Streaming Algorithms for Graph k-Matching with Optimal or Near-Optimal Update Time. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 48:1-48:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.ISAAC.2021.48,
  author =	{Chen, Jianer and Huang, Qin and Kanj, Iyad and Li, Qian and Xia, Ge},
  title =	{{Streaming Algorithms for Graph k-Matching with Optimal or Near-Optimal Update Time}},
  booktitle =	{32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
  pages =	{48:1--48:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-214-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{212},
  editor =	{Ahn, Hee-Kap and Sadakane, Kunihiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.48},
  URN =		{urn:nbn:de:0030-drops-154816},
  doi =		{10.4230/LIPIcs.ISAAC.2021.48},
  annote =	{Keywords: streaming algorithms, matching, parameterized algorithms, lower bounds}
}
Document
DOI: 10.4230/LIPIcs.STACS.2020.13
On Covering Segments with Unit Intervals

Authors: Dan Bergren, Eduard Eiben, Robert Ganian, and Iyad Kanj

Published in: LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)

Abstract
We study the problem of covering a set of segments on a line with the minimum number of unit-length intervals, where an interval covers a segment if at least one of the two endpoints of the segment falls in the unit interval. We also study several variants of this problem. We show that the restrictions of the aforementioned problems to the set of instances in which all the segments have the same length are NP-hard. This result implies several NP-hardness results in the literature for variants and generalizations of the problems under consideration. We then study the parameterized complexity of the aforementioned problems. We provide tight results for most of them by showing that they are fixed-parameter tractable for the restrictions in which all the segments have the same length, and are W[1]-complete otherwise.
Cite as

Dan Bergren, Eduard Eiben, Robert Ganian, and Iyad Kanj. On Covering Segments with Unit Intervals. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 13:1-13:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{bergren_et_al:LIPIcs.STACS.2020.13,
  author =	{Bergren, Dan and Eiben, Eduard and Ganian, Robert and Kanj, Iyad},
  title =	{{On Covering Segments with Unit Intervals}},
  booktitle =	{37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)},
  pages =	{13:1--13:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-140-5},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{154},
  editor =	{Paul, Christophe and Bl\"{a}ser, Markus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.13},
  URN =		{urn:nbn:de:0030-drops-118741},
  doi =		{10.4230/LIPIcs.STACS.2020.13},
  annote =	{Keywords: Segment covering, unit intervals, NP-completeness, parameterized complexity}
}
Document
DOI: 10.4230/LIPIcs.ESA.2018.51
Solving Partition Problems Almost Always Requires Pushing Many Vertices Around

Authors: Iyad Kanj, Christian Komusiewicz, Manuel Sorge, and Erik Jan van Leeuwen

Published in: LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018)

Abstract
A fundamental graph problem is to recognize whether the vertex set of a graph G can be bipartitioned into sets A and B such that G[A] and G[B] satisfy properties Pi_A and Pi_B, respectively. This so-called (Pi_A,Pi_B)-Recognition problem generalizes amongst others the recognition of 3-colorable, bipartite, split, and monopolar graphs. A powerful algorithmic technique that can be used to obtain fixed-parameter algorithms for many cases of (Pi_A,Pi_B)-Recognition, as well as several other problems, is the pushing process. For bipartition problems, the process starts with an "almost correct" bipartition (A',B'), and pushes appropriate vertices from A' to B' and vice versa to eventually arrive at a correct bipartition. In this paper, we study whether (Pi_A,Pi_B)-Recognition problems for which the pushing process yields fixed-parameter algorithms also admit polynomial problem kernels. In our study, we focus on the first level above triviality, where Pi_A is the set of P_3-free graphs (disjoint unions of cliques, or cluster graphs), the parameter is the number of clusters in the cluster graph G[A], and Pi_B is characterized by a set H of connected forbidden induced subgraphs. We prove that, under the assumption that NP not subseteq coNP/poly, (Pi_A,Pi_B)-Recognition admits a polynomial kernel if and only if H contains a graph of order at most 2. In both the kernelization and the lower bound results, we make crucial use of the pushing process.
Cite as

Iyad Kanj, Christian Komusiewicz, Manuel Sorge, and Erik Jan van Leeuwen. Solving Partition Problems Almost Always Requires Pushing Many Vertices Around. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 51:1-51:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{kanj_et_al:LIPIcs.ESA.2018.51,
  author =	{Kanj, Iyad and Komusiewicz, Christian and Sorge, Manuel and van Leeuwen, Erik Jan},
  title =	{{Solving Partition Problems Almost Always Requires Pushing Many Vertices Around}},
  booktitle =	{26th Annual European Symposium on Algorithms (ESA 2018)},
  pages =	{51:1--51:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-081-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{112},
  editor =	{Azar, Yossi and Bast, Hannah 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.2018.51},
  URN =		{urn:nbn:de:0030-drops-95140},
  doi =		{10.4230/LIPIcs.ESA.2018.51},
  annote =	{Keywords: Fixed-parameter algorithms, Kernelization, Vertex-partition problems, Reduction rules, Cross-composition}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2018.48
How to Navigate Through Obstacles?

Authors: Eduard Eiben and Iyad Kanj

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract
Given a set of obstacles and two points in the plane, is there a path between the two points that does not cross more than k different obstacles? This is a fundamental problem that has undergone a tremendous amount of work by researchers in various areas, including computational geometry, graph theory, wireless computing, and motion planning. It is known to be NP-hard, even when the obstacles are very simple geometric shapes (e.g., unit-length line segments). The problem can be formulated and generalized into the following graph problem: Given a planar graph G whose vertices are colored by color sets, two designated vertices s, t in V(G), and k in N, is there an s-t path in G that uses at most k colors? If each obstacle is connected, the resulting graph satisfies the color-connectivity property, namely that each color induces a connected subgraph. We study the complexity and design algorithms for the above graph problem with an eye on its geometric applications. We prove a set of hardness results, among which a result showing that the color-connectivity property is crucial for any hope for fixed-parameter tractable (FPT) algorithms, as without it, the problem is W[SAT]-hard parameterized by k. Previous results only implied that the problem is W[2]-hard. A corollary of this result is that, unless W[2] = FPT, the problem cannot be approximated in FPT time to within a factor that is a function of k. By describing a generic plane embedding of the graph instances, we show that our hardness results translate to the geometric instances of the problem. We then focus on graphs satisfying the color-connectivity property. By exploiting the planarity of the graph and the connectivity of the colors, we develop topological results that allow us to prove that, for any vertex v, there exists a set of paths whose cardinality is upper bounded by a function of k, that "represents" the valid s-t paths containing subsets of colors from v. We employ these structural results to design an FPT algorithm for the problem parameterized by both k and the treewidth of the graph, and extend this result further to obtain an FPT algorithm for the parameterization by both k and the length of the path. The latter result generalizes and explains previous FPT results for various obstacle shapes, such as unit disks and fat regions.
Cite as

Eduard Eiben and Iyad Kanj. How to Navigate Through Obstacles?. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 48:1-48:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{eiben_et_al:LIPIcs.ICALP.2018.48,
  author =	{Eiben, Eduard and Kanj, Iyad},
  title =	{{How to Navigate Through Obstacles?}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{48:1--48:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.48},
  URN =		{urn:nbn:de:0030-drops-90528},
  doi =		{10.4230/LIPIcs.ICALP.2018.48},
  annote =	{Keywords: parameterized complexity and algorithms, motion planning, barrier coverage, barrier resilience, colored path, minimum constraint removal, planar graphs}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2016.42
On Existential MSO and its Relation to ETH

Authors: Robert Ganian, Ronald de Haan, Iyad Kanj, and Stefan Szeider

Published in: LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)

Abstract
Impagliazzo et al. proposed a framework, based on the logic fragment defining the complexity class SNP, to identify problems that are equivalent to k-CNF-Sat modulo subexponential-time reducibility (serf-reducibility). The subexponential-time solvability of any of these problems implies the failure of the Exponential Time Hypothesis (ETH). In this paper, we extend the framework of Impagliazzo et al., and identify a larger set of problems that are equivalent to k-CNF-Sat modulo serf-reducibility. We propose a complexity class, referred to as Linear Monadic NP, that consists of all problems expressible in existential monadic second order logic whose expressions have a linear measure in terms of a complexity parameter, which is usually the universe size of the problem. This research direction can be traced back to Fagin's celebrated theorem stating that NP coincides with the class of problems expressible in existential second order logic. Monadic NP, a well-studied class in the literature, is the restriction of the aforementioned logic fragment to existential monadic second order logic. The proposed class Linear Monadic NP is then the restriction of Monadic NP to problems whose expressions have linear measure in the complexity parameter. We show that Linear Monadic NP includes many natural complete problems such as the satisfiability of linear-size circuits, dominating set, independent dominating set, and perfect code. Therefore, for any of these problems, its subexponential-time solvability is equivalent to the failure of ETH. We prove, using logic games, that the aforementioned problems are inexpressible in the monadic fragment of SNP, and hence, are not captured by the framework of Impagliazzo et al. Finally, we show that Feedback Vertex Set is inexpressible in existential monadic second order logic, and hence is not in Linear Monadic NP, and investigate the existence of certain reductions between Feedback Vertex Set (and variants of it) and 3-CNF-Sat.
Cite as

Robert Ganian, Ronald de Haan, Iyad Kanj, and Stefan Szeider. On Existential MSO and its Relation to ETH. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 42:1-42:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{ganian_et_al:LIPIcs.MFCS.2016.42,
  author =	{Ganian, Robert and de Haan, Ronald and Kanj, Iyad and Szeider, Stefan},
  title =	{{On Existential MSO and its Relation to ETH}},
  booktitle =	{41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
  pages =	{42:1--42:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-016-3},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{58},
  editor =	{Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.42},
  URN =		{urn:nbn:de:0030-drops-64556},
  doi =		{10.4230/LIPIcs.MFCS.2016.42},
  annote =	{Keywords: exponential time hypothesis (ETH), monadic second order logic, subexponential time complexity, serf-reducibility, logic games}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2016.14
Parameterized Algorithms for Recognizing Monopolar and 2-Subcolorable Graphs

Authors: Iyad Kanj, Christian Komusiewicz, Manuel Sorge, and Erik Jan van Leeuwen

Published in: LIPIcs, Volume 53, 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)

Abstract
We consider the recognition problem for two graph classes that generalize split and unipolar graphs, respectively. First, we consider the recognizability of graphs that admit a monopolar partition: a partition of the vertex set into sets A,B such that G[A] is a disjoint union of cliques and G[B] an independent set. If in such a partition G[A] is a single clique, then G is a split graph. We show that in O(2^k * k^3 * (|V(G)| + |E(G)|)) time we can decide whether G admits a monopolar partition (A,B) where G[A] has at most k cliques. This generalizes the linear-time algorithm for recognizing split graphs corresponding to the case when k=1. Second, we consider the recognizability of graphs that admit a 2-subcoloring: a partition of the vertex set into sets A,B such that each of G[A] and G[B] is a disjoint union of cliques. If in such a partition G[A] is a single clique, then G is a unipolar graph. We show that in O(k^(2k+2) * (|V(G)|^2+|V(G)| * |E(G)|)) time we can decide whether G admits a 2-subcoloring (A,B) where G[A] has at most k cliques. This generalizes the polynomial-time algorithm for recognizing unipolar graphs corresponding to the case when k=1. We also show that in O(4^k) time we can decide whether G admits a 2-subcoloring (A,B) where G[A] and G[B] have at most k cliques in total. To obtain the first two results above, we formalize a technique, which we dub inductive recognition, that can be viewed as an adaptation of iterative compression to recognition problems. We believe that the formalization of this technique will prove useful in general for designing parameterized algorithms for recognition problems. Finally, we show that, unless the Exponential Time Hypothesis fails, no subexponential-time algorithms for the above recognition problems exist, and that, unless P=NP, no generic fixed-parameter algorithm exists for the recognizability of graphs whose vertex set can be bipartitioned such that one part is a disjoint union of k cliques.
Cite as

Iyad Kanj, Christian Komusiewicz, Manuel Sorge, and Erik Jan van Leeuwen. Parameterized Algorithms for Recognizing Monopolar and 2-Subcolorable Graphs. In 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 53, pp. 14:1-14:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{kanj_et_al:LIPIcs.SWAT.2016.14,
  author =	{Kanj, Iyad and Komusiewicz, Christian and Sorge, Manuel and Jan van Leeuwen, Erik},
  title =	{{Parameterized Algorithms for Recognizing Monopolar and 2-Subcolorable Graphs}},
  booktitle =	{15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)},
  pages =	{14:1--14:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-011-8},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{53},
  editor =	{Pagh, Rasmus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2016.14},
  URN =		{urn:nbn:de:0030-drops-60360},
  doi =		{10.4230/LIPIcs.SWAT.2016.14},
  annote =	{Keywords: vertex-partition problems, monopolar graphs, subcolorings, split graphs, unipolar graphs, fixed-parameter algorithms}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2016.45
Degree Four Plane Spanners: Simpler and Better

Authors: Iyad Kanj, Ljubomir Perkovic, and Duru Türkoglu

Published in: LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016)

Abstract
Let P be a set of n points embedded in the plane, and let C be the complete Euclidean graph whose point-set is P. Each edge in C between two points p, q is realized as the line segment [pq], and is assigned a weight equal to the Euclidean distance |pq|. In this paper, we show how to construct in O(nlg{n}) time a plane spanner of C of maximum degree at most 4 and of stretch factor at most 20. This improves a long sequence of results on the construction of bounded degree plane spanners of C. Our result matches the smallest known upper bound of 4 by Bonichon et al. on the maximum degree while significantly improving their stretch factor upper bound from 156.82 to 20. The construction of our spanner is based on Delaunay triangulations defined with respect to the equilateral-triangle distance, and uses a different approach than that used by Bonichon et al. Our approach leads to a simple and intuitive construction of a well-structured spanner, and reveals useful structural properties of the Delaunay triangulations defined with respect to the equilateral-triangle distance.
Cite as

Iyad Kanj, Ljubomir Perkovic, and Duru Türkoglu. Degree Four Plane Spanners: Simpler and Better. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 45:1-45:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{kanj_et_al:LIPIcs.SoCG.2016.45,
  author =	{Kanj, Iyad and Perkovic, Ljubomir and T\"{u}rkoglu, Duru},
  title =	{{Degree Four Plane Spanners: Simpler and Better}},
  booktitle =	{32nd International Symposium on Computational Geometry (SoCG 2016)},
  pages =	{45:1--45:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-009-5},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{51},
  editor =	{Fekete, S\'{a}ndor and Lubiw, Anna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.45},
  URN =		{urn:nbn:de:0030-drops-59376},
  doi =		{10.4230/LIPIcs.SoCG.2016.45},
  annote =	{Keywords: Nonnumerical Algorithms and Problems,Computational Geometry and Object Modeling}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.IPEC.2015
LIPIcs, Volume 43, IPEC'15, Complete Volume

Authors: Thore Husfeldt and Iyad Kanj

Published in: LIPIcs, Volume 43, 10th International Symposium on Parameterized and Exact Computation (IPEC 2015)

Abstract
LIPIcs, Volume 43, IPEC'15, Complete Volume
Cite as

Thore Husfeldt and Iyad Kanj. LIPIcs, Volume 43, IPEC'15, Complete Volume. In 10th International Symposium on Parameterized and Exact Computation (IPEC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 43, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@Proceedings{husfeldt_et_al:LIPIcs.IPEC.2015,
  title =	{{LIPIcs, Volume 43, IPEC'15, Complete Volume}},
  booktitle =	{10th International Symposium on Parameterized and Exact Computation (IPEC 2015)},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-92-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{43},
  editor =	{Husfeldt, Thore and Kanj, Iyad},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2015},
  URN =		{urn:nbn:de:0030-drops-56020},
  doi =		{10.4230/LIPIcs.IPEC.2015},
  annote =	{Keywords: Complexity Measures and Classes, Analysis of Algorithms and Problem Complexity, Discrete Mathematics}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.IPEC.2015.i
Front Matter, Table of Contents, Preface, Program Committee, External Reviewers, List of Authors

Authors: Thore Husfeldt and Iyad Kanj

Published in: LIPIcs, Volume 43, 10th International Symposium on Parameterized and Exact Computation (IPEC 2015)

Abstract
Front Matter, Table of Contents, Preface, Program Committee, External Reviewers, List of Authors
Cite as

Thore Husfeldt and Iyad Kanj. Front Matter, Table of Contents, Preface, Program Committee, External Reviewers, List of Authors. In 10th International Symposium on Parameterized and Exact Computation (IPEC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 43, pp. i-xiv, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{husfeldt_et_al:LIPIcs.IPEC.2015.i,
  author =	{Husfeldt, Thore and Kanj, Iyad},
  title =	{{Front Matter, Table of Contents, Preface, Program Committee, External Reviewers, List of Authors}},
  booktitle =	{10th International Symposium on Parameterized and Exact Computation (IPEC 2015)},
  pages =	{i--xiv},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-92-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{43},
  editor =	{Husfeldt, Thore and Kanj, Iyad},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2015.i},
  URN =		{urn:nbn:de:0030-drops-55676},
  doi =		{10.4230/LIPIcs.IPEC.2015.i},
  annote =	{Keywords: IPEC}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.IPEC.2015.1
Bidimensionality and Parameterized Algorithms (Invited Talk)

Authors: Dimitrios M. Thilikos

Published in: LIPIcs, Volume 43, 10th International Symposium on Parameterized and Exact Computation (IPEC 2015)

Abstract
We provide an exposition of the main results of the theory of bidimensionality in parameterized algorithm design. This theory applies to graph problems that are bidimensional in the sense that i) their solution value is not increasing when we take minors or contractions of the input graph and ii) their solution value for the (triangulated) (k x k)-grid graph grows as a quadratic function of k. Under certain additional conditions, mainly of logical and combinatorial nature, such problems admit subexponential parameterized algorithms and linear kernels when their inputs are restricted to certain topologically defined graph classes. We provide all formal definitions and concepts in order to present these results in a rigorous way and in their latest update.
Cite as

Dimitrios M. Thilikos. Bidimensionality and Parameterized Algorithms (Invited Talk). In 10th International Symposium on Parameterized and Exact Computation (IPEC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 43, pp. 1-16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{thilikos:LIPIcs.IPEC.2015.1,
  author =	{Thilikos, Dimitrios M.},
  title =	{{Bidimensionality and Parameterized Algorithms}},
  booktitle =	{10th International Symposium on Parameterized and Exact Computation (IPEC 2015)},
  pages =	{1--16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-92-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{43},
  editor =	{Husfeldt, Thore and Kanj, Iyad},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2015.1},
  URN =		{urn:nbn:de:0030-drops-55663},
  doi =		{10.4230/LIPIcs.IPEC.2015.1},
  annote =	{Keywords: Parameterized algorithms, Subexponential FPT-algorithms, Kernelization, Linear kenrels, Bidimensionality, Graph Minors}
}
  • Refine by Author
  • 13 Kanj, Iyad
  • 5 Eiben, Eduard
  • 5 Ganian, Robert
  • 4 Kim, Eun Jung
  • 4 Xia, Ge
  • Show More...

  • Refine by Classification
  • 7 Theory of computation → Parameterized complexity and exact algorithms
  • 3 Theory of computation → Computational geometry
  • 2 Mathematics of computing → Graph algorithms
  • 1 Theory of computation → Algorithm design techniques
  • 1 Theory of computation → Streaming, sublinear and near linear time algorithms

  • Refine by Keyword
  • 9 parameterized complexity
  • 5 kernelization
  • 4 Kernelization
  • 4 Parameterized Complexity
  • 4 parameterized algorithms
  • Show More...

  • Refine by Type
  • 50 document
  • 1 volume

  • Refine by Publication Year
  • 38 2015
  • 3 2016
  • 2 2008
  • 2 2018
  • 2 2022
  • 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 Schloss Dagstuhl - LZI GmbH Imprint Privacy Contact