Source author record

Nicolas El Maalouly

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

ResearcherUnclaimed source record

math.CO Computational Complexity Data Structures and Algorithms

Catalog footprint

Research overview

3works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2024arXiv

On the Exact Matching Problem in Dense Graphs

In the Exact Matching problem, we are given a graph whose edges are colored red or blue and the task is to decide for a given integer k, if there is a perfect matching with exactly k red edges. Since 1987 it is known that the Exact Matching Problem can be solved in randomized polynomial time. Despite numerous efforts, it is still not known today whether a deterministic polynomial-time algorithm exists as well. In this paper, we make substantial progress by solving the problem for a multitude of different classes of dense graphs. We solve the Exact Matching problem in deterministic polynomial time for complete r-partite graphs, for unit interval graphs, for bipartite unit interval graphs, for graphs of bounded neighborhood diversity, for chain graphs, and for graphs without a complete bipartite t-hole. We solve the problem in quasi-polynomial time for Erdős-Rényi random graphs G(n, 1/2). We also reprove an earlier result for bounded independence number/bipartite independence number. We use two main tools to obtain these results: A local search algorithm as well as a generalization of an earlier result by Karzanov.

preprint2022arXiv

Compatible Spanning Trees in Simple Drawings of $K_n$

For a simple drawing $D$ of the complete graph $K_n$ , two (plane) subdrawings are compatible if their union is plane. Let $\mathcal{T}_D$ be the set of all plane spanning trees on $D$ and $\mathcal{F}(\mathcal{T}_D)$ be the compatibility graph that has a vertex for each element in $\mathcal{T}_D$ and two vertices are adjacent if and only if the corresponding trees are compatible. We show, on the one hand, that $\mathcal{F}(\mathcal{T}_D)$ is connected if $D$ is a cylindrical, monotone, or strongly c-monotone drawing. On the other hand, we show that the subgraph of $\mathcal{F}(\mathcal{T}_D)$ induced by stars, double stars, and twin stars is also connected. In all cases the diameter of the corresponding compatibility graph is at most linear in $n$ .

preprint2022arXiv

Exact Matching in Graphs of Bounded Independence Number

In the Exact Matching Problem (EM), we are given a graph equipped with a fixed coloring of its edges with two colors (red and blue), as well as a positive integer $k$ . The task is then to decide whether the given graph contains a perfect matching exactly $k$ of whose edges have color red. EM generalizes several important algorithmic problems such as perfect matching and restricted minimum weight spanning tree problems. When introducing the problem in 1982, Papadimitriou and Yannakakis conjectured EM to be $\textbf{NP}$ -complete. Later however, Mulmuley et al.~presented a randomized polynomial time algorithm for EM, which puts EM in $\textbf{RP}$ . Given that to decide whether or not $\textbf{RP}=\textbf{P}$ represents a big open challenge in complexity theory, this makes it unlikely for EM to be $\textbf{NP}$ -complete, and in fact indicates the possibility of a deterministic polynomial time algorithm. EM remains one of the few natural combinatorial problems in $\textbf{RP}$ which are not known to be contained in $\textbf{P}$ , making it an interesting instance for testing the hypothesis $\textbf{RP}=\textbf{P}$ . Despite EM being quite well-known, attempts to devise deterministic polynomial algorithms have remained illusive during the last 40 years and progress has been lacking even for very restrictive classes of input graphs. In this paper we finally push the frontier of positive results forward by proving that EM can be solved in deterministic polynomial time for input graphs of bounded independence number, and for bipartite input graphs of bounded bipartite independence number. This generalizes previous positive results for complete (bipartite) graphs which were the only known results for EM on dense graphs.

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.

Nicolas El Maalouly

Research overview

Is this your work?

3 publications

On the Exact Matching Problem in Dense Graphs

Compatible Spanning Trees in Simple Drawings of $K_n$

Exact Matching in Graphs of Bounded Independence Number

See the researcher in context

Building this map preview

Nicolas El Maalouly

Research overview

Is this your work?

3 publications

On the Exact Matching Problem in Dense Graphs

Compatible Spanning Trees in Simple Drawings of KnK_nKn​

Exact Matching in Graphs of Bounded Independence Number

See the researcher in context

Building this map preview

Compatible Spanning Trees in Simple Drawings of $K_n$