The classical ErdösGallai theorem kicked off the study ofgraph realizability by characterizing degree sequences. We extend this line of research by investigating realizability of directed acyclic graphs (DAGs)given both a local constraint via degree sequences and a global constraint via a sequence of reachability values (number of nodes reachable from a given node). We show that, without degree constraints, DAG reachability realization is solvable in linear time, whereas it is strongly NPcomplete given upper bounds on indegree or outdegree. After defining a suitable notion of bicriteria approximation based on consistency, we give two approximation algorithms achieving O(logn)reachability consistency and O(logn)degreemore »
Synchronous Dynamical Systems on Directed Acyclic Graphs: Complexity and Algorithms
Discrete dynamical systems serve as useful formal models
to study diffusion phenomena in social networks. Motivated
by applications in systems biology, several recent papers have
studied algorithmic and complexity aspects of diffusion problems
for dynamical systems whose underlying graphs are directed,
and may contain directed cycles. Such problems can
be regarded as reachability problems in the phase space of
the corresponding dynamical system. We show that computational
intractability results for reachability problems hold
even for dynamical systems on directed acyclic graphs (dags).
We also show that for dynamical systems on dags where each
local function is monotone, the reachability problem can be
solved efficiently.
 Publication Date:
 NSFPAR ID:
 10253360
 Journal Name:
 Proceedings of the AAAI Conference on Artificial Intelligence
 Volume:
 35
 Issue:
 13
 Page Range or eLocationID:
 1133411342
 ISSN:
 21595399
 Sponsoring Org:
 National Science Foundation
More Like this


Many program analyses need to reason about pairs of matching actions, such as call/return, lock/unlock, or setfield/getfield. The family of Dyck languages { D k }, where D k has k kinds of parenthesis pairs, can be used to model matching actions as balanced parentheses. Consequently, many programanalysis problems can be formulated as Dyckreachability problems on edgelabeled digraphs. Interleaved Dyckreachability (InterDyckreachability), denoted by D k ⊙ D k reachability, is a natural extension of Dyckreachability that allows one to formulate programanalysis problems that involve multiple kinds of matchingaction pairs. Unfortunately, the general InterDyckreachability problem is undecidable. In this paper, wemore »

Semisupervised and unsupervised machine learning methods often rely on graphs to model data, prompting research on how theoretical properties of operators on graphs are leveraged in learning problems. While most of the existing literature focuses on undirected graphs, directed graphs are very important in practice, giving models for physical, biological or transportation networks, among many other applications. In this paper, we propose a new framework for rigorously studying continuum limits of learning algorithms on directed graphs. We use the new framework to study the PageRank algorithm and show how it can be interpreted as a numerical scheme on a directedmore »

Directed graphs have been widely used in Community Question Answering services (CQAs) to model asymmetric relationships among different types of nodes in CQA graphs, e.g., question, answer, user. Asymmetric transitivity is an essential property of directed graphs, since it can play an important role in downstream graph inference and analysis. Question difficulty and user expertise follow the characteristic of asymmetric transitivity. Maintaining such properties, while reducing the graph to a lower dimensional vector embedding space, has been the focus of much recent research. In this paper, we tackle the challenge of directed graph embedding with asymmetric transitivity preservation and thenmore »

Resource is an important constraint when deploying Deep Neural Networks (DNNs) on mobile and edge devices. Existing works commonly adopt the cellbased search approach, which limits the flexibility of network patterns in learned cell structures. Moreover, due to the topologyagnostic nature of existing works, including both cellbased and nodebased approaches, the search process is time consuming and the performance of found architecture may be suboptimal. To address these problems, we propose AutoShrink, a topologyaware Neural Architecture Search (NAS) for searching efficient building blocks of neural architectures. Our method is nodebased and thus can learn flexible network patterns in cell structuresmore »