4
$\begingroup$

An ancestry matrix $M$ for rooted tree $T$ is defined as $M[ij] = 1$ iff node $i$ is an ancestor of node $j$. Suppose we are given a matrix $X$. We can easily check that if $X$ is compatible with some rooted tree (and create the tree) or not.

The question is if $X$ is not an ancestry matrix, how hard is the problem of modifying elements of $X$ so that it becomes an ancestry matrix. The aim is to modify as few elements as possible.

Note 1: Stated problem can be seen as using Hamming distance on the matrices. A related problem would be: "For what metrics on the matrices this problem can be solved efficiently?"

Note 2: $X$ can be assumed to be a matrix containing only 0 and 1 elements. But a more general form of $X$ is more desirable!

Note 3: Any results about some characteristic matrix like adjacency matrix instead of ancestry matrix would be appreciated!

$\endgroup$
7
  • $\begingroup$ Are you aiming at a directed tree? Is the matrix $M$ symmetric? $\endgroup$ – Yuval Filmus Mar 31 at 15:50
  • 1
    $\begingroup$ If $M$ is symmetric and you're looking for an undirected tree, then the best thing to do is to remove edges so that you obtain a spanning forest, and then add edges to connect the various connected components. $\endgroup$ – Yuval Filmus Mar 31 at 15:51
  • $\begingroup$ @YuvalFilmus Thank you very much. I have rooted trees so the tree is directed and the matrix $M$ is not symmetric. $\endgroup$ – Dandelion Mar 31 at 16:43
  • $\begingroup$ Is the root fixed ahead of time? $\endgroup$ – Yuval Filmus Mar 31 at 18:48
  • 1
    $\begingroup$ I couldn't prove it, but I would expect that the problem is NP-hard. Since each path in the tree represents a clique in the transitive closure of the graph, the problem seems to be somewhat related to Cluster Edge Deletion and Correlation Clustering problems, which are NP-hard. $\endgroup$ – Dmitry Mar 31 at 20:27
1
$\begingroup$

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):

  1. 111: Preserves 0+0+0=0 edges (vs. 3 edges for the corresponding 3 from $L^*$).
  2. 21: Preserves 1+0=1 edge (vs. 3 edges for the corresponding 3 from $L^*$).
  3. 2211: Preserves 1+1+0+0=2 edges (vs. 6 edges for the corresponding 33 from $L^*$).
  4. 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.

$\endgroup$
3
  • $\begingroup$ I'm trying to follow your proof. Thanks for your complete explanations. First I do not understand this sentence: "Here we need a slightly restricted form of the problem in which every vertex is covered by some triangle". In PIT we have $3n$ vertices and want to partition them into $n$ disjoint sets so every vertex is covered by some triangle automatically. Am I missing something? $\endgroup$ – Dandelion Apr 5 at 20:02
  • $\begingroup$ My construction needs to work for every instance of the source NP-complete problem (PIT), but it doesn't work if some vertex in the PIT instance is not part of any triangle (the answer to the PIT instance is trivially NO in this case, but we should still be able to transform such an instance into an instance of RTTD). So I wanted to first show that PIT is still NP-complete when instances are constrained to have every vertex in some triangle: I can then use this restricted problem (instead of general PIT) as the source of the reduction, since my construction works for all instances of it. $\endgroup$ – j_random_hacker Apr 6 at 9:43
  • $\begingroup$ The current proof has issues, since it mistakenly assumes that a triangle "handle" that has been assigned 0 vertices constrains the number of "plain" edges -- in fact, only triangles that have been assigned 1, 2 or 3 vertices constrain them. Working on a fix. $\endgroup$ – j_random_hacker Apr 6 at 10:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.