Hitting subgraphs in P4-tidy graphs

摘要

Vertex cover number, which is one of the most basic graph invariants, can be viewed as the smallest number of vertices that hit (or that belong to) every subgraph K2 in a graph G. In this paper, we consider the next two smallest cases of connected graphs, which are the path P3 and the cycle C3; the problem is to minimize the set of vertices that hit every subgraph H in G, where H is one of the two graphs. We focus on computational aspects of these two variations of the vertex cover number. We show that both problems are NP-complete even in the class of graphs that have no induced cycles of length t, where t∈{4,…,8} (in fact, in the P3-hitting case, the problem is NP-complete in even smaller family of graphs, where also triangles are forbidden). On the positive side, we prove a complementary result that in graphs with no induced P4 (the so-called cographs) both problems become linear. Moreover, we consider a generalization of cographs — P4-tidy graphs, for which we establish an efficient algorithm for both problems.