Source author record

Amer E. Mouawad

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms Computational Complexity Discrete Mathematics math.CO Distributed, Parallel, and Cluster Computing Logic in Computer Science math.LO

Catalog footprint

Research overview

14works

7topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

A survey on the parameterized complexity of the independent set and (connected) dominating set reconfiguration problems

A graph vertex-subset problem defines which subsets of the vertices of an input graph are feasible solutions. We view a feasible solution as a set of tokens placed on the vertices of the graph. A reconfiguration variant of a vertex-subset problem asks, given two feasible solutions of size $k$ , whether it is possible to transform one into the other by a sequence of token slides (along edges of the graph) or token jumps (between arbitrary vertices of the graph) such that each intermediate set remains a feasible solution of size $k$ . Many algorithmic questions present themselves in the form of reconfiguration problems: Given the description of an initial system state and the description of a target state, is it possible to transform the system from its initial state into the target one while preserving certain properties of the system in the process? Such questions have received a substantial amount of attention under the so-called combinatorial reconfiguration framework. We consider reconfiguration variants of three fundamental underlying graph vertex-subset problems, namely Independent Set, Dominating Set, and Connected Dominating Set. We survey both older and more recent work on the parameterized complexity of all three problems when parameterized by the number of tokens $k$ . The emphasis will be on positive results and the most common techniques for the design of fixed-parameter tractable algorithms.

preprint2022arXiv

Combinatorial and Algorithmic Aspects of Monadic Stability

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. - In monadically stable classes the Ramsey numbers $R(s,t)$ are bounded from above by $\mathcal{O}(t^{s-1-δ})$ for some $δ>0$ , improving the bound $R(s,t)\in \mathcal{O}(t^{s-1}/(\log t)^{s-1})$ known for general graphs and the bounds known for $k$ -stable graphs when $s\leq k$ . - For every monadically stable class $\mathcal{C}$ and every integer $r$ , there exists $δ> 0$ such that every graph $G \in \mathcal{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.

preprint2022arXiv

Galactic Token Sliding

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 $k$ -sized independent sets $I_s = I_0, I_1, I_2, \ldots, I_\ell = 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. A very fruitful line of research 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. 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 and interval graphs. 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.

preprint2022arXiv

On finding short reconfiguration sequences between independent sets

Assume we are given a graph $G$ , two independent sets $S$ and $T$ in $G$ of size $k \geq 1$ , and a positive integer $\ell \geq 1$ . The goal is to decide whether there exists a sequence $\langle I_0, I_1, ..., I_\ell \rangle$ of independent sets such that for all $j \in \{0,\ldots,\ell-1\}$ the set $I_j$ is an independent set of size $k$ , $I_0 = S$ , $I_\ell = T$ , and $I_{j+1}$ is obtained from $I_j$ by a predetermined reconfiguration rule. We consider two reconfiguration rules. 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 $\ell$ 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. 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. Both TSO and TJO are known to be fixed-parameter tractable when parameterized by $\ell$ on nowhere dense classes of graphs. In this work, we show that both problems are fixed-parameter tractable for parameter $k + \ell + d$ on $d$ -degenerate graphs as well as for parameter $|M| + \ell + Δ$ on graphs having a modulator $M$ whose deletion leaves a graph of maximum degree $Δ$ . We complement these result by showing that for parameter $\ell$ 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. Finally, we show that using such families one can obtain a simpler and unified algorithm for the standard Token Jumping Reachability problem parameterized by $k$ on both degenerate and nowhere dense classes of graphs.

preprint2022arXiv

Parallel Vertex Cover Algorithms on GPUs

Finding small vertex covers in a graph has applications in numerous domains. Two common formulations of the problem include: Minimum Vertex Cover, which finds the smallest vertex cover in a graph, and Parameterized Vertex Cover, which finds a vertex cover whose size is less than or equal to some parameter $k$ . Algorithms for both formulations traverse a search tree, which grows exponentially with the size of the graph or the value of $k$ . Parallelizing the traversal of the vertex cover search tree on GPUs is challenging for multiple reasons. First, the search tree is a narrow binary tree which makes it difficult to extract enough sub-trees to process in parallel to fully utilize the GPU's resources. Second, the search tree is highly imbalanced which makes load balancing across a massive number of parallel GPU workers challenging. Third, keeping around all the intermediate state needed to traverse many sub-trees in parallel puts high pressure on the GPU's memory resources and may act as a limiting factor to parallelism. To address these challenges, we propose an approach to traverse the vertex cover search tree in parallel using GPUs while handling dynamic load balancing. Each thread block traverses a different sub-tree using a local stack, however, we also use a global worklist to balance load. Blocks contribute branches of their sub-trees to the global worklist on an as-needed basis, while blocks that finish their sub-trees get new ones from the global worklist. We use degree arrays to represent intermediate graphs so that the representation is compact in memory to avoid limiting parallelism, but self-contained which is necessary for load balancing. Our evaluation shows that compared to prior work, our hybrid approach of using local stacks and a global worklist substantially improves performance and reduces load imbalance, especially on difficult instances of the problem.

preprint2015arXiv

Simultaneous Feedback Vertex Set: A Parameterized Perspective

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

preprint2015arXiv

The complexity of dominating set reconfiguration

Suppose that we are given two dominating sets $D_s$ and $D_t$ of a graph $G$ whose cardinalities are at most a given threshold $k$ . Then, we are asked whether there exists a sequence of dominating sets of $G$ between $D_s$ and $D_t$ such that each dominating set in the sequence is of cardinality at most $k$ and can be obtained from the previous one by either adding or deleting exactly one vertex. This problem is known to be PSPACE-complete in general. In this paper, we study the complexity of this decision problem from the viewpoint of graph classes. We first prove that the problem remains PSPACE-complete even for planar graphs, bounded bandwidth graphs, split graphs, and bipartite graphs. We then give a general scheme to construct linear-time algorithms and show that the problem can be solved in linear time for cographs, trees, and interval graphs. Furthermore, for these tractable cases, we can obtain a desired sequence such that the number of additions and deletions is bounded by $O(n)$ , where $n$ is the number of vertices in the input graph.

preprint2014arXiv

A Hybrid Graph Representation for Exact Graph Algorithms

Many exact search algorithms for NP-hard graph problems adopt the old Davis-Putman branch-and-reduce paradigm. The performance of these algorithms often suffers from the increasing number of graph modifications, such as vertex/edge deletions, that reduce the problem instance and have to be "taken back" frequently during the search process. We investigate practical implementation-based aspects of exact graph algorithms by providing a simple hybrid graph representation that trades space for time to address the said take-back challenge. Experiments on three well studied problems show consistent significant improvements over classical methods.

preprint2014arXiv

Reconfiguration of Dominating Sets

We explore a reconfiguration version of the dominating set problem, where a dominating set in a graph $G$ is a set $S$ of vertices such that each vertex is either in $S$ or has a neighbour in $S$ . In a reconfiguration problem, the goal is to determine whether there exists a sequence of feasible solutions connecting given feasible solutions $s$ and $t$ such that each pair of consecutive solutions is adjacent according to a specified adjacency relation. Two dominating sets are adjacent if one can be formed from the other by the addition or deletion of a single vertex. For various values of $k$ , we consider properties of $D_k(G)$ , the graph consisting of a vertex for each dominating set of size at most $k$ and edges specified by the adjacency relation. Addressing an open question posed by Haas and Seyffarth, we demonstrate that $D_{Γ(G)+1}(G)$ is not necessarily connected, for $Γ(G)$ the maximum cardinality of a minimal dominating set in $G$ . The result holds even when graphs are constrained to be planar, of bounded tree-width, or $b$ -partite for $b \ge 3$ . Moreover, we construct an infinite family of graphs such that $D_{γ(G)+1}(G)$ has exponential diameter, for $γ(G)$ the minimum size of a dominating set. On the positive side, we show that $D_{n-m}(G)$ is connected and of linear diameter for any graph $G$ on $n$ vertices having at least $m+1$ independent edges.

preprint2014arXiv

Reconfiguration over tree decompositions

A vertex-subset graph problem $Q$ defines which subsets of the vertices of an input graph are feasible solutions. The reconfiguration version of a vertex-subset problem $Q$ asks whether it is possible to transform one feasible solution for $Q$ into another in at most $\ell$ steps, where each step is a vertex addition or deletion, and each intermediate set is also a feasible solution for $Q$ of size bounded by $k$ . Motivated by recent results establishing W[1]-hardness of the reconfiguration versions of most vertex-subset problems parameterized by $\ell$ , we investigate the complexity of such problems restricted to graphs of bounded treewidth. We show that the reconfiguration versions of most vertex-subset problems remain PSPACE-complete on graphs of treewidth at most $t$ but are fixed-parameter tractable parameterized by $\ell + t$ for all vertex-subset problems definable in monadic second-order logic (MSOL). To prove the latter result, we introduce a technique which allows us to circumvent cardinality constraints and define reconfiguration problems in MSOL.

preprint2014arXiv

Shortest reconfiguration paths in the solution space of Boolean formulas

Given a Boolean formula and a satisfying assignment, a flip is an operation that changes the value of a variable in the assignment so that the resulting assignment remains satisfying. We study the problem of computing the shortest sequence of flips (if one exists) that transforms a given satisfying assignment $s$ to another satisfying assignment $t$ of a Boolean formula. Earlier work characterized the complexity of finding any (not necessarily the shortest) sequence of flips from one satisfying assignment to another using Schaefer's framework for classification of Boolean formulas. We build on it to provide a trichotomy for the complexity of finding the shortest sequence of flips and show that it is either in P, NP-complete, or PSPACE-complete. Our result adds to the small set of complexity results known for shortest reconfiguration sequence problems by providing an example where the shortest sequence can be found in polynomial time even though its length is not equal to the symmetric difference of the values of the variables in $s$ and $t$ . This is in contrast to all reconfiguration problems studied so far, where polynomial time algorithms for computing the shortest path were known only for cases where the path modified the symmetric difference only.

preprint2014arXiv

The Complexity of Bounded Length Graph Recoloring

We study the following question: Given are two $k$ -colorings $α$ and $β$ of a graph $G$ on $n$ vertices, and integer $\ell$ . The question is whether $α$ can be modified into $β$ , by recoloring vertices one at a time, while maintaining a $k$ -coloring throughout, and using at most $\ell$ such recoloring steps. This problem is weakly PSPACE-hard for every constant $k\ge 4$ . We show that it is also strongly NP-hard for every constant $k\ge 4$ . On the positive side, we give an $O(f(k,\ell) n^{O(1)})$ algorithm for the problem, for some computable function $f$ . Hence the problem is fixed-parameter tractable when parameterized by $k+\ell$ . Finally, we show that the problem is W[1]-hard (but in XP) when parameterized only by $\ell$ .

preprint2013arXiv

An Easy-to-use Scalable Framework for Parallel Recursive Backtracking

Supercomputers are equipped with an increasingly large number of cores to use computational power as a way of solving problems that are otherwise intractable. Unfortunately, getting serial algorithms to run in parallel to take advantage of these computational resources remains a challenge for several application domains. Many parallel algorithms can scale to only hundreds of cores. The limiting factors of such algorithms are usually communication overhead and poor load balancing. Solving NP-hard graph problems to optimality using exact algorithms is an example of an area in which there has so far been limited success in obtaining large scale parallelism. Many of these algorithms use recursive backtracking as their core solution paradigm. In this paper, we propose a lightweight, easy-to-use, scalable framework for transforming almost any recursive backtracking algorithm into a parallel one. Our framework incurs minimal communication overhead and guarantees a load-balancing strategy that is implicit, i.e., does not require any problem-specific knowledge. The key idea behind this framework is the use of an indexed search tree approach that is oblivious to the problem being solved. We test our framework with parallel implementations of algorithms for the well-known Vertex Cover and Dominating Set problems. On sufficiently hard instances, experimental results show linear speedups for thousands of cores, reducing running times from days to just a few minutes.

preprint2013arXiv

On the Parameterized Complexity of Reconfiguration Problems

We present the first results on the parameterized complexity of reconfiguration problems, where a reconfiguration version of an optimization problem $Q$ takes as input two feasible solutions $S$ and $T$ and determines if there is a sequence of {\em reconfiguration steps} that can be applied to transform $S$ into $T$ such that each step results in a feasible solution to $Q$ . For most of the results in this paper, $S$ and $T$ are subsets of vertices of a given graph and a reconfiguration step adds or deletes a vertex. Our study is motivated by recent results establishing that for most NP-hard problems, the classical complexity of reconfiguration is PSPACE-complete. We address the question for several important graph properties under two natural parameterizations: $k$ , the size of the solutions, and $\ell$ , the length of the sequence of steps. Our first general result is an algorithmic paradigm, the {\em reconfiguration kernel}, used to obtain fixed-parameter algorithms for the reconfiguration versions of {\sc Vertex Cover} and, more generally, {\sc Bounded Hitting Set} and {\sc Feedback Vertex Set}, all parameterized by $k$ . In contrast, we show that reconfiguring {\sc Unbounded Hitting Set} is $W[2]$ -hard when parameterized by $k+\ell$ . We also demonstrate the $W[1]$ -hardness of the reconfiguration versions of a large class of maximization problems parameterized by $k+\ell$ , and of their corresponding deletion problems parameterized by $\ell$ ; in doing so, we show that there exist problems in FPT when parameterized by $k$ , but whose reconfiguration versions are $W[1]$ -hard when parameterized by $k+\ell$ .

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Amer E. Mouawad

Research overview

Is this your work?

14 publications

A survey on the parameterized complexity of the independent set and (connected) dominating set reconfiguration problems

Combinatorial and Algorithmic Aspects of Monadic Stability

Galactic Token Sliding

On finding short reconfiguration sequences between independent sets

Parallel Vertex Cover Algorithms on GPUs

Simultaneous Feedback Vertex Set: A Parameterized Perspective

The complexity of dominating set reconfiguration

A Hybrid Graph Representation for Exact Graph Algorithms

Reconfiguration of Dominating Sets

Reconfiguration over tree decompositions

Shortest reconfiguration paths in the solution space of Boolean formulas

The Complexity of Bounded Length Graph Recoloring

An Easy-to-use Scalable Framework for Parallel Recursive Backtracking

On the Parameterized Complexity of Reconfiguration Problems

See the researcher in context

Building this map preview