A vertex subset I of a graph G is called a k-path vertex cover if every path on k vertices in G contains at least one vertex from I. The K-PATH VERTEX COVER RECONFIGURATION (K-PVCR) problem asks if one can transform one k-path vertex cover into another via a sequence of k-path vertex covers where each intermediate member is obtained from its predecessor by applying a given reconfiguration rule exactly once. We investigate the computational complexity of K-PVCR from the viewpoint of graph classes under the well-known reconfiguration rules: TS, TJ, and TAR. The problem for k=2, known as the VERTEX COVER RECONFIGURATION (VCR) problem, has been well-studied in the literature. We show that certain known hardness results for VCR on different graph classes can be extended for K-PVCR. In particular, we prove a complexity dichotomy for K-PVCR on general graphs: on those whose maximum degree is three (and even planar), the problem is PSPACE-complete, while on those whose maximum degree is two (i.e., paths and cycles), the problem can be solved in polynomial time. Additionally, we also design polynomial-time algorithms for K-PVCR on trees under each of TJ and TAR. Moreover, on paths, cycles, and trees, we describe how one can construct a reconfiguration sequence between two given k-path vertex covers in a yes-instance. In particular, on paths, our constructed reconfiguration sequence is shortest.

A siphon-trap of a Petri net N is defined as a place set S with S = S, where S = { u| N has an edge from u to a vertex of S} and S = { v| N has an edge from a vertex of S to v}. A minimal siphon-trap is a siphon-trap such that any proper subset is not a siphon-trap. The following polynomial-time algorithms are proposed: (1) FDST for finding, if any, a minimal siphon-trap or even a maximal class of mutually disjoint minimal siphon-traps of a given Petri net; (2) FDSTi that repeats FDST i times in order to extract more minimal siphon-traps than FDST. (3) STFM_T (STFM_Ti, respectively) which is a combination of the Fourier-Motzkin method and FDST (FDSTi) and which has high possibility of finding, if any, at least one minimal-support nonnegative integer invariant.

A siphon (or alternatively a structutal deadlock) of a Petri net is defined as a set S of places such that existence of any edge from a transition t to a place of S implies that there is an edge from some place of S to t. A minimal siphon is a siphon such that any proper subset is not a siphon. The results of the paper are as follows. (1) The problem of deciding whether or not a given Petri net has a minimum siphon (i.e., a minimum-cardinality minimal siphon) is NP-complete. (2) A polynomial-time algorithm to find, if any, a minimal siphon or even a maximal calss of mutually disjoint minimal siphons of a general Petri net is proposed.

A minimal siphon (or alternatively a structural deadlock) of a Petri net is defined as a minimal set S of places such that existence of any edge from a transition t to a place of S implies that there is an edge from some place of S to t. The subject of the paper is to find a minimal siphon containing a given set of specified places of a general Petri net.

In this paper, we propose an algorithm of O(|V|min{k,|V|,|A|}|A|) time complexity for finding all k-edge-connected components of a given digraph D=(V,A) and a positive integer k. When D is symmetric, incorporating a preprocessing reduces this time complexity to O(|A|+|V|2+|V|min{k,|V|}min{k|V|,|A|}), which is at most O(|A|+k2|V|2).