Author name cluster

Iyad Kanj

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

13 papers

1 author row

AAMAS Conference 2025 Conference Paper

Parameterized Algorithms for Multiagent Pathfinding on Trees

Argyrios Deligkas
Eduard Eiben
Robert Ganian
Iyad Kanj
M. S. Ramanujan

The classical Multiagent Pathfinding problem has been extensively studied not only within the artificial intelligence research community, but also by scholars in the areas of theoretical computer science and computational geometry. The problem asks for a minimum-makespan schedule that routes 𝑘 agents (or robots) from their starting points to their destinations in a graph, while avoiding collisions, and is known to be NP-hard even on the fundamental class of trees. In this article we present two fixed parameter algorithms parameterized by 𝑘: the first yields a collision-free schedule on trees whose makespan deviates from the optimum by at most an additive polynomial function of 𝑘, and the second solves Multiagent Pathfinding optimally on the class of irreducible trees, i. e. , trees with no vertices of degree 2. Both results rely on novel tools and insights into the properties of optimal schedules.

PDF

AAAI Conference 2021 Conference Paper

The Parameterized Complexity of Clustering Incomplete Data

Eduard Eiben
Robert Ganian
Iyad Kanj
Sebastian Ordyniak
Stefan Szeider

We study fundamental clustering problems for incomplete data. Specifically, given a set of incomplete d-dimensional vectors (representing rows of a matrix), the goal is to complete the missing vector entries in a way that admits a partitioning of the vectors into at most k clusters with radius or diameter at most r. We give tight characterizations of the parameterized complexity of these problems with respect to the parameters k, r, and the minimum number of rows and columns needed to cover all the missing entries. We show that the considered problems are fixed-parameter tractable when parameterized by the three parameters combined, and that dropping any of the three parameters results in parameterized intractability. A byproduct of our results is that, for the complete data setting, all problems under consideration are fixed-parameter tractable parameterized by k + r.

PDF Details

AAAI Conference 2020 Conference Paper

On the Parameterized Complexity of Clustering Incomplete Data into Subspaces of Small Rank

Robert Ganian
Iyad Kanj
Sebastian Ordyniak
Stefan Szeider

We consider a fundamental matrix completion problem where we are given an incomplete matrix and a set of constraints modeled as a CSP instance. The goal is to complete the matrix subject to the input constraints and in such a way that the complete matrix can be clustered into few subspaces with low rank. This problem generalizes several problems in data mining and machine learning, including the problem of completing a matrix into one with minimum rank. In addition to its ubiquitous applications in machine learning, the problem has strong connections to information theory, related to binary linear codes, and variants of it have been extensively studied from that perspective. We formalize the problem mentioned above and study its classical and parameterized complexity. We draw a detailed landscape of the complexity and parameterized complexity of the problem with respect to several natural parameters that are desirably small and with respect to several well-studied CSP fragments.

PDF Details

AAAI Conference 2020 Conference Paper

On the Problem of Covering a 3-D Terrain

Eduard Eiben
Isuru Godage
Iyad Kanj
Ge Xia

We study the problem of covering a 3-dimensional terrain by a sweeping robot that is equipped with a camera. We model the terrain as a mesh in a way that captures the elevation levels of the terrain; this enables a graph-theoretic formulation of the problem in which the underlying graph is a weighted plane graph. We show that the associated graph problem is NP-hard, and that it admits a polynomial time approximation scheme (PTAS). Finally, we implement two heuristic algorithms based on greedy approaches and report our ﬁndings.

PDF Details

NeurIPS Conference 2019 Conference Paper

The Parameterized Complexity of Cascading Portfolio Scheduling

Eduard Eiben
Robert Ganian
Iyad Kanj
Stefan Szeider

Cascading portfolio scheduling is a static algorithm selection strategy which uses a sample of test instances to compute an optimal ordering (a cascading schedule) of a portfolio of available algorithms. The algorithms are then applied to each future instance according to this cascading schedule, until some algorithm in the schedule succeeds. Cascading algorithm scheduling has proven to be effective in several applications, including QBF solving and the generation of ImageNet classification models. It is known that the computation of an optimal cascading schedule in the offline phase is NP-hard. In this paper we study the parameterized complexity of this problem and establish its fixed-parameter tractability by utilizing structural properties of the success relation between algorithms and test instances. Our findings are significant as they reveal that in spite of the intractability of the problem in its general form, one can indeed exploit sparseness or density of the success relation to obtain non-trivial runtime guarantees for finding an optimal cascading schedule.

PDF Details

AAAI Conference 2018 Conference Paper

Improved Results for Minimum Constraint Removal

Eduard Eiben
Jonathan Gemmell
Iyad Kanj
Andrew Youngdahl

Given a set of obstacles and two designated points in the plane, the MINIMUM CONSTRAINT REMOVAL problem asks for a minimum number of obstacles that can be removed so that a collision-free path exists between the two designated points. It is a well-studied problem in both robotic motion planning and wireless computing that has been shown to be NP-hard in various settings. In this work, we extend the study of MINIMUM CONSTRAINT REMOVAL. We start by presenting reﬁned NP-hardness reductions for the two cases: (1) when all the obstacles are axes-parallel rectangles, and (2) when all the obstacles are line segments such that no three intersect at the same point. These results improve on existing results in the literature. As a byproduct of our NP-hardness reductions, we prove that, unless the Exponential-Time Hypothesis (ETH) fails, MIN- IMUM CONSTRAINT REMOVAL cannot be solved in subexponential time 2o(n), where n is the number of obstacles in the instance. This shows that signiﬁcant improvement on the brute-force 2O(n) -time algorithm is unlikely. We then present a subexponential-time algorithm for instances of MINIMUM CONSTRAINT REMOVAL in which the number of obstacles that overlap at any point is constant; the algorithm runs in time 2O( √ N), where N is the number of the vertices in the auxiliary graph associated with the instance of the problem. We show that signiﬁcant improvement on this algorithm is unlikely by showing that, unless ETH fails, MIN- IMUM CONSTRAINT REMOVAL with bounded overlap number cannot be solved in time 2o( √ N). We describe several exact algorithms and approximation algorithms that leverage heuristics and discuss their performance in an extensive empirical simulation.

PDF Details

I&C Journal 2017 Journal Article

On the parameterized complexity of monotone and antimonotone weighted circuit satisfiability

Iyad Kanj
Dimitrios M. Thilikos
Ge Xia

We consider the weighted monotone and antimonotone satisfiability problems on normalized circuits of depth at most t ≥ 2, abbreviated Image 1 and Image 2, respectively, where the parameter under consideration is the weight of the sought satisfying assignment. These problems model the weighted satisfiability of monotone and antimonotone propositional formulas, and serve as the canonical problems in the definition of the parameterized complexity hierarchy. Moreover, several well-studied problems, including important graph problems, can be modeled as Image 1 and Image 2 problems in a straightforward manner. We study the parameterized complexity of Image 2 and Image 1 with respect to the genus of the underlying circuit. We give tight results, and draw a map of the parameterized complexity of these problems with respect to the genus of the circuit. As a byproduct of our results, we obtain tight characterizations of the parameterized complexity of several problems with respect to the genus of the underlying graph.

Details DOI

TCS Journal 2015 Journal Article

Improved parameterized and exact algorithms for cut problems on trees

Iyad Kanj
Guohui Lin
Tian Liu
Weitian Tong
Ge Xia
Jinhui Xu
Boting Yang
Fenghui Zhang

We study the Multicut on Trees and the Generalized Multiway Cut on Trees problems. For the Multicut on Trees problem, we present a parameterized algorithm that runs in time O ⁎ ( ρ k ), where ρ = 2 + 1 < 1. 554 is the positive root of the polynomial x 4 − 2 x 2 − 1. This improves the current-best algorithm of Chen et al. that runs in time O ⁎ ( 1. 619 k ). For the Generalized Multiway Cut on Trees problem, we show that this problem is solvable in polynomial time if the number of terminal sets is fixed; this answers an open question posed in a recent paper by Liu and Zhang. By reducing the Generalized Multiway Cut on Trees problem to the Multicut on Trees problem, our results give a parameterized algorithm that solves the Generalized Multiway Cut on Trees problem in time O ⁎ ( ρ k ).

Details DOI

JAIR Journal 2015 Journal Article

On the Subexponential-Time Complexity of CSP

Ronald de Haan
Iyad Kanj
Stefan Szeider

Not all NP-complete problems share the same practical hardness with respect to exact computation. Whereas some NP-complete problems are amenable to efficient computational methods, others are yet to show any such sign. It becomes a major challenge to develop a theoretical framework that is more fine-grained than the theory of NP-completeness, and that can explain the distinction between the exact complexities of various NP-complete problems. This distinction is highly relevant for constraint satisfaction problems under natural restrictions, where various shades of hardness can be observed in practice. Acknowledging the NP-hardness of such problems, one has to look beyond polynomial time computation. The theory of subexponential-time complexity provides such a framework, and has been enjoying increasing popularity in complexity theory. An instance of the constraint satisfaction problem with n variables over a domain of d values can be solved by brute-force in d n steps (omitting a polynomial factor). In this paper we study the existence of subexponential-time algorithms, that is, algorithms running in d o(n) steps, for various natural restrictions of the constraint satisfaction problem. We consider both the constraint satisfaction problem in which all the constraints are given extensionally as tables, and that in which all the constraints are given intensionally in the form of global constraints. We provide tight characterizations of the subexponential-time complexity of the aforementioned problems with respect to several natural structural parameters, which allows us to draw a detailed landscape of the subexponential-time complexity of the constraint satisfaction problem. Our analysis provides fundamental results indicating whether and when one can significantly improve on the brute-force search approach for solving the constraint satisfaction problem.

PDF Details DOI

TCS Journal 2015 Journal Article

Parameterized and subexponential-time complexity of satisfiability problems and applications

Iyad Kanj
Stefan Szeider

We study the parameterized and the subexponential-time complexity of the weighted and the unweighted satisfiability problems on bounded-depth normalized Boolean circuits. We establish relations between the subexponential-time complexity of the weighted and the unweighted satisfiability problems, and use them to derive relations among the subexponential-time complexity of several NP-hard problem. We then study the role of certain natural structural parameters of the circuit in characterizing the parameterized and the subexponential-time complexity of the circuit satisfiability problems under consideration. We obtain threshold functions on some circuit structural parameters, including the depth, the number of gates, the fan-in, and the maximum number of (variable) occurrences, that lead to tight characterizations of the parameterized and the subexponential-time complexity of the circuit satisfiability problems under consideration.

Details DOI

TCS Journal 2013 Journal Article

On the independence number of graphs with maximum degree 3

Iyad Kanj
Fenghui Zhang

Let G be an undirected graph with maximum degree at most 3 such that G does not contain any of the three graphs given in the paper as a subgraph. We prove that the independence number of G is at least n ( G ) / 3 + n t ( G ) / 42, where n ( G ) is the number of vertices in G and n t ( G ) is the number of nontriangle vertices in G. This bound is tight as implied by the well-known tight lower bound of 5 n ( G ) / 14 on the independence number of triangle-free graphs of maximum degree at most 3. We show some algorithmic applications of the aforementioned combinatorial result to the area of parameterized complexity. We present a linear-time kernelization algorithm for the independent set problem on graphs with maximum degree at most 3 that computes a kernel of size at most 140 k / 47 < 3 k, where k is the given parameter. This improves the known 3 k upper bound on the kernel size for the problem, and implies a 140 k / 93 lower bound on the kernel size for the vertex cover problem on graphs with maximum degree at most 3.

Details DOI

AAAI Conference 2013 Conference Paper

On the Subexponential Time Complexity of CSP

Iyad Kanj
Stefan Szeider

A Constraint Satisfaction Problem (CSP) with n variables ranging over a domain of d values can be solved by brute-force in dn steps (omitting a polynomial factor). With a more careful approach, this trivial upper bound can be improved for certain natural restrictions of the CSP. In this paper we establish theoretical limits to such improvements, and draw a detailed landscape of the subexponential-time complexity of CSP. We first establish relations between the subexponentialtime complexity of CSP and that of other problems, including CNF-SAT. We exploit this connection to provide tight characterizations of the subexponential-time complexity of CSP under common assumptions in complexity theory. For several natural CSP parameters, we obtain threshold functions that precisely dictate the subexponential-time complexity of CSP with respect to the parameters under consideration. Our analysis provides fundamental results indicating whether and when one can significantly improve on the brute-force search approach for solving CSP.

PDF Details

TCS Journal 2002 Journal Article

The inapproximability of non-NP-hard optimization problems

Liming Cai
David Juedes
Iyad Kanj

The inapproximability of non-NP-hard optimization problems is investigated. Techniques are given to show that the problems LOG DOMINATING SET and LOG HYPERGRAPH VERTEX COVER cannot be approximated to a constant ratio in polynomial time unless the corresponding NP-hard versions are also approximable in deterministic subexponential time. A direct connection is established between non-NP-hard problems and a PCP characterization of NP. Reductions from the PCP characterization show that LOG CLIQUE is not approximable in polynomial time and MAX SPARSE SAT does not have a FPTAS under the assumption that NP⊈DTIME(2 O( n log n)). A number of nontrivial approximation-preserving reductions are also presented, making it possible to extend inapproximability results to more natural non-NP-hard problems such as TOURNAMENT DOMINATING SET and RICH HYPERGRAPH VERTEX COVER.

Details DOI