Polynomial-Time Algorithms for Structurally Observable Graphs by Controlling Minimal Vertices
The aim of this paper is to characterize an important class of marked digraphs, called structurally observable graphs (SOGs), and to solve two minimum realization problems. To begin with, by exploring structural observability of large-scale Boolean networks (LSBNs), an underlying type of SOGs is provided based on a recent observability criterion of conjunctive BNs. Besides, SOGs are also proved to have important applicability to structural observability of general discrete-time systems. Further, two minimum realization strategies are considered to induce an SOG from an arbitrarily given digraph by marking and controlling the minimal vertices, respectively. It indicates that one can induce an observable system by means of adding the minimal sensors or modifying the adjacency relation of minimal vertices. Finally, the structural observability of finite-field networks, and the minimum pinned node theorem for Boolean networks are displayed as application and simulation. The most salient superiority is that the designed algorithms are polynomial time and avoid exhaustive brute-force searches. It means that our results can be applied to deal with the observability of large-scale systems (particularly, LSBNs), whose observability analysis and the minimum controlled node theorem are known as intractable problems.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Challenges of Generating Structurally Diverse Graphs
For many graph-related problems, it can be essential to have a set of structurally diverse graphs. For instance, such graphs can be used for testing graph algorithms or their neural approximations. However, to the best o…
DiversityOn Efficiently Explaining Graph-Based Classifiers
Recent work has shown that not only decision trees (DTs) may not be interpretable but also proposed a polynomial-time algorithm for computing one PI-explanation of a DT. This paper shows that for a wide range of classifi…
Inference and Sampling of $K_{33}$-free Ising Models
We call an Ising model tractable when it is possible to compute its partition function value (statistical inference) in polynomial time. The tractability also implies an ability to sample configurations of this model in …
Polynomial-Time Algorithms for Counting and Sampling Markov Equivalent DAGs
Counting and uniform sampling of directed acyclic graphs (DAGs) from a Markov equivalence class are fundamental tasks in graphical causal analysis. In this paper, we show that these tasks can be performed in polynomial t…
Planning in Observable POMDPs in Quasipolynomial Time
Partially Observable Markov Decision Processes (POMDPs) are a natural and general model in reinforcement learning that take into account the agent's uncertainty about its current state. In the literature on POMDPs, it is…