Given a graph G and two independent sets of G, the independent set reconfiguration problem asks whether one independent set can be transformed into the other by moving a single vertex at a time, such that at each inte...
详细信息
ISBN:
(纸本)9783031754081;9783031754098
Given a graph G and two independent sets of G, the independent set reconfiguration problem asks whether one independent set can be transformed into the other by moving a single vertex at a time, such that at each intermediate step we have an independent set of G. We study the complexity of this problem for H-free graphs under the token sliding and token jumping rule. Our contribution is twofold. First, we prove a reconfiguration analogue of Alekseev's theorem for connected graphs H, showing that the problem is PSPACE-complete unless H is a path or a subdivision of the claw. We then show that under the token sliding rule the problem admits a polynomial-time algorithm if the input graph is fork-free, generalizing known results for P4-free graphs and claw-free graphs. This implies a complete classification of the complexity of token sliding in H-free graphs, H being connected or not.
A long-standing open question is which graph class is the most general one permitting constant-time constant-factor approximations for dominating sets. The approximation ratio has been bounded by increasingly general ...
详细信息
ISBN:
(纸本)9783031744976;9783031744983
A long-standing open question is which graph class is the most general one permitting constant-time constant-factor approximations for dominating sets. The approximation ratio has been bounded by increasingly general parameters such as genus, arboricity, or expansion of the input graph. Amiri and Wiederhake considered k-hop domination in graphs of bounded k-hop expansion and girth at least 4k+ 3 [2];the k-hop expansion f(k) of a graph family denotes the maximum ratio of edges to nodes that can be achieved by contracting disjoint subgraphs of radius k and deleting nodes. In this setting, these authors to obtain a simple O(k)-round algorithm achieving approximation ratio Theta(kf(k)). In this work, we study the same setting but derive tight bounds: - A Theta(kf(k))-approximation is possible in k, but not k - 1 rounds. - In 3k rounds an O(k + f(k)(k/(k+1)))-approximation can be achieved. - No constantround deterministic algorithm can achieve approximation ratio o(k + f(k)(k/(k+1))). Our upper bounds hold in the port numbering model with small messages, while the lower bounds apply to local algorithms, i.e., with arbitrary message size and unique identifiers. This means that the constant-time approximation ratio can be sublinear in the edge density of the graph, in a graph class which does not allow a constant approximation. This begs the question whether this is an artefact of the restriction to high girth or can be extended to all graphs of k-hop expansion f(k).
In this paper we establish polynomial-time algorithms for special classes of parity games. In particular we study various constructions for combining graphs that often arise in structural graph theory and show that po...
详细信息
In this paper we establish polynomial-time algorithms for special classes of parity games. In particular we study various constructions for combining graphs that often arise in structural graph theory and show that polynomial-time solvability of parity games is preserved under these operations. This includes the join of two graphs, repeated pasting along vertices, and the addition of a vertex. As a consequence we obtain polynomial time algorithms for parity games whose underlying graph is an orientation of a complete graph (such as tournaments), a complete bipartite graph, a block graph, or a block-cactus graph. These are "classes where the problem was not known to be efficiently solvable before. (C) 2015 Elsevier B.V. All rights reserved.
Computing distances and finding shortest paths in massive real-world networks is a fundamental algorithmic task in network analysis. There are two main approaches to solving this task. On one end are traversal-based a...
详细信息
Transformers have revolutionized the field of machine learning. In particular, they can be used to solve complex algorithmic problems, including graph-based tasks. In such algorithmic tasks a key question is what is t...
详细信息
The graph Coloring Problem (GCP) is an NP-hard problem that aims to color the vertices of a graph using the minimum number of distinct colors, ensuring that adjacent vertices do not share the same color. GCP is widely...
详细信息
Modular decomposition of graphs is a powerful tool for designing efficient algorithms for problems on graphs such as Maximum Weight Stable Set (MWS) and Maximum Weight Clique. Using this tool we obtain O(n (.) m) time...
详细信息
Modular decomposition of graphs is a powerful tool for designing efficient algorithms for problems on graphs such as Maximum Weight Stable Set (MWS) and Maximum Weight Clique. Using this tool we obtain O(n (.) m) time algorithms for MWS on chair- and xbull-free graphs which considerably extend an earlier result on bull- and chair-free graphs by De Simone and Sassano (the chair is the graph with vertices a, b, c, d, e and edges ab, be, cd, be, and the xbull is the graph with vertices a, b, c, d, e, f and edges ab, be, cd, de, bf, cf). Moreover, our algorithm is robust in the sense that we do not have to check in advance whether the input graphs are indeed chair- and xbull-free. (C) 2003 Elsevier B.V. All rights reserved.
Column Generation (CG) is a popular method dedicated to enhancing computational efficiency in large scale Combinatorial Optimization (CO) problems. It reduces the number of decision variables in a problem by solving a...
详细信息
We present efficient (parallel) algorithms for two hierarchical clustering heuristics. We point out that these heuristics can also be applied to solving some algorithmic problems in graphs, including split decompositi...
详细信息
We present efficient (parallel) algorithms for two hierarchical clustering heuristics. We point out that these heuristics can also be applied to solving some algorithmic problems in graphs, including split decomposition. We show that efficient parallel split decomposition induces an efficient parallel parity graph recognition algorithm. This is a consequence of the result of S. Cicerone and D. Di Stefano [7] that parity graphs are exactly those graphs that can be split decomposed into cliques and bipartite graphs, (C) 2000 Academic Press.
A dominating induced matching, also called an efficient edge domination, of a graph G = (V, E) with n = vertical bar V vertical bar vertices and m = vertical bar E vertical bar edges is a subset F subset of E of edges...
详细信息
A dominating induced matching, also called an efficient edge domination, of a graph G = (V, E) with n = vertical bar V vertical bar vertices and m = vertical bar E vertical bar edges is a subset F subset of E of edges in the graph such that no two edges in F share a common endpoint and each edge in E \ F is incident with exactly one edge in F. It is NP-hard to decide whether a graph admits a dominating induced matching or not. In this paper, we design a 1.1467(n)n(0(1)) -time exact algorithm for this problem, improving all previous results. This problem can be redefined as a partition problem that is to partition the vertex set of a graph into two parts I and F, where I induces an independent set (a 0-regular graph) and F induces a perfect matching (a 1-regular graph), After giving several structural properties of the problem, we show that the problem always contains some "good vertices," branching on which by including them to either I or F we can effectively reduce the graph. This leads to a fast exact algorithm to this problem. (C) 2015 Elsevier B.V. All rights reserved.
暂无评论