Search

Graph editing problems offer an interesting perspective on sub- and supergraph identification problems for a large variety of target properties. They have also attracted significant attention in recent years, particularly in the area of parameterized complexity as the problems have rich parameter ecologies. In this paper we examine generalisations of the notion of editing a graph to obtain a regular subgraph. In particular we extend the notion of regularity to include two variants of edge-regularity along with the unifying constraint of strong regularity. We present a number of results, with the central observation that these problems retain the general complexity profile of their regularity-based inspiration: when the number of edits k and the maximum degree r are taken together as a combined parameter, the problems are tractable (i.e. in FPT ), but are otherwise intractable. We also examine variants of the basic editing to obtain a regular subgraph problem from the perspective of parameterizing by the treewidth of the input graph. In this case the treewidth of the input graph essentially becomes a limiting parameter on the natural k + r parameterization. [ABSTRACT FROM AUTHOR]

A subset F of vertices of a graph G is called a vertex cover P t ( V C P t ) set if every path of order t in G contains at least one vertex from F . The vertex cover P t ( V C P t ) problem is to find a minimum V C P t set in a graph. The V C P t problem is NP-complete for any integer t ≥ 2 . In this paper, we restrict our attention to the V C P 4 problem and present an FPT algorithm with runtime O ∗ ( 3 k ) for the V C P 4 problem. The algorithm constructs a V C P 4 set of size at most k in a given graph G , or reports that no such V C P 4 set exists in G . [ABSTRACT FROM AUTHOR]