The Graph Coloring Problem (GCP) is a fundamental combinatorial optimization problem that has many practical applications. Degree of SATURation (DSATUR) and Recursive Largest First (RLF) are well known as typical solution construction algorithms for GCP. It is necessary to update the vertex degree in the subgraph induced by uncolored vertices when selecting vertices to be colored in both DSATUR and RLF. There is an issue that the higher the edge density of a given graph, the longer the processing time. The purposes of this paper are to propose a degree updating method called Adaptive Degree Updating (ADU for short) that improves the issue, and to evaluate the effectiveness of ADU for DSATUR and RLF on DIMACS benchmark graphs as well as random graphs having a wide range of sizes and densities. Experimental results show that the construction algorithms with ADU are faster than the conventional algorithms for many graphs and that the ADU method yields significant speed-ups relative to the conventional algorithms, especially in the case of large graphs with higher edge density.

We introduce a new type of exponentiation algorithm in GF(2m) using Euclidean inversion. Our approach is based on the fact that Euclidean inversion cost much less logic gates than ordinary multiplication in GF(2m). By applying signed binary form of the exponent instead of classic binary form, the proposed algorithm can reduce the number of operations further compared with the classic algorithms.

This paper studies generalized variants of the MAXIMUM INDEPENDENT SET problem, called the MAXIMUM DISTANCE-d INDEPENDENT SET problem (MaxDdIS for short). For an integer d≥2, a distance-d independent set of an unweighted graph G=(V, E) is a subset S⊆V of vertices such that for any pair of vertices u, v∈S, the number of edges in any path between u and v is at least d in G. Given an unweighted graph G, the goal of MaxDdIS is to find a maximum-cardinality distance-d independent set of G. In this paper, we analyze the (in)approximability of the problem on r-regular graphs (r≥3) and planar graphs, as follows: (1) For every fixed integers d≥3 and r≥3, MaxDdIS on r-regular graphs is APX-hard. (2) We design polynomial-time O(rd-1)-approximation and O(rd-2/d)-approximation algorithms for MaxDdIS on r-regular graphs. (3) We sharpen the above O(rd-2/d)-approximation algorithms when restricted to d=r=3, and give a polynomial-time 2-approximation algorithm for MaxD3IS on cubic graphs. (4) Finally, we show that MaxDdIS admits a polynomial-time approximation scheme (PTAS) for planar graphs.

A grid drawing of a plane graph G is a drawing of G on the plane so that all vertices of G are put on plane grid points and all edges are drawn as straight line segments between their endpoints without any edge-intersection. In this paper we give a linear-time algorithm to find a grid drawing of any given 5-connected plane graph G with five or more vertices on the outer face. The size of the drawing satisfies W + H≤n - 2, where n is the number of vertices in G, W is the width and H is the height of the grid drawing.

We initiate the study of Ramsey numbers of trails. Let k≥2 be a positive integer. The Ramsey number of trails with k vertices is defined as the the smallest number n such that for every graph H with n vertices, H or the complete H contains a trail with k vertices. We prove that the Ramsey number of trails with k vertices is at most k and at least 2√k+Θ(1). This improves the trivial upper bound of ⌊3k/2⌋-1.

In this paper, we address the problem of finding a representation of a subtree distance, which is an extension of a tree metric. We show that a minimal representation is uniquely determined by a given subtree distance, and give an O(n2) time algorithm that finds such a representation, where n is the size of the ground set. Since a lower bound of the problem is Ω(n2), our algorithm achieves the optimal time complexity.

Given a graph G=(V, E), where V and E are vertex and edge sets of G, and a subset VNT of vertices called a non-terminal set, a spanning tree with a non-terminal set VNT, denoted by STNT, is a connected and acyclic spanning subgraph of G that contains all vertices of V where each vertex in a non-terminal set is not a leaf. On general graphs, the problem of finding an STNT of G is known to be NP-hard. In this paper, we show that if G is a circular-arc graph then finding an STNT of G is polynomially solvable with respect to the number of vertices.

In recent years, Graph Neural Networks has received enormous attention from academia for its huge potential of modeling the network traits such as macrostructure and single node attributes. However, prior mainstream works mainly focus on homogeneous network and lack the capacity to characterize the network heterogeneous property. Besides, most previous literature cannot the model latent influence link under microscope vision, making it infeasible to model the joint relation between the heterogeneity and mutual interaction within multiple relation type. In this letter, we propose a latent influence based self-attention framework to address the difficulties mentioned above. To model the heterogeneity and mutual interactions, we redesign the attention mechanism with latent influence factor on single-type relation level, which learns the importance coefficient from its adjacent neighbors under the same meta-path based patterns. To incorporate the heterogeneous meta-path in a unified dimension, we developed a novel self-attention based framework for meta-path relation fusion according to the learned meta-path coefficient. Our experimental results demonstrate that our framework not only achieves higher results than current state-of-the-art baselines, but also shows promising vision on depicting heterogeneous interactive relations under complicated network structure.

The NIST post-quantum project intends to standardize cryptographic systems that are secure against attacks by both quantum and classical computers. One of these cryptographic systems is NewHope that is a RING-LWE based key exchange scheme. The NewHope Key Encapsulation Method (KEM) allows to establish an encapsulated (secret) key shared by two participants. This scheme defines a private key that is used to encipher a random shared secret and the private key enables the deciphering. This paper presents Fault Information Leakage attacks, using conventional personal computers, if the attacked participant, say Bob, reuses his public key. This assumption is not so strong since reusing the pair (secret, public) keys saves Bob's device computing cost when the public global parameter is not changed. With our result we can conclude that, to prevent leakage, Bob should not reuse his NewHope secret and public keys because Bob's secret key can be retrieved with only 2 communications. We also found that Bob's secret keys can be retrieved for NewHopeToy2, NewHopeToy1 and NewHopeLudicrous with 1, 2, and 3 communications, respectively.

In this paper, we present a scheme to compute either AB or AB2 multiplications over GF(2m) and propose a bit-parallel systolic architecture based on the proposed algorithm. The AB multiplication algorithm is derived in the same form as the formula of AB2 multiplication algorithm, and an architecture that can perform AB multiplication by adding very little extra hardware to AB2 multiplier is designed. Therefore, the proposed architecture can be effectively applied to hardware constrained applications that cannot deploy AB2 multiplier and AB multiplier separately.

Machine reading comprehension with multi-hop reasoning always suffers from reasoning path breaking due to the lack of world knowledge, which always results in wrong answer detection. In this paper, we analyze what knowledge the previous work lacks, e.g., dependency relations and commonsense. Based on our analysis, we propose a Multi-dimensional Knowledge enhanced Graph Network, named MKGN, which exploits specific knowledge to repair the knowledge gap in reasoning process. Specifically, our approach incorporates not only entities and dependency relations through various graph neural networks, but also commonsense knowledge by a bidirectional attention mechanism, which aims to enhance representations of both question and contexts. Besides, to make the most of multi-dimensional knowledge, we investigate two kinds of fusion architectures, i.e., in the sequential and parallel manner. Experimental results on HotpotQA dataset demonstrate the effectiveness of our approach and verify that using multi-dimensional knowledge, especially dependency relations and commonsense, can indeed improve the reasoning process and contribute to correct answer detection.

This paper proposes a network tomography scheme for information-centric networking (ICN), which we call ICN tomography. When content is received over a conventional IP network, the communication occurs after converting the content name into an IP address, which is the locator, so as to identify the position of the network. By contrast, in ICN, communication is achieved by directly specifying the content name or content ID. The content is sent to the requesting user by a nearby node having the content or cache, making it difficult to apply a conventional network tomography that uses end-to-end quality of service (QoS) measurements and routing information between the source and destination node pairs as input to the ICN. This is because, in ICN, the end-to-end flow for an end host receiving some content can take various routes; therefore, the intermediate and source nodes can vary. In this paper, we first describe the technical challenges of applying network tomography to ICN. We then propose ICN tomography, where we use the content name as an endpoint to define an end-to-end QoS measurement and a routing matrix. In defining the routing matrix, we assume that the end-to-end flow follows a probabilistic routing. Finally, the effectiveness of the proposed method is evaluated through a numerical analysis and simulation.

The usefulness and usability of existing knowledge graphs (KGs) are mostly limited because of the incompleteness of knowledge compared to the growing number of facts about the real world. Most existing ontology-based KG completion methods are based on the closed-world assumption, where KGs are fixed. In these methods, entities and relations are defined, and new entity information cannot be easily added. In contrast, in open-world assumptions, entities and relations are not previously defined. Thus there is a vast scope to find new entity information. Despite this, knowledge acquisition under the open-world assumption is challenging because most available knowledge is in a noisy unstructured text format. Nevertheless, Open Information Extraction (OpenIE) systems can extract triples, namely (head text; relation text; tail text), from raw text without any prespecified vocabulary. Such triples contain noisy information that is not essential for KGs. Therefore, to use such triples for the KG completion task, it is necessary to identify competent triples for KGs from the extracted triple set. Here, competent triples are the triples that can contribute to add new information to the existing KGs. In this paper, we propose the Competent Triple Identification (CTID) model for KGs. We also propose two types of feature, namely syntax- and semantic-based features, to identify competent triples from a triple set extracted by a state-of-the-art OpenIE system. We investigate both types of feature and test their effectiveness. It is found that the performance of the proposed features is about 20% better compared to that of the ReVerb system in identifying competent triples.

To prove the graph relations such as the connectivity and isolation for a certified graph, a system of a graph signature and proofs has been proposed. In this system, an issuer generates a signature certifying the topology of an undirected graph, and issues the signature to a prover. The prover can prove the knowledge of the signature and the graph in the zero-knowledge, i.e., the signature and the signed graph are hidden. In addition, the prover can prove relations on the certified graph such as the connectivity and isolation between two vertexes. In the previous system, using integer commitments on RSA modulus, the graph relations are proved. However, the RSA modulus needs a longer size for each element. Furthermore, the proof size and verification cost depend on the total numbers of vertexes and edges. In this paper, we propose a graph signature and proof system, where these are computed on bilinear groups without the RSA modulus. Moreover, using a bilinear map accumulator, the prover can prove the connectivity and isolation on a graph, where the proof size and verification cost become independent from the total numbers of vertexes and edges.

In this paper, we introduce a path embedding problem inspired by the well-known hydrophobic-polar (HP) model of protein folding. A graph is said bicolored if each vertex is assigned a label in the set {red, blue}. For a given bicolored path P and a given bicolored graph G, our problem asks whether we can embed P into G in such a way as to match the colors of the vertices. In our model, G represents a protein's “blueprint,” and P is an amino acid sequence that has to be folded to form (part of) G. We first show that the bicolored path embedding problem is NP-complete even if G is a rectangular grid (a typical scenario in protein folding models) and P and G have the same number of vertices. By contrast, we prove that the problem becomes tractable if the height of the rectangular grid G is constant, even if the length of P is independent of G. Our proof is constructive: we give a polynomial-time algorithm that computes an embedding (or reports that no embedding exists), which implies that the problem is in XP when parameterized according to the height of G. Additionally, we show that the problem of embedding P into a rectangular grid G in such a way as to maximize the number of red-red contacts is NP-hard. (This problem is directly inspired by the HP model of protein folding; it was previously known to be NP-hard if G is not given, and P can be embedded in any way on a grid.) Finally, we show that, given a bicolored graph G, the problem of constructing a path P that embeds in G maximizing red-red contacts is Poly-APX-hard.

Some textbooks of formal languages and automata theory implicitly state the structural equality of the binary n-dimensional de Bruijn graph and the state diagram of minimum state deterministic finite automaton which accepts regular language (0+1)*1(0+1)n-1. By introducing special finite automata whose accepting states are refined with two or more colors, we extend this fact to both k-ary versions. That is, we prove that k-ary n-dimensional de Brujin graph and the state diagram for minimum state deterministic colored finite automaton which accepts the (k-1)-tuple of the regular languages (0+1+…+k-1)*1(0+1+…+k-1)n-1,...,and(0+1+…+k-1)*(k-1)(0+1+…+k-1)n-1 are isomorphic for arbitrary k more than or equal to 2. We also investigate the properties of colored finite automata themselves and give computational complexity results on three decision problems concerning color unmixedness of nondeterminisitic ones.

The problem of enumerating connected induced subgraphs of a given graph is classical and studied well. It is known that connected induced subgraphs can be enumerated in constant time for each subgraph. In this paper, we focus on highly connected induced subgraphs. The most major concept of connectivity on graphs is vertex connectivity. For vertex connectivity, some enumeration problem settings and enumeration algorithms have been proposed, such as k-vertex connected spanning subgraphs. In this paper, we focus on another major concept of graph connectivity, edge-connectivity. This is motivated by the problem of finding evacuation routes in road networks. In evacuation routes, edge-connectivity is important, since highly edge-connected subgraphs ensure multiple routes between two vertices. In this paper, we consider the problem of enumerating 2-edge-connected induced subgraphs of a given graph. We present an algorithm that enumerates 2-edge-connected induced subgraphs of an input graph G with n vertices and m edges. Our algorithm enumerates all the 2-edge-connected induced subgraphs in O(n3m|SG|) time, where SG is the set of the 2-edge-connected induced subgraphs of G. Moreover, by slightly modifying the algorithm, we have a O(n3m)-delay enumeration algorithm for 2-edge-connected induced subgraphs.

Betweenness centrality is one of the most significant and commonly used centralities, where centrality is a notion of measuring the importance of nodes in networks. In 2001, Brandes proposed an algorithm for computing betweenness centrality efficiently, and it can compute those values for all nodes in O(nm) time for unweighted networks, where n and m denote the number of nodes and links in networks, respectively. However, even Brandes' algorithm is not fast enough for recent large-scale real-world networks, and therefore, much faster algorithms are expected. The objective of this research is to theoretically improve the efficiency of Brandes' algorithm by introducing graph decompositions, and to verify the practical effectiveness of our approaches by implementing them as computer programs and by applying them to various kinds of real-world networks. A series of computational experiments shows that our proposed algorithms run several times faster than the original Brandes' algorithm, which are guaranteed by theoretical analyses.

For a graph G=(V,E), finding a set of disjoint edges that do not share any vertices is called a matching problem, and finding the maximum matching is a fundamental problem in the theory of distributed graph algorithms. Although local algorithms for the approximate maximum matching problem have been widely studied, exact algorithms have not been much studied. In fact, no exact maximum matching algorithm that is faster than the trivial upper bound of O(n2) rounds is known for general instances. In this paper, we propose a randomized $O(s_{max}^{3/2})$-round algorithm in the CONGEST model, where smax is the size of maximum matching. This is the first exact maximum matching algorithm in o(n2) rounds for general instances in the CONGEST model. The key technical ingredient of our result is a distributed algorithms of finding an augmenting path in O(smax) rounds, which is based on a novel technique of constructing a sparse certificate of augmenting paths, which is a subgraph of the input graph preserving at least one augmenting path. To establish a highly parallel construction of sparse certificates, we also propose a new characterization of sparse certificates, which might also be of independent interest.

In this paper, by using the properties of the cyclic Hadamard matrices of order 4t, an infinite class of (4t-1)-variable 2-resilient rotation symmetric Boolean functions is constructed, and the nonlinearity of the constructed functions are also studied. To the best of our knowledge, this is the first class of direct constructions of 2-resilient rotation symmetric Boolean functions. The spirit of this method is different from the known methods depending on the solutions of an equation system proposed by Du Jiao, et al. Several situations are examined, as the direct corollaries, three classes of (4t-1)-variable 2-resilient rotation symmetric Boolean functions are proposed based on the corresponding sequences, such as m sequences, Legendre sequences, and twin primes sequences respectively.