Salman Parsa

Current Address:

Ritter Hall

Deopartment of Computer Science

Saint Louis University, Saint Louis, MO. USA.

email: salman.parsa@slu.edu

Ritter Hall

Deopartment of Computer Science

Saint Louis University, Saint Louis, MO. USA.

email: salman.parsa@slu.edu

Welcome to my personal homepage!

with Erin Wolf Chambers, Jeff Erickson, Patrick Lin

We present the first algorithm to morph graphs on the torus. Given two isotopic essentially 3-connected embeddings of the same graph on the Euclidean flat torus, where the edges in both drawings are geodesics, our algorithm computes a continuous deformation from one drawing to the other, such that all edges are geodesics at all times. Previously even the existence of such a morph was not known. Our algorithm runs in O(n1+ω/2) time, where ω is the matrix multiplication exponent, and the computed morph consists of O(n) parallel linear morphing steps. Existing techniques for morphing planar straight-line graphs do not immediately generalize to graphs on the torus; in particular, Cairns' original 1944 proof and its more recent improvements rely on the fact that every planar graph contains a vertex of degree at most 5. Our proof relies on a subtle geometric analysis of 6-regular triangulations of the torus. We also make heavy use of a natural extension of Tutte's spring embedding theorem to torus graphs.

Accepted to SODA 2021

with A. Skopenkov

embeddability of [3]∗K

In this survey-research paper, we first introduce the theory of Smith

classes of complexes with fixed-point free, periodic maps on them.

These classes, when defined for the deleted product of a simplicial

complex K, are the same as the embedding classes of K. Embedding

classes, in turn, are generalizations of the van Kampen obstruction

class for embeddability of a d-dimensional complex K into the Euclidean 2d-space. All of these concepts will be introduced in simple

terms. Second, we use the theory introduced in the first part to relate the

embedding classes (or the special Smith classes) of the the complex

[3] ∗ K with the embedding classes of K. Here [3] ∗ K is the join of K

with a set of three points. Specifically, we prove that if the m-th embedding class of K is nonzero, then the (m+2)-nd embedding class of [3]∗K is non-zero. We also prove some of the consequences of this theorem for the embeddability of [3] ∗ K.

Hardness of Segment Cover, Contiguous SAT and Visibility with Uncertain Obstacles

with Sh. Alipour

Consider SAT with the following restrictions. An input formula is in CNF form, and, there exists an ordering of the clauses in which clauses containing any fixed literal appear contiguously. We call this restricted SAT CONTIGUOUS SAT. We also define the related problem SEGMENT COVER. In SEGMENT COVER, we are given a set of uncertain segments, each uncertain segment defined to be a random interval, chosen from two possible sub-intervals of the unit interval. Then, SEGMENT COVER asks if the probability of covering the entire unit interval is non-zero. We prove that SEGMENT COVER and hence CONTIGUOUS SAT are NP-hard. We further show that we can assume all intervals of SEGMENT COVER to be of equal lengths, this proves another problem called BCU to be NP-hard in dimension 1. Moreover, we also deduce hardness of approximation for CONTIGUOUS SAT and show it cannot have a PTAS, unless P= NP.

with Sh. Alipour

Consider SAT with the following restrictions. An input formula is in CNF form, and, there exists an ordering of the clauses in which clauses containing any fixed literal appear contiguously. We call this restricted SAT CONTIGUOUS SAT. We also define the related problem SEGMENT COVER. In SEGMENT COVER, we are given a set of uncertain segments, each uncertain segment defined to be a random interval, chosen from two possible sub-intervals of the unit interval. Then, SEGMENT COVER asks if the probability of covering the entire unit interval is non-zero. We prove that SEGMENT COVER and hence CONTIGUOUS SAT are NP-hard. We further show that we can assume all intervals of SEGMENT COVER to be of equal lengths, this proves another problem called BCU to be NP-hard in dimension 1. Moreover, we also deduce hardness of approximation for CONTIGUOUS SAT and show it cannot have a PTAS, unless P= NP.

In this project, we presented an exponential time algorithm for deciding the contractibilty of a closed curve with self-intersections on the boundary of a 3-manifold. The main idea is to extract the computational content of the proof of the Loop Theorem.

Preliminary version of the result is published in:

É. Colin de Verdière, S. Parsa, “Deciding Contractibility of a Non-Simple Curve on the Boundary of a 3-Manifold”, Proceedings of the twenty-eighth annual ACM-SIAM Symposium On Discrete Algorithms. 2017, 2691-2704

The journal version of the paper. This is a totally rewritten improved version:

In this work, I have given a critorion that the each intersection of link-complexes of three disjoint vertices of an embeddable complex must satisfy. This triple intersection is a subgraph of the 1-skeleton of given 2-complex. This graph has to be planar. In the paper I have also a weaker general statement for general dimension that is proved by means of elementary algebraic topology.

This result is published in:

S. Parsa, “On the Links of Vertices in Simplicial d-Complexes Embeddable in the Euclidean 2d-Space”, Discrete Comput Geom (2017). https://doi.org/10.1007/s00454-017-9936-

In this research, I have shown by a new proof that each homotopy type of a 2-dimensional simplicial complex has a member simplicial complex that embeds into 4-space. In particular, any finitely presented group appears as a fundamental group of a 2-complex PL embeded into 4-space. These result had been known before, and I have independently proven them. These embeddings can be built in linear time, that implies, knowing that a 2-complex is embeddable in 4-space does not help with regard to efficiency of algorithmic problems related to its fundamental group.

The paper can be downloaded from here:

“Small Model 2-Complexes in 4-space and Applications.” ArXiv e-prints, 1512.05152, 2015

Reductions from Matrix Rank

with H. Edelsbrunner.

I

H. Edelsbrunner, S. Parsa, “On the computational complexity of Betti numbers: reductions from matrix rank”, Proceedings of the twenty-fifth annual ACM-SIAM Symposium On Discrete Algorithms. 2014, 152-160.

S. Parsa, “A Deterministic O ( m log m ) Time Algorithm for the Reeb Graph” . Discrete & Computational Geometry 49(4): 864-878 (2013) [ First version in SOCG 2012].

Please contact me if you need the code for this project.

This is my first paper. It discusses a technique to accelerate the raytracing procedure where the environment is static.

“A Ray Tracing Acceleration Technique for Wave Propagation Modeling”, Proc. IEEE Asia–Pacific Microwave Conference , 2009.