Selecting an Induced Subgraph from a DAG with Specific Conditions

Question

I am working with a Directed Acyclic Graph (DAG), denoted as $G$. The graph has a specific constraint where the out-degree of each vertex in $G$ is at most $2$.

My objective is to select an induced subgraph from $G$ that satisfies the following conditions:

1. It includes at least $\frac{3}{7}$ of the total vertices in $G$.
2. It does not contain any directed path of length $2$.

I am seeking a solution that can accomplish this in polynomial time.

So far, my observations are limited. I have noted that if we have chosen vertices $u$ and $v$ such that there is a directed edge from $u$ to $v$ in $G$, we cannot select a vertex $w$ that has a directed edge to $u$ in $G$.

I have spent considerable time pondering this problem but have not been able to make any significant progress or observations. Any insights or suggestions would be greatly appreciated.

Answer 1

Considering any induced subgraph of size 3 or more of a transitively-oriented complete graph will have a directed path of length 2, you are going to have to further specify what you want your algorithm to do in the case there is no such induced subgraph.