En el problema de eliminación de aristas de co-grafo dirigido, se nos da un grafo dirigido y un entero , y la pregunta es si podemos eliminar, como máximo, aristas para que el grafo resultante sea un co-grafo dirigido. En este documento, hacemos dos contribuciones menores. En primer lugar, mostramos que el problema es NP-duro. Luego, mostramos que los co-grafos dirigidos están completamente caracterizados por ocho estructuras prohibidas, cada una con, como máximo, seis aristas. Basándonos en las propiedades de simetría y varias observaciones refinadas, desarrollamos un algoritmo de ramificación con un tiempo de ejecución de , que es significativamente más eficiente en comparación con el algoritmo de fuerza bruta, que tiene un tiempo de ejecución de .