In the solution discovery variant of a vertex (edge) subset problem Π on graphs, we are given an initial configuration of tokens on the vertices (edges) of an input graph G together with a budget b. The question is whether we can transform this configuration into a feasible solution of Π on G with at most b modification steps. We consider the token sliding variant of the solution discovery framework, where each modification step consists of sliding a token to an adjacent vertex (edge). The framework of solution discovery was recently introduced by Fellows et al. [ECAI 2023] and for many solution discovery problems the classical as well as the parameterized complexity has been established. In this work, we study the kernelization complexity of the solution discovery variants of Vertex Cover, Independent Set, Dominating Set, Shortest Path, Matching, and Vertex Cut with respect to the parameters number of tokens k, discovery budget b, as well as structural parameters such as pathwidth.

Under the reconfiguration framework, we consider the various ways that a target graph H is a minor of a host graph G, where a subgraph of G can be transformed into H by means of edge contraction (replacement of both endpoints of an edge by a new vertex adjacent to any vertex adjacent to either endpoint). Equivalently, an H-model of G is a labeling of the vertices of G with the vertices of H, where the contraction of all edges between identically-labeled vertices results in a graph containing representations of all edges in H. We explore the properties of G and H that result in a connected reconfiguration graph, in which nodes represent H-models and two nodes are adjacent if their corresponding H-models differ by the label of a single vertex of G. Various operations on G or H are shown to preserve connectivity. In addition, we demonstrate properties of graphs G that result in connectivity for the target graphs K_2, K_3, and K_4, including a full characterization of graphs G that result in connectivity for K_2-models, as well as the relationship between connectivity of G and other H-models.

The $k$-atomicity property can be used to describe the consistency of data operations in large distributed storage systems. The weak consistency guarantees offered by such systems are seen as a necessary compromise in view of Brewer's CAP principle. The $k$-atomicity property requires that every read operation obtains a value that is at most $k$ updates (writes) old and becomes a useful way to quantify weak consistency if $k$ is treated as a variable that can be computed from a history of operations. Specifically, the value of $k$ quantifies how far the history deviates from the atomicity (linearizability) property for read/write registers. We address the problem of computing $k$ indirectly by solving the $k$-atomicity verification problem ($k$-AV): given a history of read/write operations and a positive integer $k$, decide whether the history is $k$-atomic. Gibbons and Korach showed that in general this problem is NP-complete when $k=1$ and hence not solvable in polynomial time unless $P = NP$. In this paper we present two algorithms that solve the $k$-AV problem for any $k \geq 3$ in special cases. Similarly to known solutions for $k = 1$ and $k = 2$, both algorithms assume that all the values written to a given object are distinct. The first algorithm places an additional restriction on the structure of the input history and solves $k$-AV in $O(n^2 + n \cdot k \log k)$ time, where $n$ is the number of operations in the history. The second algorithm does not place any additional restrictions on the input but is efficient only when $k$ is small and when concurrency among write operations is limited. Its time complexity is $O(n^2)$ if both $k$ and our particular measure of write concurrency are bounded by constants.

In this paper, we study covering and domination problems on directed graphs. Although undirected Vertex Cover and Edge Dominating Set are well-studied classical graph problems, the directed versions have not been studied much due to the lack of clear definitions. We give natural definitions for Directed r-In (Out) Vertex Cover and Directed (p,q)-Edge Dominating Set as directed generations of Vertex Cover and Edge Dominating Set. For these problems, we show that (1) Directed r-In (Out) Vertex Cover and Directed (p,q)-Edge Dominating Set are NP-complete on planar directed acyclic graphs except when r=1 or (p,q)=(0,0), (2) if r>=2, Directed r-In (Out) Vertex Cover is W[2]-hard and (c*ln k)-inapproximable on directed acyclic graphs, (3) if either p or q is greater than 1, Directed (p,q)-Edge Dominating Set is W[2]-hard and (c*ln k)-inapproximable on directed acyclic graphs, (4) all problems can be solved in polynomial time on trees, and (5) Directed (0,1),(1,0),(1,1)-Edge Dominating Set are fixed-parameter tractable in general graphs. The first result implies that (directed) r-Dominating Set on directed line graphs is NP-complete even if r=1.

Given a Boolean formula and a satisfying assignment, a flip is an operation that changes the value of a variable in the assignment so that the resulting assignment remains satisfying. We study the problem of computing the shortest sequence of flips (if one exists) that transforms a given satisfying assignment $s$ to another satisfying assignment $t$ of an input Boolean formula. Earlier work characterized the complexity of deciding the existence of a sequence of flips between two given satisfying assignments using Schaefer's framework for classification of Boolean formulas. We build on it to provide a trichotomy for the complexity of finding the shortest sequence of flips and show that it is either in P, NP-complete, or PSPACE-complete. Our result adds to the growing set of complexity results known for shortest reconfiguration sequence problems by providing an example where the shortest sequence can be found in polynomial time even though the sequence flips variables that have the same value in both $s$ and $t$. This is in contrast to most reconfiguration problems studied so far, where polynomial-time algorithms for computing the shortest path were known only for cases where the path modified no more than the symmetric difference of $s$ and $t$. Our proof uses Birkhoff's representation theorem on a set system that we show to be a distributive lattice. The technique provides insights and can perhaps be used for other reconfiguration problems as well.

The k-atomicity property can be used to describe the consistency of data operations in large distributed storage systems. The weak consistency guarantees offered by such systems are seen as a necessary compromise in view of Brewer's CAP principle. The k-atomicity property requires that every read operation obtains a value that is at most k updates (writes) old, and becomes a useful way to quantify weak consistency if k is treated as a variable that can be computed from a history of operations. Specifically, the value of k quantifies how far the history deviates from Lamport's atomicity property for read/write registers. We address the problem of computing k indirectly by solving the k-atomicity verification problem (k-AV): given a history of read/write operations and a positive integer k, decide whether the history is k-atomic. Gibbons and Korach showed that in general this problem is NP-complete when k = 1, and hence not solvable in polynomial time unless P = NP. In this paper we present two algorithms that solve the k-AV problem for any k >= 2 in special cases. Similarly to known solutions for k = 1 and k = 2, both algorithms assume that all the values written to a given object are distinct. The first algorithm places an additional restriction on the structure of the input history and solves k-AV in O(n^2 + n (k log k) time. The second algorithm does not place any additional restrictions on the input but is efficient only when k is small and when concurrency among write operations is limited. Its time complexity is O(n2) if both k and our particular measure of write concurrency are bounded by constants.

The problem of deciding, given a graph G and two vertices s and t, whether there exists an induced path of given parity between s and t in G is known to be NP-complete. We show how to solve the problem in O(|V (G)|7) time, when the input graph is planar. We use techniques from the theory of graph minors as well as the theory of perfect graphs.

Three pointer based parallel join algorithms are presented and analyzed for environments in which secondary storage is made transparent to the programmer through memory mapping. P.A. Buhr et al. (1992) show that data structures such as B Trees, R Trees and graph data structures can be implemented as efficiently and effectively in this environment as in a traditional environment using explicit I/O. We show how higher order algorithms, in particular parallel join algorithms, behave in a memory mapped environment. A quantitative analytical model has been developed to conduct performance analysis of the parallel join algorithms. The model has been validated by experiments.

Article μDatabase: parallelism in a memory-mapped environment (research summary) Share on Authors: Peter A. Buhr Department of Computer Science, University of Waterloo, Waterloo, Ontario, Canada N2L 3G1 Department of Computer Science, University of Waterloo, Waterloo, Ontario, Canada N2L 3G1View Profile , Anil K. Goel Department of Computer Science, University of Waterloo, Waterloo, Ontario, Canada N2L 3G1 Department of Computer Science, University of Waterloo, Waterloo, Ontario, Canada N2L 3G1View Profile , Naomi Nishimura Department of Computer Science, University of Waterloo, Waterloo, Ontario, Canada N2L 3G1 Department of Computer Science, University of Waterloo, Waterloo, Ontario, Canada N2L 3G1View Profile , Prabhakar Ragde Department of Computer Science, University of Waterloo, Waterloo, Ontario, Canada N2L 3G1 Department of Computer Science, University of Waterloo, Waterloo, Ontario, Canada N2L 3G1View Profile Authors Info & Claims SPAA '96: Proceedings of the eighth annual ACM symposium on Parallel Algorithms and ArchitecturesJune 1996 Pages 196–199https://doi.org/10.1145/237502.237547Online:24 June 1996Publication History 0citation143DownloadsMetricsTotal Citations0Total Downloads143Last 12 Months0Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Traditional theoretical shared memory parallel models have been based on a number of assumptions which simultaneously simplify solutions to problems and distance the models from actual parallel machines. One such assumption is that processors work together in a synchronous fashion. Recent work has focused on finding a model that captures the essence of computation by processors communicating asynchronously through shared memory. In this paper, a general framework and set of criteria used to analyze these models, including the complexity analysis of several fundamental algorithmic paradigms, are considered. A general asynchronous model is introduced and how it satisfies these criteria is demonstrated. In this model, $O(\log p)$ algorithms are demonstrated for solving p-input versions of the problems of AND, OR, parity, maximum, minimum, and list ranking. To handle list ranking, a technique of analyzing algorithms is developed in which the set of tasks that are to be executed depends on the processor schedules.

Article Asynchronous shared memory parallel computation Share on Author: N. Nishimura University of Toronto University of TorontoView Profile Authors Info & Claims SPAA '90: Proceedings of the second annual ACM symposium on Parallel algorithms and architecturesMay 1990 Pages 76–84https://doi.org/10.1145/97444.97672Online:01 May 1990Publication History 39citation341DownloadsMetricsTotal Citations39Total Downloads341Last 12 Months5Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access