BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Arash Rafiey

Arash Rafiey appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Data Structures and AlgorithmsDiscrete Mathematicsmath.COComputational ComplexityComputational Geometry

Catalog footprint

What is connected

12works
5topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

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.

Published work

12 published item(s)

preprint2020arXiv

Bi-Arc Digraphs and Conservative Polymorphisms

In this paper we study the class of bi-arc digraphs, important from two seemingly unrelated perspectives. On the one hand, they are precisely the digraphs that admit certain polymorphisms of interest in the study of constraint satisfaction problems; on the other hand, they are a very broad generalization of interval graphs. Bi-arc digraphs is the class of digraphs that admit conservative semilattice polymorphisms. There is much interest in understanding structures that admit particular types of polymorphisms, and especially in their recognition algorithms. (Such problems are referred to as metaproblems.) Surprisingly, the class of bi-arc digraphs also describes the class of digraphs that admit certain other kinds of conservative polymorphisms. Thus solving the recognition problem for bi-arc digraphs solves the metaproblem for digraphs for several types of conservative polymorphisms. The complexity of the recognition problem for digraphs with conservative semilattice polymorphisms was an open problem, while it was known to be NP-complete for certain more complex relational structures. We complement our result by providing a complete dichotomy classification of which general relational structures have polynomial or NP-complete recognition problems for the existence of conservative semilattice polymorphisms. Bi-arc digraphs also generalizes the class of interval graphs; in fact it reduces to the class of interval graphs for symmetric and reflexive digraphs. It is much broader than interval graphs and includes other generalizations of interval graphs such as co-threshold tolerance graphs and adjusted interval digraphs. Yet, it is still a reasonable extension of interval graphs, in the sense that it keeps much of the appeal of interval graphs. Our main result is a forbidden obstruction characterization of, and a polynomial recognition for, the class of bi-arc digraphs.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Dichotomy for Digraph Homomorphism Problems

We consider the problem of finding a homomorphism from an input digraph $G$ to a fixed digraph $H$. We show that if $H$ admits a weak-near-unanimity polymorphism $ϕ$ then deciding whether $G$ admits a homomorphism to $H$ (HOM($H$)) is polynomial time solvable? This gives a proof of the dichotomy conjecture (now dichotomy theorem) by Feder and Vardi [29]. Our approach is combinatorial, and it is simpler than the two algorithms found by Bulatov [9] and Zhuk [46] in 2017. We have implemented our algorithm and show some experimental results.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Ordering with precedence constraints and budget minimization

We introduce a variation of the scheduling with precedence constraints problem that has applications to molecular folding and production management. We are given a bipartite graph $H=(B,S)$. Vertices in $B$ are thought of as goods or services that must be \emph{bought} to produce items in $S$ that are to be \emph{sold}. An edge from $j\in S$ to $i\in B$ indicates that the production of $j$ requires the purchase of $i$. Each vertex in $B$ has a cost, and each vertex in $S$ results in some gain. The goal is to obtain an ordering of $B\cup S$ that respects the precedence constraints and maximizes the minimal net profit encountered as the vertices are processed. We call this optimal value the \emph{budget} or \emph{capital} investment required for the bipartite graph, and refer to our problem as \emph{the bipartite graph ordering problem}. The problem is equivalent to a version of an NP-complete molecular folding problem that has been studied recently [12]. Work on the molecular folding problem has focused on heuristic algorithms and exponential-time exact algorithms for the un-weighted problem where costs are $\pm 1$ and when restricted to graphs arising from RNA folding. The bipartite graph present work seeks exact algorithms for solving the bipartite ordering problem. We demonstrate an algorithm that computes the optimal ordering in time $O^*(2^n)$ when $n$ is the number of vertices in the input bipartite graph. Our main result is a general strategy that can be used to find an optimal ordering in polynomial time for bipartite graphs that satisfy certain properties. We apply the technique to a variety of graph classes, obtaining polynomial-time solutions to the bipartite graph ordering problem for bipartite permutation graphs, trivially perfect, co-bipartite graphs, and trees.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

PTAS for Ordered Instances of Resource Allocation Problems with Restrictions on Inclusions

We consider the problem of allocating a set $I$ of $m$ indivisible resources (items) to a set $P$ of $n$ customers (players) competing for the resources. Each resource $j \in I$ has a same value $v_j > 0$ for a subset of customers interested in $j$, and zero value for the remaining customers. The utility received by each customer is the sum of the values of the resources allocated to her. The goal is to find a feasible allocation of the resources to the interested customers such that for the Max-Min allocation problem (Min-Max allocation problem) the minimum of the utilities (maximum of the utilities) received by the customers is maximized (minimized). The Max-Min allocation problem is also known as the \textit{Fair Allocation problem}, or the \textit{Santa Claus problem}. The Min-Max allocation problem is the problem of Scheduling on Unrelated Parallel Machines, and is also known as the $R \, | \, | C_{\max}$ problem. In this paper, we are interested in instances of the problem that admit a Polynomial Time Approximation Scheme (PTAS). We show that an ordering property on the resources and the customers is important and paves the way for a PTAS. For the Max-Min allocation problem, we start with instances of the problem that can be viewed as a \textit{convex bipartite graph}; a bipartite graph for which there exists an ordering of the resources such that each customer is interested in (has a positive evaluation for) a set of \textit{consecutive} resources. We demonstrate a PTAS for the inclusion-free cases. This class of instances is equivalent to the class of bipartite permutation graphs. For the Min-Max allocation problem, we also obtain a PTAS for inclusion-free instances. These instances are not only of theoretical interest but also have practical applications.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Single Exponential FPT Algorithm for Interval Vertex Deletion and Interval Completion Problem

Let G be an input graph with n vertices and m edges and let k be a fixed parameter. We provide a single exponential FPT algorithm with running time O(c^kn(n+m)), c= min {18,k} that turns graph G into an interval graph by deleting at most k vertices from G. This solves an open problem posed by D.Marx [19]. We also provide a single exponential FPT algorithm with running time O(c^kn(n+m)), c= min {17,k} that turns G into an interval graph by adding at most$k edges. The first FPT algorithm with run time O(k^{2k}n^3m) appeared in STOC 2007 [24]. Our algorithm is the the first single exponential FPT algorithm that improves the running time of the previous algorithm. The algorithms are based on a structural decomposition of G into smaller subgraphs when G is free from small interval graph obstructions. The decomposition allows us to manage the search tree more efficiently.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Approximation Algorithms for Generalized MST and TSP in Grid Clusters

We consider a special case of the generalized minimum spanning tree problem (GMST) and the generalized travelling salesman problem (GTSP) where we are given a set of points inside the integer grid (in Euclidean plane) where each grid cell is $1 \times 1$. In the MST version of the problem, the goal is to find a minimum tree that contains exactly one point from each non-empty grid cell (cluster). Similarly, in the TSP version of the problem, the goal is to find a minimum weight cycle containing one point from each non-empty grid cell. We give a $(1+4\sqrt{2}+ε)$ and $(1.5+8\sqrt{2}+ε)$-approximation algorithm for these two problems in the described setting, respectively. Our motivation is based on the problem posed in [7] for a constant approximation algorithm. The authors designed a PTAS for the more special case of the GMST where non-empty cells are connected end dense enough. However, their algorithm heavily relies on this connectivity restriction and is unpractical. Our results develop the topic further.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Finding minimum Tucker submatrices

A binary matrix has the Consecutive Ones Property (C1P) if its columns can be ordered in such a way that all 1s on each row are consecutive. These matrices are used for DNA physical mapping and ancestral genome reconstruction in computational biology on the other hand they represents a class of convex bipartite graphs and are of interest of algorithm graph theory researchers. Tucker gave a forbidden submartices characterization of matrices that have C1P property in 1972. Booth and Lucker (1976) gave a first linear time recognition algorithm for matrices with C1P property and then in 2002, Habib, et al. gave a simpler linear time recognition algorithm. There has been substantial amount of works on efficiently finding minimum size forbidden submatrix. Our algorithm is at least $n$ times faster than the existing algorithm where $n$ is the number of columns of the input matrix.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Ordering without forbidden patterns

Let F be a set of ordered patterns, i.e., graphs whose vertices are linearly ordered. An F-free ordering of the vertices of a graph H is a linear ordering of V(H) such that none of patterns in F occurs as an induced ordered subgraph. We denote by ORD(F) the decision problem asking whether an input graph admits an F-free ordering; we also use ORD(F) to denote the class of graphs that do admit an F-free ordering. It was observed by Damaschke (and others) that many natural graph classes can be described as ORD(F) for sets F of small patterns (with three or four vertices). Damaschke also noted that for many sets F consisting of patterns with three vertices, ORD(F) is polynomial-time solvable by known algorithms or their simple modifications. We complete the picture by proving that all these problems can be solved in polynomial time. In fact, we provide a single master algorithm, i.e., we solve in polynomial time the problem $ORD_3$ in which the input is a set F of patterns with at most three vertices and a graph H, and the problem is to decide whether or not H admits an F-free ordering of the vertices. Our algorithm certifies non-membership by a forbidden substructure, and thus provides a single forbidden structure characterization for all the graph classes described by some ORD(F) with F consisting of patterns with at most three vertices. Many of the problems ORD(F) with F consisting of larger patterns have been shown to be NP-complete by Duffus, Ginn, and Rodl, and we add two simple examples. We also discuss a bipartite version of the problem, BORD(F), in which the input is a bipartite graph H with a fixed bipartition of the vertices, and we are given a set F of bipartite patterns. We also describe some examples of digraph ordering problems and algorithms. We conjecture that for every set F of forbidden patterns, ORD(F) is either polynomial or NP-complete.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Pattern overlap implies runaway growth in hierarchical tile systems

We show that in the hierarchical tile assembly model, if there is a producible assembly that overlaps a nontrivial translation of itself consistently (i.e., the pattern of tile types in the overlap region is identical in both translations), then arbitrarily large assemblies are producible. The significance of this result is that tile systems intended to controllably produce finite structures must avoid pattern repetition in their producible assemblies that would lead to such overlap. This answers an open question of Chen and Doty (SODA 2012), who showed that so-called "partial-order" systems producing a unique finite assembly *and" avoiding such overlaps must require time linear in the assembly diameter. An application of our main result is that any system producing a unique finite assembly is automatically guaranteed to avoid such overlaps, simplifying the hypothesis of Chen and Doty's main theorem.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Space complexity of list H-colouring: a dichotomy

The Dichotomy Conjecture for constraint satisfaction problems (CSPs) states that every CSP is in P or is NP-complete (Feder-Vardi, 1993). It has been verified for conservative problems (also known as list homomorphism problems) by A. Bulatov (2003). We augment this result by showing that for digraph templates H, every conservative CSP, denoted LHOM(H), is solvable in logspace or is hard for NL. More precisely, we introduce a digraph structure we call a circular N, and prove the following dichotomy: if H contains no circular N then LHOM(H) admits a logspace algorithm, and otherwise LHOM(H) is hard for NL. Our algorithm operates by reducing the lists in a complex manner based on a novel decomposition of an auxiliary digraph, combined with repeated applications of Reingold's algorithm for undirected reachability (2005). We also prove an algebraic version of this dichotomy: the digraphs without a circular N are precisely those that admit a finite chain of polymorphisms satisfying the Hagemann-Mitschke identities. This confirms a conjecture of Larose and Tesson (2007) for LHOM(H). Moreover, we show that the presence of a circular N can be decided in time polynomial in the size of H.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

The Dichotomy of List Homomorphisms for Digraphs

The Dichotomy Conjecture for constraint satisfaction problems has been verified for conservative problems (or, equivalently, for list homomorphism problems) by Andrei Bulatov. An earlier case of this dichotomy, for list homomorphisms to undirected graphs, came with an elegant structural distinction between the tractable and intractable cases. Such structural characterization is absent in Bulatov's classification, and Bulatov asked whether one can be found. We provide an answer in the case of digraphs; the technique will apply in a broader context. The key concept we introduce is that of a digraph asteroidal triple (DAT). The dichotomy then takes the following form. If a digraph H has a DAT, then the list homomorphism problem for H is NP-complete; and a DAT-free digraph H has a polynomial time solvable list homomorphism problem. DAT-free graphs can be recognized in polynomial time.

0 citations0 reviewsNo code linkedOpen access