TL;DR: I prove the variant of this problem in which we can only change matrix entries from 1 to 0 is NP-complete. (I think the original version is NP-complete too, but haven't proved this.)
Rooted Transitive Tree Editing
Another way of stating this problem is to ask for the minimum number of edge changes (additions of new edges or deletions of existing edges) needed to change a given digraph into the transitive closure of a rooted tree -- that is, a rooted tree augmented with all edges $uv$ whenever there is a path from $u$ to $v$. Let's call this graph a rooted transitive tree, and the decision form of this problem "Rooted Transitive Tree Editing":
Given a digraph $G=(V',E')$ and an integer $q$, is it possible to turn $G$ into a rooted transitive tree with at most $q$ edge edits?
I'll call the variant of the problem in which we are only permitted to delete edges "Rooted Transitive Tree Deletion". In the language of the original problem, in this variant we are only allowed to flip matrix entries from 1 to 0. This deletion variant of the problem is NP-complete by reduction from a slightly restricted form of Partition Into Triangles (PIT), as I'll show below. I suspect the full editing version can be shown to be NP-complete using a similar reduction, probably involving making the "handle" gadgets longer paths -- suggestions/extensions welcome!
The basic idea is to create a "triangle handle" vertex for each of the $O(n^3)$ triangles in the input graph, make each input vertex a descendant of the handle of every triangle it belongs to, and then look for a way to keep only the edges from the input graph that are used in a partition into triangles, and only the edges to handle vertices of triangles in this partition, deleting all other edges.
Partition Into Triangles
In Partition Into Triangles, we are given an undirected graph with $3n$ vertices, and ask whether it is possible to partition the vertices into triangles. P. 192 of "Computers and Intractability: A Guide to the Theory of NP-Completeness" (Garey and Johnson, 1979) indicates this problem is NP-complete. Here we need a slightly restricted form of the problem in which every vertex is covered by some triangle. The following simple reduction from the general problem shows the restricted version is still NP-complete. Attach a separate "diamond" to each vertex -- that is, for each $v_i, 1 \le i \le |V|$, add the vertices $x_i$, $y_i$ and $z_i$, and the edges $v_ix_i$, $v_iy_i$, $x_iy_i$, $x_iz_i$ and $y_iz_i$. Every vertex in the modified graph is covered by a triangle, and since the only triangle covering $z_i$ is $x_iy_iz_i$, it must always be chosen, leaving $v_i$ available as before.
Construction
Let $G=(V,E)$ be the input PIT instance, with $|V|=3n$. Let $t$ be the number of triangles in $G$. Note that $t \le {|V| \choose 3}$ and can be computed in polynomial time. We construct an instance $R=(V', E', k)$ of RTTD as follows:
- Create a "plain" vertex $v_i'$ for every vertex $v_i \in V$.
- Create the directed "plain" edges $u_i'v_i'$ and $v_i'u_i'$ for every undirected edge $uv \in E$.
- For the $j$-th triangle $v_av_bv_c$ in $G$:
- Create a "handle" vertex $h_j$.
- Create the directed "handle" edges $h_jv_a'$, $h_jv_b'$ and $h_jv_c'$.
- Create a root vertex $r$, and directed edges from it to every other vertex.
- Set the threshold parameter $q$ to $3t+2|E|-2|V|$.
$G$ is a YES-instance of PIT $\implies$ $R$ is a YES-instance of RTTD. First notice that between any two adjacent vertices $u'$ and $v'$, at least one of the two opposite-pointing directed edges must be deleted. Also, for any triangle $v_iv_jv_k$ in $G$, 3 of the 6 resulting directed edges in $R$ can be deleted so as to produce a transitive 3-path, e.g.:
vj
| \ Edges are directed from high to low
| \
| vi
| /
| /
vk
A partition into triangles uses exactly $|V|$ edges in $G$. Given a partition of $G$ into triangles, we delete all $2(|E|-|V|)$ of the directed edges in $R$ corresponding to edges not used by the partition. For each triangle, we also delete 3 of the 6 directed edges so as to produce a transitive 3-path as shown in the above figure (the order of the vertices in the path is unimportant) -- this deletes a further $|V|$ edges. Finally, we delete directed edges from handle vertices to plain vertices for all unused triangles: There are $t-|V|/3$ unused triangles, each of which has 3 such edges. The final digraph is a rooted transitive tree, and we have deleted in total $2(|E|-|V|)+|V|+3(t-|V|/3)=3t+2|E|-2|V|=q$ directed edges, so $R$ is a YES-instance of RTTD.
$R$ is a YES-instance of RTTD $\implies$ $G$ is a YES-instance of PIT. We know there exists a subset of at most $q=3t+2|E|-2|V|$ directed edges, the deletion of which from $R$ yields a rooted transitive tree $R'$.
No directed edge from the root $r$ to any handle vertex can be deleted, since that handle vertex would then become a second vertex with indegree 0 (in addition to $r$), and a rooted transitive tree must have exactly one such vertex. Nor can a directed edge from $r$ to a plain vertex $v_i'$ be deleted, since by the assumption that every vertex is covered by a triangle, $v_i$ has some handle vertex $h_j$ for an ancestor, and the deletion of $rv_i'$ would imply the deletion of $rh_j'$, which fails as just described.
The budget of directed edge deletions must therefore be allocated between handle edges and plain edges. If a vertex in $G$ participates in multiple triangles, its corresponding plain vertex in $R$ will have multiple handle vertices as ancestors -- but since no handle vertex is the ancestor of any other handle vertex, each plain vertex can choose at most one handle vertex to be its parent in the edited digraph $R'$, and must delete directed edges from all other handle vertices. Thus at most $|V|$ handle edges can survive, meaning that at least $3t-|V|$ handle edges must be deleted in any solution.
We now wish to show that plain edges will be deleted so as to ensure that each handle vertex is either totally "full" or totally "empty" -- that is, that for any handle vertex, either all 3 of its out-edges are preserved, or all 3 are deleted. Say that a vertex in $G$ is assigned to triangle $j$ if $h_jv_i'$ is preserved in $R'$ (not deleted). Each triangle is assigned between 0 and 3 vertices, inclusive. We will show that any valid assignment -- that is, an assignment in which every triangle is assigned either exactly 0 or exactly 3 vertices -- preserves strictly more plain edges, and thus requires strictly fewer deletions of these edges, than any assignment in which some triangle is assigned 1 or 2 vertices.
A valid assignment preserves $|V|$ plain edges, meaning that $2|E|-|V|$ plain edges must be deleted, which together with the $3t-|V|$ handle edges that must be deleted requires a total of $3t+2|E|-2|V|$ edges.
Notice that for any pair of vertices assigned to distinct triangles, there must be no directed edges between their corresponding plain vertices in either direction in $R'$, so if these 2 directed edges exist (i.e., if the vertices are adjacent in $G$) they must both be deleted. IOW, triangle assignments group plain vertices into connected components in $R'$.
Take the assigned vertex counts of the $t$ triangles and sort them in decreasing order. Doing so with a valid assignment produces a list $L^*=333\cdots3000\cdots0$, with $|V|/3$ 3s followed by $t-|V|/3$ 0s. Suppose we have an invalid assignment, producing a list $L$ containing at least one 1 or 2. We will walk along these 2 lists 3 or 6 vertices at a time, comparing the number of preserved plain edges.
- Each triangle assigned 3 vertices preserves 3 plain edges (see ASCII art diagram).
- Each triangle assigned 2 vertices preserves 1 plain edge.
- Each triangle assigned 1 or 0 vertices preserves 0 plain edges.
The longest common prefix of $L$ and $L^*$, consisting of 3s, preserves an equal number of plain edges. Following this, $L$ continues with one of the following cases (with cases having trailing 0s promoted to equivalent cases having trailing 1s):
- 111: Preserves 0+0+0=0 edges (vs. 3 edges for the corresponding 3 from $L^*$).
- 21: Preserves 1+0=1 edge (vs. 3 edges for the corresponding 3 from $L^*$).
- 2211: Preserves 1+1+0+0=2 edges (vs. 6 edges for the corresponding 33 from $L^*$).
- 222: Preserves 1+1+1=3 edges (vs. 6 edges for the corresponding 33 from $L^*$).
Each case preserves strictly fewer edges than does the valid assignment, and any subsequent cases are at least as bad due to the decreasing order. Thus any invalid assignment requires strictly more plain edge deletions and at least as many handle edge deletions, so a solution with $3t+2|E|-2|V|$ edge deletions implies a valid triangle assignment, from which a solution to the original PIT instance can be immediately read off.
The above establishes NP-hardness of the RTTD problem. Clearly the construction takes polynomial time, so the problem is furthermore NP-complete.
