检索结果-内蒙古大学图书馆

graph Inference with Effective Resistance Queries

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Bennett, Huck Black, Mitchell Nayyeri, Amir Warton, Evelyn University of Colorado Boulder United States University of California San Diego United States Oregon State University United States

The goal of graph inference is to design algorithms for learning properties of a hidden graph using queries to an oracle that returns information about the graph. graph reconstruction, verification, and property testing are all special cases of graph inference. In this work, we study graph inference using an oracle that returns the effective resistance (ER) distance between a given pair of vertices. Effective resistance is a natural notion of distance that arises from viewing graphs as electrical circuits, and has many applications. However, it has received little attention from a graph inference perspective. Indeed, although it is known that an n-vertex graph can be uniquely reconstructed by making all (n2) = Θ(n2) possible ER queries, very little else is known. We address this and show a number of fundamental results in this model, including: 1. O(n)-query algorithms for testing whether a graph is a tree;deciding whether two graphs are equal assuming one is a subgraph of the other;and testing whether a given vertex (or edge) is a cut vertex (or cut edge). 2. Property testing algorithms, including for testing whether a graph is vertex-biconnected and whether it is edge-biconnected. We also give a reduction that shows how to adapt property testing results from the well-studied bounded-degree model to our model with ER queries. This yields ER-query-based algorithms for testing k-connectivity, bipartiteness, planarity, and containment of a fixed subgraph. 3. graph reconstruction algorithms, including an algorithm for reconstructing a graph from a low-width tree decomposition;a Θ(k2)-query, polynomial-time algorithm for recovering the entire adjacency matrix A of the hidden graph, given A with k of its entries deleted;and a k-query, exponential-time algorithm for the same task. We additionally compare the relative power of ER queries and shortest path queries, which are closely related and better studied. Interestingly, we show that the two query models are incomparabl

关键词： graph algorithms

On Optimizing Locality of graph Transposition on Modern Architectures

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Esfahani, Mohsen Koohi Vandierendonck, Hans

This paper investigates the shared-memory graph Transposition (GT) problem, a fundamental graph algorithm that is widely used in graph analytics and scientific computing. Previous GT algorithms have significant memory requirements that are proportional to the number of vertices and threads which obstructs their use on large graphs. Moreover, atomic memory operations have become comparably fast on recent CPU architectures, which creates new opportunities for improving the performance of concurrent atomic accesses in GT. We design PoTra, a GT algorithm which leverages graph structure and processor and memory architecture to optimize locality and performance. PoTra limits the size of additional data structures close to CPU cache sizes and utilizes the skewed degree distribution of graph datasets to optimize locality and performance. We present the performance model of PoTra to explain the connection between cache and memory response times and graph locality. Our evaluation of PoTra on three CPU architectures and 20 real-world and synthetic graph datasets with up to 128 billion edges demonstrates that PoTra achieves up to 8.7 times speedup compared to previous works and if there is a performance loss it remains limited to 15.7%, on average. © 2025, CC BY.

关键词： graph algorithms

Linear-Time graph Programs without Preconditions

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Alaoui, Ziad Ismaili Plump, Detlef Department of Computer Science University of Liverpool Liverpool United Kingdom Department of Computer Science University of York York United Kingdom

We report on a recent breakthrough in rule-based graph programming, which allows us to reach the time complexity of imperative linear-time algorithms. In general, achieving the complexity of graph algorithms in conventional languages using graph transformation rules is challenging due to the cost of graph matching. Previous work demonstrated that with rooted rules, certain algorithms can be executed in linear time using the graph programming language GP 2. However, for non-destructive algorithms that retain the structure of input graphs, achieving linear runtime required input graphs to be connected and of bounded node degree. In this paper, we overcome these preconditions by enhancing the graph data structure generated by the GP 2 compiler and exploiting the new structure in programs. We present three case studies, a cycle detection program, a program for numbering the connected components of a graph, and a breadth-first search program. Each of these programs runs in linear time on both connected and disconnected input graphs with arbitrary node degrees. We give empirical evidence for the linear time complexity by using timings for various classes of input graphs. © 2025, CC BY.

关键词： graph algorithms

Local Problems in Trees Across a Wide Range of Distributed Models 28

学校读者我要写书评

暂无评论

Local Problems in Trees Across a Wide Range of Distributed M...

28th International Conference on Principles of Distributed Systems, OPODIS 2024

作者： Dhar, Anubhav Kujawa, Eli Lievonen, Henrik Modanese, Augusto Muftuoglu, Mikail Studený, Jan Suomela, Jukka Aalto University Espoo Finland Indian Institute of Technology Kharagpur India University of Illinois Urbana-ChampaignIL United States

ISBN: (纸本)9783959773607

The randomized online-LOCAL model captures a number of models of computing;it is at least as strong as all of these models: the classical LOCAL model of distributed graph algorithms, the quantum version of the LOCAL model, finitely dependent distributions [e.g. Holroyd 2016], any model that does not violate physical causality [Gavoille, Kosowski, Markiewicz, DISC 2009], the SLOCAL model [Ghaffari, Kuhn, Maus, STOC 2017], and the dynamic-LOCAL and online-LOCAL models [Akbari et al., ICALP 2023]. In general, the online-LOCAL model can be much stronger than the LOCAL model. For example, there are locally checkable labeling problems (LCLs) that can be solved with logarithmic locality in the online-LOCAL model but that require polynomial locality in the LOCAL model. However, in this work we show that in trees, many classes of LCL problems have the same locality in deterministic LOCAL and randomized online-LOCAL (and as a corollary across all the above-mentioned models). In particular, these classes of problems do not admit any distributed quantum advantage. We present a near-complete classification for the case of rooted regular trees. We also fully classify the super-logarithmic region in unrooted regular trees. Finally, we show that in general trees (rooted or unrooted, possibly irregular, possibly with input labels) problems that are global in deterministic LOCAL remain global also in the randomized online-LOCAL model. © Anubhav Dhar, Eli Kujawa, Henrik Lievonen, Augusto Modanese, Mikail Muftuoglu, Jan Studený, and Jukka Suomela.

关键词： graph algorithms

Fast FPT algorithms for Grundy Number on Dense graphs 11th

学校读者我要写书评

暂无评论

Fast FPT Algorithms for Grundy Number on Dense Graphs

11th International Conference on algorithms and Discrete Applied Mathematics, CALDAM 2025

作者： Ghasemi Nezhad, Sina Moghaddas, Maryam Panolan, Fahad Department of Mathematical Sciences Sharif University of Technology Tehran Iran School of Computer Science University of Leeds Leeds United Kingdom

ISBN: (纸本)9783031834370

In this paper, we investigate the Grundy Coloring problem for graphs with a cluster modulator, a structure commonly found in dense graphs. The Grundy chromatic number, representing the maximum number of colors needed for the first-fit coloring of a graph in the worst-case vertex ordering, is known to be W[1]-hard when parameterized by the number of colors required by the most adversarial ordering. We focus on fixed-parameter tractable (FPT) algorithms for solving this problem on graph classes characterized by dense substructures, specifically those with a cluster modulator. A cluster modulator is a vertex subset whose removal results in a cluster graph (a disjoint union of cliques). We present FPT algorithms for graphs where the cluster graph consists of one, two, or k cliques, leveraging the cluster modulator’s properties to achieve the best-known FPT runtimes, parameterized by both the modulator’s size and the number of cliques. © The Author(s), under exclusive license to Springer Nature Switzerland AG 2025.

关键词： graph algorithms

Efficient Top-k Frequent Subgraph Mining Using Tight Upper and Lower Bounds 51st

学校读者我要写书评

暂无评论

Efficient Top-k Frequent Subgraph Mining Using Tight Upper a...

51st International Conference on Very Large Data Bases, VLDB 2025

作者： Lee, Seonho Lee, Yeunjun Park, Kunsoo Seoul National University Korea Republic of

Frequent sub graph mining is an important and well-studied problem with numerous applications such as the prediction of protein functionalities and graph indexing. Many studies use the minimum image-based support (MNI) to measure the frequency of sub graphs in single graph mining. Given a graph G and an integer k, top-k frequent sub graph mining is to find top-: frequent sub graphs in the graph G based on MNI. However, there are two main challenges in top-k frequent sub graph mining. (1) Computing MNI is time consuming.(2) The number of sub graphs for which MNI should be computed is large. In this paper, we propose a novel algorithm Minting to address these challenges. We propose a method to significantly reduce the number of sub graphs for which MNI computation is required by using a tight upper bound of the MNI value. We also improve the computation of MNI itself by utilizing both alower bound and an upper bound of the MNI value. Experiments shows that our algorithm outperforms the state-of-the-art algorithms by up to three orders of magnitude in terms of the elapsed time. Our algorithm is also a feasible solution for this challenging problem, even for large k. © 2025, VLDB Endowment, All rights reserved.

关键词： graph algorithms

Parameterized Saga of First-Fit and Last-Fit Coloring 42

学校读者我要写书评

暂无评论

Parameterized Saga of First-Fit and Last-Fit Coloring

42nd International Symposium on Theoretical Aspects of Computer Science, STACS 2025

作者： Agrawal, Akanksha Lokshtanov, Daniel Panolan, Fahad Saurabh, Saket Verma, Shaily Indian Institute of Technology Madras India University of California Santa BarbaraCA United States School of Computer Science University of Leeds United Kingdom The Institute of Mathematical Sciences HBNI Chennai India Department of Informatics University of Bergen Norway Algorithm Engineering Group Hasso Plattner Institute Potsdam Germany

ISBN: (纸本)9783959773652

The classic greedy coloring algorithm considers the vertices of an input graph G in a given order and assigns the first available color to each vertex v in G. In the Grundy Coloring problem, the task is to find an ordering of the vertices that will force the greedy algorithm to use as many colors as possible. In the Partial Grundy Coloring, the task is also to color the graph using as many colors as possible. This time, however, we may select both the ordering in which the vertices are considered and which color to assign the vertex. The only constraint is that the color assigned to a vertex v is a color previously used for another vertex if such a color is available. Whether Grundy Coloring and Partial Grundy Coloring admit fixed-parameter tractable (FPT) algorithms, algorithms with running time f(k)nO(1), where k is the number of colors, was posed as an open problem by Zaker and by Effantin et al., respectively. Recently, Aboulker et al. (STACS 2020 and Algorithmica 2022) resolved the question for Grundy Coloring in the negative by showing that the problem is W[1]-hard. For Partial Grundy Coloring, they obtain an FPT algorithm on graphs that do not contain Ki,j as a subgraph (a.k.a. Ki,j-free graphs). Aboulker et al. re-iterate the question of whether there exists an FPT algorithm for Partial Grundy Coloring on general graphs and also asks whether Grundy Coloring admits an FPT algorithm on Ki,j-free graphs. We give FPT algorithms for Partial Grundy Coloring on general graphs and for Grundy Coloring on Ki,j-free graphs, resolving both the questions in the affirmative. We believe that our new structural theorems for partial Grundy coloring and "representative-family" like sets for Ki,j-free graphs that we use in obtaining our results may have wider algorithmic applications. © Akanksha Agrawal, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, and Shaily Verma.

关键词： graph algorithms

algorithms and Hardness Results for the (3, 1)-Cover Problem 11th

学校读者我要写书评

暂无评论

Algorithms and Hardness Results for the (3, 1)-Cover Pro...

11th International Conference on algorithms and Discrete Applied Mathematics, CALDAM 2025

作者： Madani, Amirali Maheshwari, Anil Miraftab, Babak Roy, Bodhayan Carleton University OttawaON Canada IIT Kharagpur Kharagpur India

ISBN: (纸本)9783031834370

A connected graph has a (k,)-cover if each of its edges is contained in at least cliques of order k. Motivated by recent advances in extremal combinatorics and the literature on edge modification problems, we study the algorithmic version of the (3, 1)-cover problem. Given a connected graph G, the (k, 1)-cover problem is to find the minimum number of non-edges of G, whose addition to G yields a graph with a (k, 1)-cover. We show that the (3, 1)-cover problem is NP-complete for general graphs. Moreover, we show that it admits no polynomial-time constant-factor approximation algorithm unless P=NP. However, we show that the (3, 1)-cover problem can be solved in polynomial time when the input graph is chordal. © The Author(s), under exclusive license to Springer Nature Switzerland AG 2025.

关键词： graph algorithms

GENERALIZED graph CODES AND THIER MINIMUM DISTANCES

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Fujii, Naoki Graduate School of Fundamental Science and Engineering Waseda University Japan

graph code is a linear code obtained from linear codes C and a certain bipartite graph G. In this paper, I propose an expansion of the definition of graph code to general -partite, and give its lower bound of minimum distance. I also give an example of generalized graph code and calculate its parameters [n, k, d]. Copyright © 2025, The Authors. All rights reserved.

关键词： graph algorithms