In a graph, a perfect matching cut is an edge cut that is a perfect matching. PERFECT MATCHING CUT (PMC) is the problem of deciding whether a given graph has a perfect matching cut, and is known to be NP-complete. We ...
详细信息
In a graph, a perfect matching cut is an edge cut that is a perfect matching. PERFECT MATCHING CUT (PMC) is the problem of deciding whether a given graph has a perfect matching cut, and is known to be NP-complete. We revisit the problem and show that PMC remains NP-complete when restricted to bipartite graphs of maximum degree 3 and arbitrarily large girth. Complementing this hardness result, we give two graph classes in which PMC is polynomial-time solvable. The first one includes claw-free graphs and graphs without an induced path on five vertices, the second one properly contains all chordal graphs. Assuming the Exponential Time Hypothesis, we show there is no O*(2o(n))-time algorithm for PMC even when restricted to n-vertex bipartite graphs, and also show that PMC can be solved in O*(1.2721n) time by means of an exact branching algorithm.(c) 2022 Elsevier B.V. All rights reserved.
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...
详细信息
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(n(2)) time algorithm that finds such a representation, where n is the size of the ground set. Since a lower bound of the problem is Omega(n(2)), our algorithm achieves the optimal time complexity.
The shortest path problem is the most classical and fundamental problem in the field of graph algorithm. Recently, its reconfiguration variant, namely the Shortest Path Reconfiguration problem, has received a lot of a...
详细信息
ISBN:
(数字)9789819705665
ISBN:
(纸本)9789819705658;9789819705665
The shortest path problem is the most classical and fundamental problem in the field of graph algorithm. Recently, its reconfiguration variant, namely the Shortest Path Reconfiguration problem, has received a lot of attention. In this paper, we study the complexity of k-SPR, which generalizes the Shortest Path Reconfiguration problem, with respect to k. In k-SPR, we are allowed to replace at most k consecutive vertices of the current shortest path at a time. We first show that, for any fixed rational numbers c and epsilon such that c > 0 and 0 < epsilon <= 1, k-SPR with k = cn(1-epsilon) is polynomially solvable if epsilon = 1 and c < 1;otherwise, PSPACE-complete. This intractability holds even when given graphs are restricted to bipartite graphs and r-th power graphs, where r is any positive integer. Furthermore, when we restrict 0 < epsilon < 1, the PSPACE-completeness holds for graphs with maximum degree 3. Then, we design an FPT algorithm parameterized by mu = n/2 - k >= 0 that runs in O(m + 6.730(mu) mu(4) n) time. Finally, we show that, for any k, k-SPR can be solved in linear time for K-2,K-3-minor-free graphs.
Data parallel primitives are highly optimized general-purpose algorithms designed only for GPUs and are used as building blocks to develop applications. However, existing data parallel primitives cannot handle data la...
详细信息
ISBN:
(纸本)9783031683114;9783031683121
Data parallel primitives are highly optimized general-purpose algorithms designed only for GPUs and are used as building blocks to develop applications. However, existing data parallel primitives cannot handle data larger than the GPU memory size. In this paper, we propose an extension to existing data parallel primitives to efficiently handle data larger than the GPU memory size by cooperatively using both GPUs and CPUs. Moreover, we evaluate the impact of these primitives when applying them to large data processing applications, with respect to both performance and software development cost.
We consider the following problem that we call the Shortest Two Disjoint Paths problem: given an undirected graph G = ( V, E) with edge weights w : E -> R, two terminals s and t in G, find two internally vertex-dis...
详细信息
ISBN:
(纸本)9783959773119
We consider the following problem that we call the Shortest Two Disjoint Paths problem: given an undirected graph G = ( V, E) with edge weights w : E -> R, two terminals s and t in G, find two internally vertex-disjoint paths between s and t with minimum total weight. As shown recently by Schlotter and Sebo (2022), this problem becomes NP-hard if edges can have negative weights, even if the weight function is conservative, i.e., there are no cycles in G with negative total weight. We propose a polynomial-time algorithm that solves the SHORTEST TWO DISJOINT PATHS problem for conservative weights in the case when the negative-weight edges form a constant number of trees in G.
Automatic knowledge graph (KG) construction is widely used in industry for data integration and access, and there are several approaches to enable (semi-)automatic construction of knowledge graphs. One important appro...
详细信息
ISBN:
(纸本)9783031194320;9783031194337
Automatic knowledge graph (KG) construction is widely used in industry for data integration and access, and there are several approaches to enable (semi-)automatic construction of knowledge graphs. One important approach is to map the raw data to a given knowledge graph schema, often a domain ontology, and construct the entities and properties according to the ontology. However, the existing approaches to construct knowledge graphs are not always efficient enough and the resulting knowledge graphs are not sufficiently application-oriented and user-friendly. The challenge arises from the trade-off: the domain ontology should be knowledge-oriented, to reflect the general domain knowledge rather than data particularities;while a knowledge graph schema should be data-oriented, to cover all data features. If the former is directly used as the knowledge graph schema, this can cause issues like blank nodes created due to classes unmapped to data and deep knowledge graph structures. To this end, we propose a system for ontology reshaping, which generates knowledge graph schemata that fully cover the data while also covers domain knowledge well. We evaluated our approach extensively with a user study and three real manufacturing datasets from Bosch against four baselines, showing promising results.
The anti-Ramsey number, ar(G, H) is the minimum integer k such that in any edge colouring of G with k colours there is a rainbow subgraph isomorphic to H, namely, a copy of H with each of its edges assigned a differen...
详细信息
The anti-Ramsey number, ar(G, H) is the minimum integer k such that in any edge colouring of G with k colours there is a rainbow subgraph isomorphic to H, namely, a copy of H with each of its edges assigned a different colour. The notion was introduced by Erdos and Simonovits in 1973. Since then the parameter has been studied extensively. The case when H is a star graph was considered by several graph theorists from the combinatorial point of view. Recently this case received the attention of researchers from the algorithm community because of its applications in interface modelling of wireless networks. To the algorithm community, the problem is known as maximum edge q-colouring problem: Find a colouring of the edges of G, maximizing the number of colours satisfying the constraint that each vertex spans at most q colours on its incident edges. It is easy to see that the maximum value of the above optimization problem equals ar(G, K1,q+1) - 1. In this paper, we study the maximum edge 2-colouring problem from the approx-imation algorithm point of view. The case q = 2 is particularly interesting due to its application in real-life problems. algorithmically, this problem is known to be NP-hard for q - 2. For the case of q = 2, it is also known that no polynomial-time algorithm can approximate to a factor less than 3/2 assuming the unique games conjecture. Feng et al. showed a 2-approximation algorithm for this problem. Later Adamaszek and Popa presented a 5/3-approximation algorithm with the additional assumption that the input graph has a perfect matching. Note that the obvious but the only known algorithm issues different colours to the edges of a maximum matching (say M) and different colours to the connected components of G \ M. In this article, we give a new analysis of the aforementioned algorithm to show that for triangle-free graphs with perfect matching the approximation ratio is 8/5. We also show that this algorithm cannot achieve a factor better than 58/37 o
Many structural models in chemistry, biology, computer science, sociology, and operations research can be analyzed using graph theory. Some examples of these structure models are species movement between regions, mole...
详细信息
Many structural models in chemistry, biology, computer science, sociology, and operations research can be analyzed using graph theory. Some examples of these structure models are species movement between regions, molecular bonds, shortest spanning trees, development of computer algorithms. This paper introduces the edge decomposition of circulant graphs with 2n vertices by different graph classes. These circulant graphs are denoted as C-2n,C-n, where n is the degree of the graph C-2n,C-n. We propose two algorithmic approaches for constructing edge decomposition of C-2n,C-n. With aid of the proposed algorithmic approaches, we construct paths decompositions, trees decompositions, disjoint unions of cycles and trees decompositions, and complete bipartite graphs decompositions of C-2n,C-n. In the end, a recursive construction of an edge decomposition, based on orthogonal edge decompositions, is proposed. This helps in using the mutually orthogonal decompositions of the circulant graphs C2n,n in several applications, such as the design of experiments and binary codes generation. (C) 2022 THE AUTHORS. Published by Elsevier BV on behalf of Faculty of Engineering, Alexandria University.
Suffix trees are an important data structure at the core of optimal solutions to many fundamental string problems, such as exact pattern matching, longest common substring, matching statistics, and longest repeated su...
详细信息
Suffix trees are an important data structure at the core of optimal solutions to many fundamental string problems, such as exact pattern matching, longest common substring, matching statistics, and longest repeated substring. Recent lines of research focused on extending some of these problems to vertex-labeled graphs, either by using efficient ad-hoc approaches which do not generalize to all input graphs, or by indexing difficult graphs and having worst-case exponential complexities. In the absence of an ubiquitous and polynomial tool like the suffix tree for labeled graphs, we introduce the labeled direct product of two graphs as a general tool for obtaining optimal algorithms in the worst case: we obtain conceptually simpler algorithms for the quadratic problems of string matching (SMLG) and longest common substring (LCSP) in labeled graphs. Our algorithms run in time linear in the size of the labeled product graph, which may be smaller than quadratic for some inputs, and their run-time is predictable, because the size of the labeled direct product graph can be precomputed efficiently. We also solve LCSP on graphs containing cycles, which was left as an open problem by Shimohira et al. in 2011. To show the power of the labeled product graph, we also apply it to solve the matching statistics (MSP) and the longest repeated string (LRSP) problems in labeled graphs. Moreover, we show that our (worst-case quadratic) algorithms are also optimal, conditioned on the Orthogonal Vectors Hypothesis. Finally, we complete the complexity picture around LRSP by studying it on undirected graphs.
A connected feedback vertex set of a graph is a connected subgraph of the graph whose removal makes the graph cycle free. In this paper, we give an approximation algorithm that computes a connected feedback vertex set...
详细信息
ISBN:
(纸本)9783031343469;9783031343476
A connected feedback vertex set of a graph is a connected subgraph of the graph whose removal makes the graph cycle free. In this paper, we give an approximation algorithm that computes a connected feedback vertex set of size (1.9091OPT + 6) on 2-connected AT-free graphs with running time O(n(8)m(2)). Also, we give another approximation algorithm that computes a connected feedback vertex set of size (2.9091OPT + 6) on the same graph class with more efficient running time O(min{m(log(n)), n(2)}).
暂无评论