On the parameterized complexity of multiple-interval graph problems

Multiple-interval graphs are a natural generalization of interval graphs where each vertex may have more than one interval associated with it. Many applications of interval graphs also generalize to multiple-interval graphs, often allowing for more robustness in the modeling of the specific application. With this motivation in mind, a recent systematic study of optimization problems in multiple-interval graphs was initiated. In this sequel, we study multiple-interval graph problems from the perspective of parameterized complexity. The problems under consideration are k$k$-Independent Set, k$k$-Dominating Set, and k$k$-Clique, which are all known to be W[1]-hard for general graphs, and NP-complete for multiple-interval graphs. We prove that k$k$-Clique is in FPT, while k$k$-Independent Set and k$k$-Dominating Set are both W[1]-hard. We also prove that k$k$-Independent Dominating Set, a hybrid of the two above problems, is also W[1]-hard. Our hardness results hold even when each vertex is associated with at most two intervals, and all intervals have unit length. Furthermore, as an interesting byproduct of our hardness results, we develop a useful technique for showing W[1]-hardness via a reduction from the k$k$-Multicolored Clique problem, a variant of k$k$-Clique. We believe this technique has interest in its own right, as it should help in simplifying W[1]-hardness results which are notoriously hard to construct and technically tedious.     

On the information-based complexity of optimal reconstruction for nonlinear systems

The information-based complexity of optimal reconstruction problems for general nonlinear systems is studied. Both lower and upper bounds for the worst-case reconstruction-error functional are given. The existence of an optimal reconstruction algorithm which achieves the infimum of the reconstruction-error is established.     

Expressiveness and complexity of graph logic

We investigate the complexity and expressive power of a spatial logic for reasoning about graphs. This logic was previously introduced by Cardelli, Gardner and Ghelli, and provides the simplest setting in which to explore such results for spatial logics. We study several forms of the logic: the logic with and without recursion, and with either an exponential or a linear version of the basic composition operator. We study the combined complexity and the expressive power of the four combinations. We prove that, without recursion, the linear and exponential versions of the logic correspond to significant fragments of first-order (FO) and monadic second-order (MSO) Logics; the two versions are actually equivalent to FO and MSO on graphs representing strings. However, when the two versions are enriched with μ-style recursion, their expressive power is sharply increased.Both are able to express PSPACE-complete problems, although their combined complexity and data complexity still belong to PSPACE.     

The complexity of determining the rainbow vertex-connection of a graph

A vertex-colored graph is rainbow vertex-connected if any two vertices are connected by a path whose internal vertices have distinct colors, which was introduced by Krivelevich and Yuster. The rainbow vertex-connection of a connected graph G, denoted by rvc(G), is the smallest number of colors that are needed in order to make G rainbow vertex-connected. In this paper, we study the complexity of determining the rainbow vertex-connection of a graph and prove that computing rvc(G) is NP-Hard. Moreover, we show that it is already NP-Complete to decide whether rvc(G)=2. We also prove that the following problem is NP-Complete: given a vertex-colored graph G, check whether the given coloring makes G rainbow vertex-connected.     

The complexity of comparability graph recognition and coloring

Using the notion ofG-decomposition introduced in Golumbic [8, 9], we present an implementation of an algorithm which assigns a transitive orientation to a comparability graph inO(δ·|E|) time andO(|E|) space where δ is the maximum degree of a vertex and |E| is the number of edges. A quotient operation reducing the graph in question and preservingG-decomposition and transitive orientability is shown, and efficient solutions to a number ofNP-complete problems which reduce to polynomial time for comparability graphs are discussed.     

The complexity of graph languages generated by hyperedge replacement

Summary Although in many ways, hyperedge replacement graph grammars (HRGs) are, among all graph generating mechanisms, what context-free Chomsky grammars are in the realm of string rewriting, their parsing problem is known to be, in general, NP-complete. In this paper, the main difficulty in HRG parsing is analysed and some conditions on either grammar or input graphs are developed under which parsing can be done in polynomial time. For some of the cases, the parsing problem is shown to be log-space reducible to context-free string parsing.Parts of the results of this paper were presented at 15^th ICALP, [La88b]     

On the edge-tenacity of the middle graph of a graph

We consider the problem of efficiently breaking a graph into small components by removing edges. One measure of how easily this can be done is the edge-tenacity. Given a set of edges of G, the score of S is defined as sc(S)=[| S|+τ (G?S)]/[w(G?S)]. Formally, the edge-tenacity of a graph G is defined as T′(G)=min sc(S), where the minimum is taken over all edge-sets S of G. A subset S of E(G) is said to be a T′-set of G if T′(G)=sc(S). Note that if G is disconnected, the set S may be empty. For any graph G, τ(G?S) is the number of vertices in the largest component of G?S and w(G?S) is the number of components of G?S. The middle graph M(G) of a graph G is the graph obtained from G by inserting a new vertex into every edge of G and by joining by edges those pairs of these new vertices which lie on adjacent edges of G. In this paper, we give the edge-tenacity of the middle graph of specific families of graphs and its relationships with other parameters.     

Lower bounds for the majority communication complexity of various graph accessibility problems

We investigate the probabilistic communication complexity (more exactly, the majority communication complexity), of the graph accessibility problem (GAP) and its counting versions MOD _k -GAP,k ≥ 2. Due to arguments concerning matrix variation ranks and certain projection reductions, we prove that, for any partition of the input variables, GAP and MOD _m -GAP have majority communication complexity Ω,(n), wheren denotes the number of nodes of the graph under consideration.     

On the complexity of or-parallelism

We formalize the implementation mechanisms required to support or-parallel execution of logic programs in terms of operations on dynamic data structures. Upper and lower bounds are derived, in terms of the number of operationsn performed on the data structure, for the problem of guaranteeing correct semantics during or-parallel execution. The lower bound Ω(lgn) formally proves the impossibility of achieving an ideal implementation (i.e., parallel implementation with constant time overhead per operation). We also derive an upper bound of $\tilde O\left( {\sqrt[3]{n}} \right)$ per operation for or-parallel execution. This upper bound is far better than what has been achieved in the existing or-parallel systems and indicates that faster implementations may be feasible.     

On the encryption for graph foundation model inference of sparse graph

Graph foundation models and graph prompts have emerged as a popular research area for graph learning research in recent years. However, their real-world deployment raises concerns about the potential leakage of sensitive information during inference. This work presents a new graph encryption for private graph foundation model（GFM） inference with applications for sparse graphs. It adds dummy edges into graphs randomly and encrypts graph structures rather than adjacency matrices through homomorphic encryption（HE）. Based on this kind of graph encryption, we propose a new private GFM inference scheme with graph prompts, and the basic idea is to perform private neighbor queries for the multiplications of adjacency matrices, and integrate neighbor sampling to reduce computation costs. Our scheme achieves a computational complexity of O（M） for HE multiplications, which is a remarkable improvement over the previous O（N²） complexity. Here,N and M are the numbers of nodes and edges in a graph, respectively. Theoretically, we prove the correctness of our private prompted GFM inference and the security of our encryption scheme. Finally, we have conducted extensive experiments to validate the effectiveness and efficiency of our private GFM inference.     

On graph reasoning

In this paper, we study the (positive) graph relational calculus. The basis for this calculus was introduced by Curtis and Lowe in 1996 and some variants, motivated by their applications to semantics of programs and foundations of mathematics, appear scattered in the literature. No proper treatment of these ideas as a logical system seems to have been presented. Here, we give a formal presentation of the system, with precise formulation of syntax, semantics, and derivation rules. We show that the set of rules is sound and complete for the valid inclusions, and prove a finite model result as well as decidability. We also prove that the graph relational language has the same expressive power as a first-order positive fragment (both languages define the same binary relations), so our calculus may be regarded as a notational variant of the positive existential first-order logic of binary relations. The graph calculus, however, has a playful aspect, with rules easy to grasp and use. This opens a wide range of applications which we illustrate by applying our calculus to the positive relational calculus (whose set of valid inclusions is not finitely axiomatizable), obtaining an algorithm for deciding the valid inclusions and equalities of the latter.     

Research on intelligence recognition and reconstruction of engineering graph

In the paper, the authors put forward a regulation-based expert system which is used in auto-recognition and reconstruction of engineering graph. It consists of four parts-dynamic fact library, static regulation h'brary,inference control and 3D reconstruction. it discribles the knowledge and regulations to reeongnize engineering graph with regulation- expressing method, and sets up the inference mechanism according to its recognition thoughts. At last, it introduces recognition results of 3D reconstruction with AutoCAD.