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

PROFILE AND NEIGHBOURHOOD COMPLEXITY OF graphS WITH EXCLUDED MINORS AND TREE-STRUCTURED graphS

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Beaudou, Laurent Bok, Jan Foucaud, Florent Quiroz, Daniel A. Raymond, Jean-Florent Université Clermont Auvergne CNRS Clermont Auvergne INP Mines Saint-Étienne LIMOS Clermont-Ferrand63000 France Department of Algebra Faculty of Mathematics and Physics Charles University Sokolovská 83 Prague 818675 Czech Republic Instituto de Ingeniería Matemática Centro de Investigación y Mode-lamiento de Fenómenos Aleatorios - Valparaíso CIMFAV Universidad de Valparaíso Valparaíso Chile Univ. Lyon CNRS ENS de Lyon Université Claude Bernard Lyon 1 LIP UMR5668 Lyon France

The r-neighbourhood complexity of a graph G is the function counting, for a given integer k, the largest possible number, over all vertex-subsets A of size k, of subsets of A realized as the intersection between the r-neighbourhood of some vertex and A. A refinement of this notion is the r-profile complexity, that counts the maximum number of distinct distance-vectors from any vertex to the vertices of A, ignoring distances larger than r. Typically, in structured graph classes such as graphs of bounded VC-dimension or chordal graphs, these functions are bounded, leading to insights into their structural properties and efficient algorithms. We improve existing bounds on the r-profile complexity (and thus on the r-neighbourhood complexity) for graphs in several structured graph classes. We show that the r-profile complexity of graphs excluding Kh as a minor is in Oh(r3h−3k). For graphs of treewidth at most t, we give a bound in Ot(rt+1k), which is tight up to a function of t as a factor. These bounds improve results of Joret and Rambaud and answer a question of their paper [Combinatorica, 2024]. We also apply our methods to other classes of bounded expansion such as graphs excluding a fixed complete graph as a subdivision. For outerplanar graphs, we can improve our treewidth bound by a factor of r and conjecture that a similar improvement holds for graphs with bounded simple treewidth. For graphs of treelength at most , we give the upper bound of O(k(r2( + 1)k)), which we improve to O (k · (r2k + r2k2)) in the case of chordal graphs and O(k2r) for interval graphs. Our bounds also imply relations between the order, diameter and metric dimension of graphs in these classes, improving results from [Beaudou et al., SIDMA 2017]. Copyright © 2025, The Authors. All rights reserved.

关键词： graph algorithms

Towards Optimal Distributed Delta Coloring

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Jakob, Manuel Maus, Yannic

The ∆-vertex coloring problem has become one of the prototypical problems for understanding the complexity of local distributed graph problems on constant-degree graphs. The major open problem is whether the problem can be solved deterministically in logarithmic time, which would match the lower bound [Chang et al., FOCS’16]. Despite recent progress in the design of efficient ∆-coloring algorithms, there is currently a polynomial gap between the upper and lower bounds. In this work we present a O(log n)-round deterministic ∆-coloring algorithm for dense constant-degree graphs, matching the lower bound for the problem on general graphs. For general ∆ the algorithms’ complexity is min{Oe(log5/3 n), O(∆ + log n)}. All recent distributed and sublinear graph coloring algorithms (also for coloring with more than ∆ colors) decompose the graph into sparse and dense parts. Our algorithm works for the case that this decomposition has no sparse vertices. Ironically, in recent (randomized) ∆-coloring algorithms, dealing with sparse parts was relatively easy and these dense parts arguably posed the major hurdle. We present a solution that addresses the dense parts and may have the potential for extension to sparse parts. Our approach is fundamentally different from prior deterministic algorithms and hence hopefully contributes towards designing an optimal algorithm for the general case. Additionally, we leverage our result to also obtain a randomized min{Oe(log5/3 log n), O(∆ + log log n)}-round algorithm for ∆-coloring dense graphs that also matches the lower bound for the problem on general constant-degree graphs [Brandt et al.;STOC’16]. Copyright © 2025, The Authors. All rights reserved.

关键词： graph algorithms

Representation Number of Word-Representable Split graphs

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Dwary, Tithi Mozhui, Khyodeno Krishna, K.V. Indian Institute of Technology Guwahati India

A split graph is a graph whose vertex set can be partitioned into a clique and an independent set. The word-representability of split graphs was studied in a series of papers in the literature, and the class of word-representable split graphs was characterized through semi-transitive orientation. Nonetheless, the representation number of this class of graphs is still not known. In general, determining the representation number of a word-representable graph is an NP-complete problem. In this work, through an algorithmic procedure, we show that the representation number of the class of word-representable split graphs is at most three. Further, we characterize the class of word-representable split graphs as well as the class of split comparability graphs which have representation number exactly three. © 2025, CC BY.

关键词： graph algorithms

On the Complexity of Minimising the Moving Distance for Dispersing Objects

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Honorato-Droguett, Nicolás Kurita, Kazuhiro Hanaka, Tesshu Ono, Hirotaka Nagoya University Japan Kyushu University Japan

We study Geometric graph Edit Distance (GGED), a graph-editing model to compute the minimum edit distance of intersection graphs that uses moving objects as an edit operation. We first show an O(n log n)-time algorithm that minimises the total moving distance to disperse unit intervals. This algorithm is applied to render a given unit interval graph (i) edgeless, (ii) acyclic and (iii) k-clique-free. We next show that GGED becomes strongly NP-hard when rendering a weighted interval graph (i) edgeless, (ii) acyclic and (iii) k-clique-free. Lastly, we prove that minimising the maximum moving distance for rendering a unit disk graph edgeless is strongly NP-hard over the L1 and L2 distances. © 2025, CC BY.

关键词： graph algorithms

FLUCTUATIONS OF THE GIANT OF POISSON RANDOM graphS

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Clancy, David University of Wisconsin Department of Mathematics United States

Enriquez, Faraud, and Lemaire (2023) have established process-level fluctuations for the giant of the dynamic Erdős-Rényi random graph above criticality and show that the limit is a centered Gaussian process with continuous sample paths. A random walk proof was recently obtained by Corujo, Limic and Lemaire (2024). We show that a similar result holds for rank-one inhomogeneous models whenever the empirical weight distribution converges to a limit and its second moment converges as *** Codes 60F17, 05C80 Copyright © 2025, The Authors. All rights reserved.

关键词： graph algorithms

When MIS and Maximal Matching are Easy in the Congested Clique

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Censor-Hillel, Keren Even, Tomer Flin, Maxime Halldórsson, Magnús M. Department of Computer Science Technion Department of Computer Science Reykjavik University Reykjavik Iceland

Two of the most fundamental distributed symmetry-breaking problems are that of finding a maximal independent set (MIS) and a maximal matching (MM) in a graph. It is a major open question whether these problems can be solved in constant rounds of the all-to-all communication model of Congested Clique, with O(log log ∆) being the best upper bound known (where ∆ is the maximum degree). We explore in this paper the boundary of the feasible, asking for which graphs we can solve the problems in constant rounds. We find that for several graph parameters, ranging from sparse to highly dense graphs, the problems do have a constant-round solution. In particular, we give algorithms that run in constant rounds when: • the average degree is at most d(G) ≤ 2O(√log n), • the neighborhood independence number is at most β(G) ≤ 2O(√log n), or • the independence number is at most α(G) ≤ |V (G)|/d(G)µ, for any constant µ > 0. Further, we establish that these are tight bounds for the known methods, for all three parameters, suggesting that new ideas are needed for further progress. © 2025, CC BY.

关键词： graph algorithms

Enumerating minimal dominating sets and variants in chordal bipartite graphs

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Castelo, Emanuel Defrain, Oscar Gomes, Guilherme C.M. Aix-Marseille Université CNRS LIS Marseille13009 France LIRMM Université de Montpellier CNRS Montpellier France Universidade Federal de Minas Gerais Belo Horizonte Brazil

Enumerating minimal dominating sets with polynomial delay in bipartite graphs is a long-standing open problem. To date, even the subcase of chordal bipartite graphs is open, with the best known algorithm due to Golovach, Heggernes, Kanté, Kratsch, Sæther, and Villanger running in incremental-polynomial time. We improve on this result by providing a polynomial delay and space algorithm enumerating minimal dominating sets in chordal bipartite graphs. Additionally, we show that the total and connected variants admit polynomial and incremental-polynomial delay algorithms, respectively, within the same class. This provides an alternative proof of a result by Golovach et al. for total dominating sets, and answers an open question for the connected variant. Finally, we give evidence that the techniques used in this paper cannot be generalized to bipartite graphs for (total) minimal dominating sets, unless P = NP, and show that enumerating minimal connected dominating sets in bipartite graphs is harder than enumerating minimal transversals in general hypergraphs. © 2025, CC BY.

关键词： graph algorithms

On the time complexity of finding a well-spread perfect matching in bridgeless cubic graphs

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Ghanbari, Babak Šámal, Robert Computer Science Institute Charles University Prague Czech Republic

We present an algorithm for finding a perfect matching in a 3-edge-connected cubic graph that intersects every 3-edge cut in exactly one edge. Specifically, we propose an algorithm with a time complexity of O(nlog4 n), which significantly improves upon the previously known O(n3)-time algorithms for the same problem. The technique we use for the improvement is efficient use of cactus model of 3-edge cuts. As an application, we use our algorithm to compute embeddings of 3-edge-connected cubic graphs with limited number of singular edges (i.e., edges that are twice in the boundary of one face) in O(nlog4 n) time;this application contributes to the study of the well-known Cycle Double Cover conjecture. Copyright © 2025, The Authors. All rights reserved.

关键词： graph algorithms

graphs of unbounded linear cliquewidth must transduce all trees

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Bojańczyk, Mikolaj Ohlmann, Pierre

The Pathwidth Theorem states that if a class of graphs has unbounded pathwidth, then it contains all trees as graph minors. We prove a similar result for dense graphs: if a class of graphs has unbounded linear cliquew... 详细信息

关键词： graph algorithms