# Ordinally Consensus Subset over Multiple Metrics

Dingkang Wang, Yusu Wang

###### Abstract

In this paper, we propose to study the following maximum ordinal consensus
problem: Suppose we are given a metric system $(\mathcal{M},X)$, which
contains $k$ metrics $\mathcal{M}=\\{\rho_{1},\ldots,\rho_{k}\\}$ defined on
the same point set $X$. We aim to find a maximum subset $X^{\prime}\subset X$
such that all metrics in $\mathcal{M}$ are “consistent” when restricted on the
subset $X^{\prime}$. In particular, our definition of consistency will rely
only on the _ordering_ between pairwise distances, and thus we call a
“consistent” subset an ordinal consensus of $X$ w.r.t. $\mathcal{M}$. We will
introduce two concepts of “consistency” in the ordinal sense: a strong one and
a weak one. Specifically, a subset $X^{\prime}$ is strongly consistent means
that the ordering of their pairwise distances is the same under each of the
input metric $\rho_{i}\in\mathcal{M}$. The weak consistency, on the other
hand, relaxes this exact ordering condition, and intuitively allows us to take
the plurality of ordering relation between two pairwise distances.

We show in this paper that the maximum consensus problems over both the strong
and the weak consistency notions are NP-complete, even when there are only 2
or 3 simple metrics, such as line metrics and ultrametrics. We also develop
constant-factor approximation algorithms for the dual version, the minimum
inconsistent subset problem of a metric system $(\mathcal{M},P)$, – note that
optimizing these two dual problems are equivalent.

##  1 Introduction

In recent years, there have been many studies on data sets with multiple
views, which can contain different sets of features from multiple sources
carrying different types of information. For example, consider neuron cells in
the field of neuroscience [15]. A single neuron cell could have both
morphology features and RNA-sequencing information available. Simply
concatenating these two types of feature sets and applying a classical single-
view method may not produce meaningful results – The types of features may be
different, and it is not clear how to properly weigh them when combined.
Instead, there have been many approaches developed to handle multi-view data.
For example, Lashkari and Golland [14], Bickel and Scheffer [4] considered
using EM algorithm and (convex) mixture model on multi-view clustering; Kumar,
Rai and Hal [13] and Cai et al. [5] extended spectral clustering algorithm for
multi-view data. See also surveys on multi-view clustering [6], and more
broadly, on multi-view learning [16].

Very often in applications, multiple views give rise to multiple metrics
$\\{{\rho}_{1},\ldots\\\ ,{\rho}_{k}\\}$ over the same data set $X$. Our goal
is to study whether these metrics are “consistent” over $X$, and identify a
largest subset $X^{\prime}$ of $X$, called _consensus_ , over which these
input metrics are “consistent”. However, when comparing these metrics, note
that the precise distance values between points in $X$ induced by different
${\rho}_{i}$s may not have the same meaning, two metrics may not have simple,
say, linear relation between them, and thus the distance values are not
readily comparable (even after normalization). For example, the distance
between two neuron cells based on their tree morphology can be very different
from that based on their gene expression profiles. Hence in this paper, we
will compute consensus under multiple metrics based on _ordinal information_ ,
namely the order of pairwise distances under each metric.

More specifically, given a _metric system_ $(\mathcal{M},X)$, consisting of a
set of $k$ input metrics $\mathcal{M}=\\{{\rho}_{1},...,{\rho}_{k}\\}$ on a
discrete data set $X$ with cardinality $n$, we propose to study the problem of
finding maximum _ordinal consensus of $X$ w.r.t. $\mathcal{M}$_. Specifically,
we aim to find a maximum subset $X^{\prime}\subset X$, such that all metrics
will have _consistent_ pairwise distances if restricted on node set
$X^{\prime}$. We also call $S=X\setminus X^{\prime}$ as _outliers_ , while
$X^{\prime}$ is our targeted ordinal consensus. The dual problem is to find
the minimum inconsistent (outlier) set $S$ such that all metrics are
consistent when restricted to the subset $X\setminus S$.

Our contributions. We propose two notions to measure the “ordinal
consistency”, which we call strong consistency and weak consistency,
respectively. Intuitively, a strong consensus $X^{\prime}\subseteq X$ means
that the order of all pairwise distances among $X^{\prime}$ must be the same
w.r.t. all input metrics. Under the weak consistency notion, roughly speaking
for each pair of pairwise distances, only a plurality of input metrics
(instead of all of them) need to agree on that. The formal definitions of
these consistency notions are in Section 2.

Note that the maximum (ordinal) consensus subset and the minimum inconsistent
subset are equivalent. In Section 3 and 4, we will show for both the strong
and weak consistency definitions, finding the subset $S$ over an input of a
constant number of (two for the strong case, and three for the weak case)
ultrametrics or Euclidean metrics on the real line are NP-hard. These special
cases imply that the problems are NP-hard if the inputs are arbitrary metrics.
We also study the approximation algorithms for both the strongly and weakly
minimum inconsistent subset problems. In particular, for the strongly
inconsistent subset, we propose a 4-approximation algorithm with time
complexity $O(kn^{2}\log n)$. For the weak case, we have a $O(n^{6})$-time
6-approximation algorithm. See Appendix A.10 for a table summarizing our
hardness results and approximation algorithms.

All missing technical details can be found in the appendix.

Some related work. We note that this maximum consensus problem has been
considered before when input metrics are tree-metrics. In particular, in the
scenario where the inputs are multiple leaf-labeled phylogenetic (rooted)
trees, one aims to find a maximum subset of labels that are “consistent” among
all inputs. In [2], Amir and Keselman proposed Maximum Agreement Subtree
problem (MAST): given a set of rooted binary trees with the same set of taxa
(leaf labels), find the maximum subset, such that all the given trees
restricted on the subset are isomorphic. This can be considered as a special
case of tree consistency [1]. The Maximum Agreement Supertree problem (SMAST)
problem is studied in [3]: Here for the given trees
$\mathcal{T}=\\{T_{1},...,T_{k}\\}$, the leaf label set $\Lambda(T_{i})$ for
input trees may not be same. The goal is to find a tree $Q$ with
$\Lambda(Q)\subset\cup_{T_{i}\in\mathcal{T}}\Lambda(T_{i})$ such that
$|\Lambda(Q)|$ is maximized and for each tree $T_{i}\in\mathcal{T}$, the
subtree $T_{i}|\Lambda(Q)$ is isomorphic to $Q|\Lambda(T_{i})$ (where $T|S$ is
the subtree of $T$ restricted on leaf set $S$).

These definitions of consistency over trees however are not identical from the
ordinal consistency we propose. These problems are related to, but still
different from, our maximum ordinal consensus problem if the input metrics are
ultrametrics. An ultrametric can be represented by a corresponding
representing tree where each tree node has a height value. Finding a strong
consensus $S$ is equivalent to finding a subset of leaf nodes such that the
restricted subtrees are not only isomorphic, _but also_ the heights of all
internal nodes must have the same order – This height condition appears to
make the problem much harder: While the MAST problem on two trees can be
solved in polynomial time via dynamic programming, the ordinal consensus
problem is NP-hard even for only two ultrametrics, as we will show in Section
3.

##  2 Preliminaries and problem setup

The input is a _metric system $(\mathcal{M};X)$_, consisting of a set of $k$
metrics $\mathcal{M}=\\{{\rho}_{1},{\rho}_{2},...,{\rho}_{k}\\}$ over the
point set $X=\\{x_{1},...,x_{n}\\}$. For any $i\in[1,k]$,
${\rho}_{i}(x,x^{\prime})$ is the distance between point $x,x^{\prime}\in X$
w.r.t. ${\rho}_{i}$. Our goal is to find a minimum subset $S\subset X$, such
that the order of all pairwise distance restricted on $X\backslash S$ are
consistent under a certain definition. Below we first introduce two notions of
consistency. The two optimization problems we will study are given in
Definition 2.6.

######  Definition 2.1 (Strong Consistency).

Given a metric system $(\mathcal{M}=\\{{\rho}_{1},{\rho}_{2},...,\\\
{\rho}_{k}\\};Y=\\{y_{1},y_{2},...,y_{m}\\})$, we say that the set of metrics
$\mathcal{M}$ is strongly consistent w.r.t. $Y$ if for any quartet
$\\{y_{p},y_{q},y_{r},y_{s}\\}\subset Y$, we have that (i)
${\rho}_{i}(y_{p},y_{q})<{\rho}_{i}(y_{r},y_{s})\Leftrightarrow{\rho}_{j}(y_{p},y_{q})<{\rho}_{j}(y_{r},y_{s})$
and (ii)
${\rho}_{i}(y_{p},y_{q})={\rho}_{i}(y_{r},y_{s})\Leftrightarrow{\rho}_{j}(y_{p},y_{q})={\rho}_{j}(y_{r},y_{s})$
for any $1\leq i,j\leq k$. In this case, we say that $Y$ is _a strongly
consistent set, or a strong consensus, over $\mathcal{M}$_.

We also say that two pairs $(y_{p},y_{q})$ and $(y_{r},y_{s})$ are _strongly
consistent w.r.t. $\mathcal{M}$_, if the order between these two pairwise
distances is the same w.r.t. any metric in $\mathcal{M}$.

Other than strong consistency, we also consider a weaker notion of
consistency: In particular, we now only require that the order constructed by
taking the _plurality voting_ 111In plurality voting, a candidate wins if it
has the most votes than the other candidates. It does not have to get a
majority (more than 50%) of the votes.  over all input metrics is valid. To
define the weak consistency formally, we will first define the so-called
relation set and the auxiliary graph.

######  Definition 2.2 (Relation Set of Pairwise Distances).

Given an input set of $k$ metrics $\mathcal{M}$ over point set $X$, the
_relation set $\mathcal{R}$ of pairwise distances_ w.r.t. $(\mathcal{M};X)$ is
the set of relations over all distinct pairs
$\\{(x_{p},x_{q})\,|\,x_{p},x_{q}\in X,p\not=q\\}$ defined as follows: For any
two pairs $(x_{p},x_{q})$ and $(x_{r},x_{s})$, among all three possible
relations between $(x_{p},x_{q})$ and $(x_{r},x_{s})$, namely, $``<"$, $``="$,
and $``>"$, the one induced by most number of metrics in $M$ will be included
in the relation set $R$. If there is any tie, we will choose the relation with
appearance in the metric of smaller index.

For example, the relation $(x_{p},x_{q})<(x_{r},x_{s})\in\mathcal{R}$ _if and
only if_ this relation appears in more (or the same number of) metrics than
the other two relations ($``="$, $``<"$).

The relation set constructed above may be not “valid” in the sense that no
single metric can generate those relations. To check the validity of this
relation set, we now define a specific auxiliary graph $\mathcal{G}$, whose
nodes correspond to pairs of points from $X$. There are three different
connections between two graph nodes, which correspond to the three possible
relations between their corresponding pairs in the relation set $\mathcal{R}$.
We will use this graph later to decide whether $\mathcal{R}$ is valid or not.

######  Definition 2.3 (Auxiliary Graph for Relation Set).

Given the relation set $\mathcal{R}$ of pairwise distances over point set $X$
and metrics $\mathcal{M}$, the auxiliary graph $\mathcal{G}=(V,E)$, where
$V=\\{(x_{i},x_{j})|x_{i},x_{j}\in X,i\not=j\\}$, is a mixed graph (meaning it
contains both directed and undirected edges): There is a _directed_ edge from
$v_{1}=(x_{p},x_{q})$ to $v_{2}=(x_{r},x_{s})$ if
$(x_{p},x_{q})>(x_{r},x_{s})\in\mathcal{R}$; there is a _undirected_ edge
between $v_{1}$ and $v_{2}$ if $(x_{p},x_{q})=(x_{r},x_{s})\in\mathcal{R}$.

We will use $v_{1},...,v_{N}$ (corresponding to all pairs in $X$) to represent
nodes in graph $\mathcal{G}$, where $N={n\choose 2}$ if $n=|X|$. The auxiliary
graph $G$ is a fully connected mixed graph (i.e., every pair of distinct
vertices is connected by a unique edge, and the edge can be directed or
undirected) with one edge between every two nodes. We say $v_{i}>v_{j}$ (or
$``="$ or $``<"$) if there is a directed edge from $v_{i}$ to $v_{j}$ (or an
undirected edge between them, or a directed edge from $v_{j}$ to $v_{i}$),
which means the pair, say $(x,y)\in X\times X$, represented by $v_{i}$ has a
larger pairwise distance compared with the pair represented by $v_{j}$. A
cycle in a mixed graph can be formed by a mixture of directed edges and
undirected edges. Intuitively, suppose we have a completely directed cycle
like the one shown in Figure 1 (a), then there is a conflict in the relations
for pairwise distances, as $v_{1}<v_{2}<v_{3}<v_{4}<v_{1}$. Hence the relation
set $\mathcal{R}$ will not be valid in this case. There are more types of
“directed” cycles and they can cause such conflict. In particular:

######  Definition 2.4 (Directed cycle of mixed graphs).

A cycle $C=\\{e_{1},\ldots,e_{r}\\}$ is a _fully-directed cycle_ if all edges
in it are directed, and the directions of all edges inside are consistent
(namely, Figure 1 (a)). A directed cycle of a mixed graph is a cycle
$C=\\{e_{1},e_{2},...,e_{n}\\}$ such that (i) it consists of at least one
directed edge, and (ii) one can assign a direction for each undirected edges
in $C$ to make it into a fully directed cycle. See Figure 1 for examples.

|  |  |
---|---|---|---
(a) A full-directed | (b) A directed cycle | (c) This is not | (d) This is not
(and directed) cycle | (of mixed graphs) with | a directed cycle since | a directed cycle since
with length 5. | an undirected edge. | none of the | conflicts between
|  | edges is directed. | directed edges.

Figure 1: Examples of fully-directed cycle, directed cycle and other cycles of
a mixed graph.

We say that a metric $\widehat{{\rho}}$ _generates_ a relation set
$\mathcal{R}$, if the order of any two pairwise distances induced by
$\widehat{{\rho}}$ are the same as in $\mathcal{R}$. In this case, we say the
relation set $\mathcal{R}$ is _valid_. The following result provides a simple
characterization for a valid relation set by using its corresponding auxiliary
graph.

######  Lemma 2.1.

There exists a metric $\widehat{{\rho}}$ generating a relation set
$\mathcal{R}$, or equivalently, $\mathcal{R}$ is valid, if and only if there
is no directed cycle in the auxiliary graph $\mathcal{G}$ for the relation set
$\mathcal{R}$.

###### Proof.

The “$\Rightarrow$” direction. This direction is relatively easier and we
prove it by contradiction. Suppose the relation set is defined over a point
set $\widehat{X}$ and there is a metric $\widehat{\rho}$ over set
$\widehat{X}$ that generates all relations in $\mathcal{R}$. Then assume there
is a directed cycle of graph nodes $C=\langle v_{1},v_{2}\cdots
v_{r},v_{1}\rangle$ in the auxiliary graph $\mathcal{G}$. Now, one can derive
that the distance between the pair of nodes in $v_{1}$ will be larger than
itself by following the edges $v_{i}\to v_{i+1}$ for $i=1,\ldots,r$, which is
a contradiction.

The “$\Leftarrow$” direction. For any two nodes $v_{a}$ and $v_{b}$ connected
by an undirected edge (i.e., $v_{a}$, $v_{b}$ represents equal distance), we
can always contract them together without causing any problems if there is no
directed cycle in graph $\mathcal{G}$. It is because that for another
arbitrary $v_{c}$, the directions of edges $(v_{a},v_{c})$ and $(v_{b},v_{c})$
are consistent. These two edges will be both going to $v_{c}$, coming out from
$v_{c}$ or undirected.

Therefore, we can iteratively contract all node pairs connected by undirected
edges until there is no such pair left. The produced graph
$\widehat{\mathcal{G}}$ will be a directed graph, and each node corresponds to
a set of nodes in the original graph $\mathcal{G}$. It is clear that
$\widehat{\mathcal{G}}$ is acyclic, because any directed cycle in
$\widehat{\mathcal{G}}$ will map back to a directed cycle (of a mixed graph)
in $\mathcal{G}$ simply by selecting an arbitrary representative for all these
supernodes in $\widehat{\mathcal{G}}$.

A linear order over those supernodes can be constructed by, e.g., topological
sort, such that the orders among pairwise distances are consistent with the
directed acyclic graph (DAG) $\widehat{\mathcal{G}}$. Nodes in $\mathcal{G}$
represented by the same supernode in $\widehat{\mathcal{G}}$ share the same
value. This provides a way to assign values over all pairwise distances such
that the ordinal relations are consistent with $\mathcal{G}$. To make it a
metric, one can force that the minimum distance is larger than one half of the
maximum distance. This way, no matter which three nodes we consider, the sum
of two pairwise distances will always be larger than the third pairwise
distance. ∎

We are now ready to define the weak consistency.

######  Definition 2.5 (Weak Consistency).

Given a set of $k$ metrics
$\mathcal{M}=\\{{\rho}_{1},{\rho}_{2},...,{\rho}_{k}\\}$ over the same point
set $Y=\\{y_{1},y_{2},...,y_{m}\\}$, we say that the set of metrics
$\mathcal{M}$ is weakly consistent with $Y$ if there is no directed cycle in
the auxiliary graph $\mathcal{G}(Y)$ for the relation set $\mathcal{R}(Y)$ as
specified in Definitions 2.2 and 2.3. In this case, we may also say that $Y$
is a weakly consistent set, or a weak consensus, over $\mathcal{M}$.

The optimization problems we aim to study in this paper are defined as
follows.

######  Definition 2.6 (Strong-MIS and Weak-MIS Problems).

Given a set of metrics $\mathcal{M}=\\{{\rho}_{1},...,{\rho}_{k}\\}$ on point
set $X$, the Strong-MIS problem (resp. Weak-MIS problem) aims to find a
minimum subset of $S^{*}\subset X$, such that all metrics restricted on
$X\backslash S^{*}$ are strongly consistent (resp. weakly consistent).

The set $S^{*}$ is called the _minimum (strong/weak) inconsistent set_ , while
$X\setminus S^{*}$ is called the _maximum (strong/weak) consensus set w.r.t.
input metrics $\mathcal{M}$_.

Note that minimizing the inconsistent set is equivalent to maximizing the
consensus (although their approximation may not be equivalent).

The decision version of Strong-MIS (and Weak-MIS) problem is as follows: Given
$\mathcal{M},X$ and also an integer $a$. Is there a subset $S\subset X$ with
$|S|=a$ such that $\mathcal{M}$ restricted on $X\backslash S$ are strongly
consistent (resp. weakly consistent)?

We will show in Section 3 and 4 that the decision versions of Strong-MIS and
Weak-MIS are in NP (see lemma 3.1 and lemma 4.1). Thus in most proofs, we will
only show NP-hardness via reductions from NP-hard problems. The NP-
completeness naturally follows by the fact that both decision problems are in
NP.

#### Some specific metrics.

Later in Sections 3 and 4, we will show that the decision version of the
minimum inconsistent set (equivalently, maximum consensus set) problem is NP-
complete even when input metrics are restricted to two common choices: the
Euclidean metric on the line (and thus in any ${\mathbb{R}}^{d}$), and the
ultrametrics.

######  Definition 2.7 (Line metric).

A line metric is a metric $({\mathbb{R}},{\rho})$, where the distance function
${\rho}(x,y)=|x-y|$, and $x,y\in{\mathbb{R}}$ (Note, this is simply the
Euclidean metric on ${\mathbb{R}}$).

######  Definition 2.8 (Ultrametric).

An ultrametric is a metric $(Z,{\rho})$ defined on a set $Z$, which satisfies
the following strong triangle inequality: for any $x,y,z\in Z$,
$d(x,z)\leq\max(d(x,y),d(y,z)).$

Any finite ultrametric $(Z,{\rho})$ has a corresponding _representing tree_
[8] $T_{Z}$ such that:

  1. 1.

$T_{Z}$ is a rooted tree with the set of leaf nodes being $Z$. $T_{Z}$ is
equipped with a height function $h:N\cup Z\rightarrow\mathbb{R}_{+}$, where
$N$ is the set of internal nodes of $T_{Z}$ such that (i) all leaves have the
same height; and (ii) $h$ is non-increasing along any root to leaf path.

  2. 2.

For any two leaf nodes $z$ and $z^{\prime}$, their distance
${\rho}(z,z^{\prime})$ equals to $h({\texttt{LCA}}(z,z^{\prime}))$, namely,
the height of their lowest common ancestor (LCA ($z,z^{\prime}$)).

An example of an ultrametric and its representing tree is given in Appendix
A.1.

##  3 Strong-MIS problem

In this section, we will study the Strong-MIS problem. Specifically, we show
in Theorem 3.1 and 3.2 that the decision version of the Strong-MIS problem is
NP-complete even when the input metric spaces are restricted to two very
simple cases: the line metrics and the ultrametrics. Corollary 3.1 gives an
inapproximability result. To complement that, in Theorem 3.4, we provide a
$4$-approximation algorithm for the general case.

Intuitively, finding the minimum strongly inconsistent set has a similar
flavor as Minimum Vertex Cover or Minimum Hitting Set [10]. Intuitively, in
Strong-MIS problem, given data points $X$, a quartet
$(x_{p},x_{q},x_{r},x_{s})$ will be a target set if they induce a conflict
between any two input metrics, and the goal is to find a Minimum Hitting Set
$\mathcal{H}$ such that for all target sets, at least one element is in
$\mathcal{H}$. However, to show that Strong-MIS remains hard even for special
simple metrics, we need to construct reductions carefully, and sometimes need
to use different NP-complete problems to reduce from. We include the list of
NP-complete problems used for reductions in Appendix B.

To study Strong-MIS, we first define the so-called Conflict Set, which will be
used frequently in NP-hardness proofs.

######  Definition 3.1 (Conflict Set).

Given $k$ metrics $\mathcal{M}=\\{{\rho}_{1},...,{\rho}_{k}\\}$ on node set
$X=\\{x_{1},...,x_{n}\\}$, the _conflict set $\mathcal{C}$_ induced by
$(\mathcal{M};X)$ is defined as
$\mathcal{C}=\\{(x_{p},x_{q},x_{r},x_{s})|(x_{p}$, $x_{q}),(x_{r},x_{s})\text{
are not strongly consistent over }\mathcal{M}\\}$. Each element in this
conflict set is called a _conflict quartet_.

It is clear that the decision version of Strong-MIS is in NP as stated in the
following lemma.

######  Lemma 3.1.

The decision version of Strong-MIS is in NP.

###### Proof.

Given a set $S$ with size $a$, one can check whether metrics in $\mathcal{M}$
are strongly consistent on $X\backslash S$ by simply iterating over all
possible quartets and comparing their pairwise distances in different metrics.
This process takes polynomial time. ∎

It turns out that the decision version of Strong-MIS is weakly NP-complete
(which allows the magnitude of data involved to be exponential) even if we
restrict the input metrics to be only two line metrics. The proof is in
Appendix A.2.

######  Theorem 3.1.

The decision version of Strong-MIS is weakly NP-complete even when one only
considers metric systems $(\mathcal{M};X)$ where
$\mathcal{M}=\\{{\rho}_{1},{\rho}_{2}\\}$ contains only two line metrics.

The following theorem shows that even with only 2 ultrametrics, finding a
Strong-MIS remains NP-hard. The proof uses a reduction from Max 2-SAT problem;
it is non-trivial and can be found in Appendix A.3.

######  Theorem 3.2.

Given a metric system $(\mathcal{M};X)$, where
$\mathcal{M}=\\{{\rho}_{1},{\rho}_{2}\\}$ contains two ultrametrics, The
decision version of Strong-MIS is NP-complete.

The hardness result on 2 ultrametrics implies that finding Strong-MIS is also
NP-hard when the input is two arbitrary metrics. The result is stated below.
This theorem can also be proven directly via a reduction from Minimum Vertex
Cover, which for completeness we include the simple details in Appendix A.4.

######  Theorem 3.3.

Given a metric system $(\mathcal{M};X)$, where
$\mathcal{M}=\\{{\rho}_{1},{\rho}_{2}\\}$ contains two arbitrary metrics, the
decision version of Strong-MIS is NP-complete.

In fact, the proof in Appendix A.4 gives a size-preserving reduction. Hence
the Corollary below follows directly from the inapproximability result [12]
for Minimum Vertex Cover.

######  Corollary 3.1.

Strong-MIS with 2 metrics is Unique Games-hard to approximate within a factor
$2-\epsilon$, where $\epsilon$ is an arbitrarily small positive number.

#### Approximation algorithm for Strong-MIS.

As we mention above, one can consider a collection $\mathcal{C}$ of all
conflict quartet $(x_{p},x_{q},x_{r},x_{s})$ as the target set. The goal is to
find a minimum set from $X$ such that it intersects (hits) every quartet in
$\mathcal{C}$. This is actually a special case of $4$-hitting set problem, and
it is easy to obtain a 4-approximation algorithm in time $O(kn^{4})$ time by
checking all quartets. However, below we show we can improve this to
$O(kn^{2}\log n)$ time complexity.

######  Theorem 3.4.

Given a metric system $(\mathcal{M};X)$ where
$\mathcal{M}=\\{{\rho}_{1},\ldots,{\rho}_{k}\\},X=\\{x_{1},\ldots,x_{n}\\}$,
there is an $O(kn^{2}\log n)$ 4-approximation algorithm for the Strong-MIS
problem.

###### Proof.

Let $S^{*}$ denote the minimum inconsistent set so that $X\setminus S^{*}$ is
the maximum consensus for metric system $(\mathcal{M};X)$. We propose
Algorithm 1, which will compute a set $S$ to be removed as inconsistent set.

Algorithm 1 $S$ = Strong-MIS ($\mathcal{M}=({\rho}_{1},\cdots,{\rho}_{k}),X$)

1:for each metric ${\rho}_{i}\in\mathcal{M}$ do

2: Sort all pairwise distances based on the distances in ascending order. Let
$L_{1},\cdots,L_{k}$ denote those $k$ sorted lists.

3:end for

4:Initialize $S=\emptyset.$ $k$ pointers
${\mathsf{p}}_{1},\cdots,{\mathsf{p}}_{k}$ pointing to the head of
$L_{1},\cdots,L_{k}$.

5:while None of ${\mathsf{p}}_{i}$s points out of bound. do

6: while $E({\mathsf{p}}_{1})\cap S\not=\emptyset$ do

7: ${\mathsf{p}}_{1}={\mathsf{p}}_{1}+1$

8: end while$\triangleright$ Move the pointer of the first list.

9: flag = False

10: for $i\in[2\cdots k]$ do

11: while $E({\mathsf{p}}_{i})\cap S\not=\emptyset$ do

12: ${\mathsf{p}}_{i}={\mathsf{p}}_{i}+1$

13: end while

14: if ${\mathsf{p}}_{1},{\mathsf{p}}_{i}$ in bound $\textbf{ and
}E({\mathsf{p}}_{i})\not=E({\mathsf{p}}_{1})$ then

15: $S=S\cup\\{E({\mathsf{p}}_{i}),E({\mathsf{p}}_{1})\\}$

16: flag = True $\triangleright$ Found a conflict

17: end if

18: ${\mathsf{p}}_{i}={\mathsf{p}}_{i}+1$ $\triangleright$ Move the pointer to
the next since it is already considered.

19: if flag = True then $\triangleright$ If there is a conflict, move on to
the next iteration.

20: break

21: end if

22: end for

23:end while

24:return $S$

On the high level, Algorithm 1 starts with sorting all pairs of points based
on their distances (If two pairs have the same distance, then they are sorted
in lexicographical order). With $k$ sorted lists of pairs
$L_{1},\ldots,L_{k}$, we set $k$ pointers to the heads of these lists: Let
${\mathsf{p}}_{i}$ be the pointer to the list of pairwise distances of metric
$\rho_{i}$, and $E({\mathsf{p}}_{i})$ denote the pair of data points in $X$
that ${\mathsf{p}}_{i}$ is pointing to. As pointers move down these lists, it
checks whether all pointers are pointing to the same pair of points from $X$.
If that is the case, it moves on. Otherwise, if $E({\mathsf{p}}_{i})\neq
E({\mathsf{p}}_{1})$ (line-14), it means a conflict quartet is discovered,
formed by the two pairs $E({\mathsf{p}}_{i})$ and $E({\mathsf{p}}_{1})$. In
this case, we will remove all these points (by adding them to $S$), and move
on. The code from lines 6-8 and 11-13 is to skip all pairs which contain at
least one point from the outlier set $S$. The procedure ends when any pointer
moves out of bound (i.e., beyond the last element of the list). An
illustration of how the algorithm works is given in Figure 9 in Appendix A.5.

Time complexity. There are $k$ metrics and $n\choose 2$ pairs. The sorting
process takes $O(kn^{2}\log n)$ time. Since the procedure ends when each
pointer reaches the tail, the pointers will be moved for at most $kn^{2}$
total times. During each pointer move, the most expensive step is line-11,
which can be done in $O(1)$ with an array of length $n$ indicating if a node
is in $S$ or not.

Putting everything together, the total time complexity for our algorithm is
$O(kn^{2}\log n)$.

Correctness of algorithm. We consider the points ever added to set $S$. Note
that $S$ is only updated in line-12, where there is a conflict (i.e, the pair
$E({\mathsf{p}}_{i})=(a,b)$ pointed by $p_{i}$ in list $L_{i}$ is different
from the pair $E({\mathsf{p}}_{1})=(c,d)$ by the pointer for list $L_{1}$).
Assume that $(a,b)$ is smaller than $(c,d)$ for lexicographical order. We
claim that $\\{(a,b),(c,d)\\}$ form a conflict quartet. To prove this, first,
note that as we skip all pairs that contain any element from $S$ (lines 6-8,
11-13), this means that $S\cap\\{a,b,c,d\\}=\emptyset$. Hence in list $L_{1}$,
we have not yet seen (scanned) the pair $(a,b)$ – as otherwise, at the time
when the pointer in $L_{1}$ reaches $(a,b)$, if at that moment the pointer in
$L_{i}$ is not pointing to $(a,b)$, we would have already seen a conflict and
added $a,b$ to $S$. It then follows that w.r.t. metric ${\rho}_{1}$, we have
that ${\rho}_{1}(a,b)>{\rho}_{1}(c,d)$. On the other hand, in list $L_{i}$, it
must be that we have not yet seen $(c,d)$ by the same reasoning, meaning that
${\rho}_{i}(a,b)\leq{\rho}_{i}(c,d)$ w.r.t. metric ${\rho}_{i}$. Hence these
two pairs form a conflict quartet. Obviously, for any conflict quartet, the
minimum inconsistent set $S^{*}$ has to contain at least one element from it.
Furthermore, since all the conflict quartet the algorithm ever identifies are
disjoint. This means that the $|S^{*}|\geq|S|/4$, that is, $|S|\leq 4|S^{*}|$.

Finally, consider the ordered sublist $\widehat{L}_{i}$ of $L_{i}$, obtained
by removing from $L_{i}$ all pairs that intersect $S$. Then it is easy to see
that by construction of the algorithm, all $\widehat{L}_{i}$s are the same. In
other words, after removing all elements in $S$, the remaining points
$X\setminus S$ form a consensus subset for the $k$ metrics
$\mathcal{M}=\\{{\rho}_{1},\ldots,{\rho}_{k}\\}$. Hence $S$ is a valid
inconsistent set and $|S|\geq|S^{*}|$. It follows that $S$ is a
4-approximation of the minimum inconsistent subset for the metric system
$(\mathcal{M};X)$.

∎

##  4 Weak-MIS problem

We now focus on the Weak-MIS problem of finding a minimum weakly inconsistent
subset. In Theorems 4.1 and 4.2, we show that it is NP-complete for the
special case of only three input line metrics or ultrametrics. We provide a
straightforward 6-approximation algorithm at the end.

Figure 2: Three possible directed triangles.

By definition 2.5 and 2.6, if $X\backslash S$ is a consensus set, then the
auxiliary graph $\mathcal{G}$ restricted on $X\backslash S$ must contain no
directed cycle. It is well known that a tournament (fully connected directed
graph) has a directed cycle if and only if it has a directed triangle [7]. It
turns out that a similar result holds for auxiliary graphs, which are mixed
graphs: see the claim below. See Figure 2 for the 3 possible cases of directed
triangles. The simple proof of this claim can be found in Appendix A.6.

######  Claim 4.1.

An auxiliary graph $\mathcal{G}$ has no directed cycle if and only if it has
no directed triangle.

Hence to see whether there is any directed cycle in the auxiliary graph, one
only needs to check if there is any directed triangle.

Followed by claim 4.1, the decision version of Weak-MIS is in NP.

######  Lemma 4.1.

The decision version of Weak-MIS is in NP.

###### Proof.

By definition 2.5 and claim 4.1, one can check whether metrics from
$\mathcal{M}$ are weakly consistent on a set $S$ by iterating over all
triangles in the auxiliary graph. It is clearly polynomial. ∎

When there are two metrics, with the tie-breaking rule defined in Definition
2.2, it is clear that we would always prefer the first metric (once the order
of input metrics is fixed). Thus in this case, the minimum inconsistent set is
simply $\emptyset$. The problem of Weak-MIS becomes non-trivial when there are
three metrics.

Our first main result is as follows, with proof in Appendix A.7.

######  Theorem 4.1.

Given a metric system $(\mathcal{M};X)$, where
$\mathcal{M}=\\{{\rho}_{1},{\rho}_{2},{\rho}_{3}\\}$ contains three line
metrics. The decision version of Weak-MIS is weakly NP-complete.

Our second main result is the hardness for ultrametrics.

######  Theorem 4.2.

Given a metric system $(\mathcal{M};X)$, where
$\mathcal{M}=\\{{\rho}_{1},{\rho}_{2},{\rho}_{3}\\}$ contains three
ultrametrics. The decision version of Weak-MIS is NP-complete.

###### Proof of Theorem 4.2.

We prove this theorem via a reduction from the so-called 3-dimensional
Matching problem. In particular, instead of the problem of finding the minimum
inconsistent set, we will consider the equivalent dual version of finding a
maximum consensus for a set of 3 ultrametrics.

Description of the reduction. Suppose we are given an instance of
3-dimensional Matching problem ($X,Y,Z;{\mathcal{S}}\subseteq X\times Y\times
Z$), where $|X|=|Y|=|Z|$. Assume that
$X=\\{x_{1},...,x_{n}\\},Y=\\{y_{1},...,y_{n}\\},Z=\\{z_{1},...,z_{n}\\}$,
while ${\mathcal{S}}=\\{{\mathsf{s}}_{1},...,{\mathsf{s}}_{m}\\}$ where each
relation ${\mathsf{s}}_{i}$ is of the form
${\mathsf{s}}_{i}=(x_{a},y_{b},z_{c})$ with $x_{a}\in X,y_{b}\in Y$ and
$z_{c}\in Z$. A matching $\Pi\subset{\mathcal{S}}$ is such that each element
in $X\cup Y\cup Z$ can appear at most once in all relations in $\Pi$. The
decision version of the 3-dimensional Matching problem is that, given
$(X,Y,Z,{\mathcal{S}})$ and an integer $K$, does there exist a matching
$\Pi\subset{\mathcal{S}}$ such that $|\Pi|=K$?

From this instance $(X,Y,Z;{\mathcal{S}})$ of the 3-dimensional Matching
problem, we will now construct an instance of the Weak-MIS problem
$(\mathcal{M}=\\{U_{X},U_{Y},U_{Z}\\},P)$, where the node set is
$P=\\{a_{1},\ldots,a_{m},b_{1},\ldots,b_{m},c_{1},\ldots,c_{m},\\\
d_{1},\ldots,d_{m},{\widehat{{\mathsf{s}}}}_{1},\ldots,{\widehat{{\mathsf{s}}}}_{m}\\}$,
and $\mathcal{M}$ consists of 3 ultrametrics, $U_{X},U_{Y}$, and $U_{Z}$ over
node set $P$. (Note that we do not use $X$ as the node set as $X$ is already
used in the instance of 3-dimensional Matching problem.) Recall that any
ultrametric over node set $P$ corresponds to a representing tree, which is a
rooted tree where all nodes have a height value, and all leaves (corresponding
to node set $P$) have the same height. In what follows, we will describe the
three representing trees $T_{X},T_{Y}$ and $T_{Z}$, generating $U_{X},U_{Y}$
and $U_{Z}$, respectively. In particular, these three representing trees
$T_{X},T_{Y}$ and $T_{Z}$ all have the same tree shape. However, the height of
those internal nodes will be different.

We will first describe the representing tree for $T_{X}$. The root $root$ has
5 children, represented by $A,B,C,D$ and $\widehat{X}$. Each of $A,B,C,D$ has
exactly $m$ children, which are ${\texttt{Ch}}(A)=\\{a_{1},\ldots,a_{m}\\}$,
${\texttt{Ch}}(B)=\\{b_{1},\ldots,b_{m}\\}$,
${\texttt{Ch}}(C)=\\{c_{1},\ldots,c_{m}\\}$ and
${\texttt{Ch}}(D)=\\{d_{1},\ldots,d_{m}\\}$, respectively. Note that these
children are leaves, corresponding to the first $4m$ nodes in the node set $P$
(See Figure 3). The node $\widehat{X}$ has $n$ children,
${\widehat{x}}_{1},\ldots,{\widehat{x}}_{n}$, corresponding to the $n$ points
in input set $X$ of the 3-dimensional Matching instance
$(X,Y,Z;{\mathcal{S}})$. The child(ren) of each ${\widehat{x}}_{i}$ is defined
as: ${\texttt{Ch}}({\widehat{x}}_{i})=\\{{\widehat{{\mathsf{s}}}}_{j}\mid
x_{i}\in{\mathsf{s}}_{j}\\}$; all children of ${\widehat{x}}_{i}$s are all
leaves. See Figure 3.

Next, we assign height values for nodes in $T_{X}$. All leaves (corresponding
to elements in the node set $P$ where ultrametrics are defined on) have height
$0$. The height values for the internal nodes are listed in the row
corresponding to $T_{X}$ in Table 1.

The representing tree $T_{Y}$ (resp. $T_{Z}$) has the same tree shape as
$T_{X}$, and the only difference is that the node $\widehat{X}$ and
${\widehat{x}}_{i}$s are replaced by $\widehat{Y}$ and ${\widehat{y}}_{i}$s
(resp. by $\widehat{Z}$ and ${\widehat{z}}_{i}$s). See Figure 3. The height
values of all leaves nodes are still $0$, and the height values of internal
nodes are listed in the last two rows of Table 1. Also see Figure 3 where the
height of each node is listed in the parenthesis next to each node.

| $root$ | $A$ | $B$ | $C$ | $D$ | $\widehat{X}(\widehat{Y},\widehat{Z})$ | $\widehat{x}_{i}(\widehat{y}_{i},\widehat{z}_{i})$
---|---|---|---|---|---|---|---
$T_{X}$ | 10 | 5 | 4 | 3 | 1 | 2 | 0
$T_{Y}$ | 10 | 3 | 0 | 2 | 5 | 4 | 1
$T_{Z}$ | 10 | 2 | 4 | 0 | 1 | 5 | 3
Table 1: Height function values assigned to internal nodes. Figure 3: An
instance of 3D Matching problem, and the corresponding instance of Weak-MIS.
The values in parentheses are the height values of tree nodes.

This finishes setting up all three representing trees (thus also the
ultrametrics $U_{X},U_{Y}$ and $U_{Z}$). Recall that for each ultrametric say
$U_{X}$, the distance $U_{X}(p,q)$, with $p,q\in P$, corresponds to the height
value of the lowest common ancestor (LCA) of leaves $p$ and $q$.

In what follows, we will first prove some properties of the constructed
ultrametrics. Specifically, consider the auxiliary graph $\mathcal{G}$
constructed for the metric system $(\mathcal{M}=\\{U_{X},U_{Y},U_{Z}\\};P)$.
Recall that each graph node in $\mathcal{G}$ corresponds to a pair of points
from $P$, $(p,q)\in P\times P$. For simplicity, we use ${\mathsf{A}}$ to
represent the set $\\{a_{1},\ldots,a_{m}\\}$, and similarly for
${\mathsf{B}},{\mathsf{C}}$, ${\mathsf{D}}$, and ${\mathsf{S}}$. Given a graph
node $(p,q)$ of $\mathcal{G}$, we say that this pair _splits_ if $p$ and $q$
are from two different sets in
$\\{{\mathsf{A}},{\mathsf{B}},{\mathsf{C}},{\mathsf{D}},{\mathsf{S}}\\}$ (e.g,
$p\in{\mathsf{A}}$ and $q\in{\mathsf{D}}$). Now consider a triple
${\widehat{{\mathsf{s}}}}_{i}=(x^{\prime},y^{\prime},z^{\prime})\in X\times
Y\times Z$; we refer to $x^{\prime}$ (resp, $y^{\prime}$, $z^{\prime}$) as the
$x$-coordinate (resp. $y$\- or $z$-coordinate) of
${\widehat{{\mathsf{s}}}}_{i}$. Given a graph node of the auxiliary graph
$\mathcal{G}$ of the form
$({\widehat{{\mathsf{s}}}}_{i},{\widehat{{\mathsf{s}}}}_{j})$, we say that
this pair _has shared coordinate_ , if
${\widehat{{\mathsf{s}}}}_{i}\cap{\widehat{{\mathsf{s}}}}_{j}\neq\emptyset$.
This means that ${\widehat{{\mathsf{s}}}}_{i}$ shares either $x$-, $y$\- or
$z$-coordinate. This is the key lemma to guarantee the correctness of our
reduction. The proof of this lemma can be found in Appendix A.8. We remark
that the height values of all nodes in the three representing trees are chosen
carefully so that the lemma below holds. To compute these height values, we in
fact write a computer program testing all possible permutations of heights
over internal nodes to make sure all conditions in Lemma 4.2 are satisfied.

######  Lemma 4.2.

Consider a graph node $(p,q)\in P\times P$ of the auxiliary graph
$\mathcal{G}$.

  * (i)

If $(p,q)$ splits, then this graph node cannot appear in any directed triangle
in the auxiliary graph $\mathcal{G}$.

  * (ii)

Any directed triangle in $\mathcal{G}$ must contain at least one graph node of
the form $({\widehat{{\mathsf{s}}}}_{i},{\widehat{{\mathsf{s}}}}_{j})$ where
this pair have shared coordinate.

  * (iii)

If $(p,q)$ is of the form
$({\widehat{{\mathsf{s}}}}_{i},{\widehat{{\mathsf{s}}}}_{j})$ and this pair
has shared coordinate, then this graph node
$({\widehat{{\mathsf{s}}}}_{i},{\widehat{{\mathsf{s}}}}_{j})$ must participate
in at least one directed triangle.

Note that the correctness of the reduction then follows easily from the above
key lemma. In particular, we now show that $(X,Y,Z;{\mathcal{S}})$ has a
matching $\Pi\subseteq{\mathcal{S}}$ of size $K$ if and only if the metric
system $(\\{U_{X},U_{Y},U_{Z}\\},P)$ has a consensus subset of size $4m+K$.

“$\Rightarrow$” direction: Suppose $(X,Y,Z;{\mathcal{S}})$ has a matching
$\Pi=\\{{\mathsf{s}}_{I_{1}},\ldots,{\mathsf{s}}_{I_{K}}\\}$ of size $K$. Then
we claim that the set

$\begin{split}P^{\prime}=&\\{a_{1},\cdots,a_{m},b_{1},\cdots,b_{m},c_{1},\cdots,c_{m},d_{1},\cdots,d_{m},{\widehat{{\mathsf{s}}}}_{I_{1}},\cdots,{\widehat{{\mathsf{s}}}}_{I_{K}}\\}\\\
=&{\mathsf{A}}\cup{\mathsf{B}}\cup{\mathsf{C}}\cup{\mathsf{D}}\cup\\{{\widehat{{\mathsf{s}}}}_{I_{1}},\cdots,{\widehat{{\mathsf{s}}}}_{I_{K}}\\}\end{split}$

forms a consensus subset of $P$ w.r.t. the metric system
$(\\{U_{X},U_{Y},U_{Z}\\};P)$. Specifically, by Claim 4.1, we just need to
show that the subgraph $\mathcal{G}^{\prime}$ of the auxiliary graph
$\mathcal{G}$ spanned by nodes coming from $P^{\prime}\times P^{\prime}$
contains no directed triangle. As $\Pi$ is a valid matching, no two
${\widehat{{\mathsf{s}}}}_{I_{i}}$ and ${\widehat{{\mathsf{s}}}}_{I_{j}}$ can
have shared coordinates. It then follows from Lemma 4.2 (ii) that there cannot
be any directed triangle in the subgraph $\mathcal{G}^{\prime}$.

“$\Leftarrow$” direction: Suppose we have a consensus subset
$P^{\prime}\subset P$ for the metric system $(\\{U_{X},U_{Y},U_{Z}\\};P)$ such
that $|P^{\prime}|=4m+K$. First, consider
$P^{\prime}\cap{\mathsf{S}}=\\{{\widehat{{\mathsf{s}}}}_{J_{1}},\ldots,{\widehat{{\mathsf{s}}}}_{J_{s}}\\}$.
We know that the subgraph $\mathcal{G}^{\prime}$ spanned by nodes from
$P^{\prime}\times P^{\prime}$ contains no directed triangle. By Lemma 4.2
(iii), it then follows that no two
${\widehat{{\mathsf{s}}}}_{J_{i}},{\widehat{{\mathsf{s}}}}_{J_{j}}$,
$i,j\in[1,s]$, could have shared coordinate. In other words, the set
$\\{{\widehat{{\mathsf{s}}}}_{J_{1}},\ldots,{\widehat{{\mathsf{s}}}}_{J_{s}}\\}$
forms a valid 3D matching for $(X,Y,Z;{\mathcal{S}})$ of size $s$. On the
other hand, we know that $|P^{\prime}\setminus{\mathsf{S}}|\leq 4m$ (as the
largest possible choise for $P^{\prime}\setminus{\mathsf{S}}$ is
${\mathsf{A}}\cup{\mathsf{B}}\cup{\mathsf{C}}\cup{\mathsf{D}}$). Since
$|P^{\prime}|=4m+K$, it then follows that $s\geq|K|$, and thus there exists a
3D matching of $(X,Y,Z;{\mathcal{S}})$ of size at least $|K|$.

As 3-dimensional Matching is NP-complete, it then follows that the decision
problem of Weak-MIS is NP-complete. This finishes the proof of Theorem 4.2. ∎

The following theorem is an implication from the previous proof. Similarly as
Strong-MIS, we also provide a direct proof for arbitrary metrics in Appendix
A.9. In the proof, we construct a size-preserving reduction from Minimum
Vertex Cover which again leads to an $(2-\epsilon)$-inapproximability result.

######  Theorem 4.3.

Given a metric system $(\mathcal{M};X)$, where
$\mathcal{M}=\\{{\rho}_{1},{\rho}_{2},{\rho}_{3}\\}$ contains three arbitrary
metrics, the decision version of Weak-MIS is NP-complete.

Furthermore, Weak-MIS with 3 metrics is Unique Games-hard to approximate
within a factor $2-\epsilon$ for an arbitrarily small positive constant
$\epsilon>0$.

Finally, there is a simple 6-approximation algorithm with running time
$O(n^{6})$: Specifically, given a metric system $(\mathcal{M};X)$ with
$n=|X|$, we first build auxiliary graph $\mathcal{G}$ as described earlier in
$O(kn^{4})$ time. We want to construct an outlier set $S\subset X$ so that it
“hits” all directed triangles in $\mathcal{G}$: note that this will then
guarantee that $X\setminus S$ is a consensus set w.r.t. $\mathcal{M}$. To this
end, we simply enumerate all directed triangles in $\mathcal{G}$ in $O(n^{6})$
time. We then initialize $S=\emptyset$ and go through the list of directed
triangles one by one. For each directed triangle $\Delta w_{1}w_{2}w_{3}$
(where each $w_{i}$ is a pair of points in $X$), if $S$ does not intersect
with any of the points included in $w_{1}\cup w_{2}\cup w_{3}\subset X$, then
we simply add all these points (at most 6 distinct points) to $S$. Otherwise,
this triangle is already “hit” by $S$ and we do nothing. Let $S^{*}$ be the
minimum weakly inconsistent set (i,e, the optimal solution for Weak-MIS). It
is easy to see that $|S^{*}|\geq|S|/6$, as all the 6-tuples (at most 6) we
ever added to $S$ are all disjoint, and for each such 6-tuple, $S^{*}$ must
contain at least one point from it. Furthermore, it is also easy to see that
after removing all points $S$, the resulting auxiliary graph restricted to
only pairs not containing points in $S$ is free of directed triangles, and
thus free of directed cycles by Lemma 2.1 and Claim 4.1. Hence $X\setminus S$
is a consensus set w.r.t. $\mathcal{M}$, and $|S|\leq 6|S^{*}|$. Hence:

######  Theorem 4.4.

There is a 6-approximation algorithm for the Weak-MIS problem that runs in
$O(kn^{4}+n^{6})$ time for $k$ metrics defined on a point set of size $n$.

##  5 Conclusion

In this paper, we proposed to study the maximum ordinal consensus problem over
a set of input metrics. We developed two concepts of “consistency” that only
rely on ordinal information of pairwise distances. We proved several hardness
results for both definitions with different input metrics. We also developed
constant-factor approximation algorithms for the minimum inconsistent set
problem under both definitions.

There are still some open directions for future work. For example, can we
close the gap between the inapproximability and the approximation algorithm we
developed? Can we improve the time complexity, especially for the Weak-MIS
problem? Can we find better approximation algorithms for special cases such as
Euclidean metrics or ultrametrics? We also note that the current approximation
algorithms target the minimum (ordinally) inconsistent subset problems – how
about the dual maximum ordinal consensus problem?

##  6 Acknowledgment

This work is partially supported by National Science Foundation (NSF) under
grant IIS-1815697, as well as National Institute of Health (NIH) under grant
R01EB022899.

## References

  * [1] A. V. Aho, Y. Sagiv, T. G. Szymanski, and J. D. Ullman.  Inferring a tree from lowest common ancestors with an application to the optimization of relational expressions.  SIAM Journal on Computing, 10(3):405–421, 1981.  URL: https://doi.org/10.1137/0210030, arXiv:https://doi.org/10.1137/0210030, doi:10.1137/0210030.
  * [2] A. Amir and D. Keselman.  Maximum agreement subtree in a set of evolutionary trees: Metrics and efficient algorithms.  SIAM Journal on Computing, 26(6):1656–1669, 1997.  URL: https://doi.org/10.1137/S0097539794269461, arXiv:https://doi.org/10.1137/S0097539794269461, doi:10.1137/S0097539794269461.
  * [3] Vincent Berry and François Nicolas.  Maximum agreement and compatible supertrees.  Journal of Discrete Algorithms, 5(3):564 – 591, 2007.  Selected papers from Ad Hoc Now 2005.  URL: http://www.sciencedirect.com/science/article/pii/S1570866706000785, doi:https://doi.org/10.1016/j.jda.2006.08.005.
  * [4] Steffen Bickel and Tobias Scheffer.  Multi-view clustering.  In Proceedings of the Fourth IEEE International Conference on Data Mining, ICDM ’04, pages 19–26, Washington, DC, USA, 2004. IEEE Computer Society.  URL: http://dl.acm.org/citation.cfm?id=1032649.1033432.
  * [5] X. Cai, F. Nie, H. Huang, and F. Kamangar.  Heterogeneous image feature integration via multi-modal spectral clustering.  In CVPR 2011, pages 1977–1984, June 2011.  doi:10.1109/CVPR.2011.5995740.
  * [6] Guoqing Chao, Shiliang Sun, and Jinbo Bi.  A survey on multi-view clustering.  CoRR, abs/1712.06246, 2017.  URL: http://arxiv.org/abs/1712.06246, arXiv:1712.06246.
  * [7] Michael Dom, Jiong Guo, Falk Hüffner, Rolf Niedermeier, and Anke Truss.  Fixed-parameter tractability results for feedback set problems in tournaments.  J. of Discrete Algorithms, 8(1):76–86, March 2010.  URL: http://dx.doi.org/10.1016/j.jda.2009.08.001, doi:10.1016/j.jda.2009.08.001.
  * [8] Oleksiy Dovgoshey and Evgeniy Petrov.  Properties and morphisms of finite ultrametric spaces and their representing trees.  p-Adic Numbers, Ultrametric Analysis and Applications, 11(1):1–20, Jan 2019.  URL: https://doi.org/10.1134/S2070046619010011, doi:10.1134/S2070046619010011.
  * [9] M. R. Garey, D. S. Johnson, and L. Stockmeyer.  Some simplified np-complete problems.  In Proceedings of the Sixth Annual ACM Symposium on Theory of Computing, STOC ’74, page 47–63, New York, NY, USA, 1974. Association for Computing Machinery.  URL: https://doi.org/10.1145/800119.803884, doi:10.1145/800119.803884.
  * [10] Michael R. Garey and David S. Johnson.  Computers and Intractability; A Guide to the Theory of NP-Completeness.  W. H. Freeman & Co., New York, NY, USA, 1990.
  * [11] Richard M. Karp.  Reducibility among Combinatorial Problems, pages 85–103.  Springer US, Boston, MA, 1972.  URL: https://doi.org/10.1007/978-1-4684-2001-2_9, doi:10.1007/978-1-4684-2001-2_9.
  * [12] Subhash Khot and Oded Regev.  Vertex cover might be hard to approximate to within 2-$\epsilon$.  Journal of Computer and System Sciences, 74(3):335 – 349, 2008\.  Computational Complexity 2003.  URL: http://www.sciencedirect.com/science/article/pii/S0022000007000864, doi:https://doi.org/10.1016/j.jcss.2007.06.019.
  * [13] Abhishek Kumar, Piyush Rai, and Hal Daume.  Co-regularized multi-view spectral clustering.  In J. Shawe-Taylor, R. S. Zemel, P. L. Bartlett, F. Pereira, and K. Q. Weinberger, editors, Advances in Neural Information Processing Systems 24, pages 1413–1421. Curran Associates, Inc., 2011.  URL: http://papers.nips.cc/paper/4360-co-regularized-multi-view-spectral-clustering.pdf.
  * [14] Danial Lashkari and Polina Golland.  Convex clustering with exemplar-based models.  In J. C. Platt, D. Koller, Y. Singer, and S. T. Roweis, editors, Advances in Neural Information Processing Systems 20, pages 825–832. Curran Associates, Inc., 2008.  URL: http://papers.nips.cc/paper/3181-convex-clustering-with-exemplar-based-models.pdf.
  * [15] Arpiar Saunders, Evan Z. Macosko, Alec Wysoker, Melissa Goldman, Fenna M. Krienen, Heather de Rivera, Elizabeth Bien, Matthew Baum, Laura Bortolin, Shuyu Wang, Aleksandrina Goeva, James Nemesh, Nolan Kamitaki, Sara Brumbaugh, David Kulp, and Steven A. McCarroll.  Molecular diversity and specializations among the cells of the adult mouse brain.  Cell, 174(4):1015 – 1030.e16, 2018.  URL: http://www.sciencedirect.com/science/article/pii/S0092867418309553, doi:https://doi.org/10.1016/j.cell.2018.07.028.
  * [16] Chang Xu, Dacheng Tao, and Chao Xu.  A survey on multi-view learning.  CoRR, abs/1304.5634, 2013.  URL: http://arxiv.org/abs/1304.5634, arXiv:1304.5634.

##  Appendix A Missing Details

###  A.1 An Ultrametric and its Representing Tree

Figure 4 shows an example of an ultrametric and its representing tree. Values
on internal nodes are their heights, and all leaf nodes are with height 0. The
distance between any two leaf nodes is the height function value of their LCA.
For example, the distance from $A$ to $E$ is 3.

Figure 4: An ultrametric and its corresponding representing tree.

###  A.2 Proof of Theorem 3.1

###### Proof.

We prove this theorem via a reduction from the Minimum Vertex Cover problem.

Description of the reduction. Suppose we are given an instance $G=(V,E)$ of
Minimum Vertex Cover, where $V=\\{v_{1},...,v_{n}\\}$ and
$E=\\{e_{1},...,e_{m}\\}$. A vertex cover $V^{\prime}\subset V$ is such that
every edge in $E$ has at least one endpoint in $V^{\prime}$. The decision
version of the Minimum Vertex Cover problem is that, given $G=(V,E)$ and an
integer $K$, is there a vertex cover $V^{\prime}\subset V$ such that
$|V^{\prime}|=K$? From the instance of Minimum Vertex Cover, we construct an
instance of the Strong-MIS problem
$(\mathcal{M}=\\{{\rho}_{1},{\rho}_{2}\\};X)$, where ${\rho}_{1},{\rho}_{2}$
are two line metrics. Here
$X=\\{{\widehat{v}}_{1},...,{\widehat{v}}_{n},r_{e_{1},l},r_{e_{1},r},...,r_{e_{m},l},r_{e_{m},r}\\}$,
and $|X|=n+2m$. The $r_{e_{i},l}$ and $r_{e_{i},r}$ are two “pivots” for $i$th
edge $e_{i}$.

Since all these points are on real line ${\mathbb{R}}$, we will use
$``[\cdot]_{1}"$ and $``[\cdot]_{2}"$ to represent coordinates. When the
coordinate is the same for both metrics or there is no ambiguity, we will omit
the subscript and use $``[\cdot]"$ for the coordinate. For example,
$[{\widehat{v}}_{1}]_{1}$ is the coordinate of point ${\widehat{v}}_{1}$ in
${\rho}_{1}$. Instead of constructing ${\rho}_{1},{\rho}_{2}$ directly, we
construct the coordinates of each point as follows (see Figure 5 for an
example):

  1. 1.

For both ${\rho}_{1},{\rho}_{2}$, $[{\widehat{v}}_{i}]=2^{i-1}$.

  2. 2.

For both ${\rho}_{1},{\rho}_{2}$, the coordinate of
$[r_{e_{j},l}]=2^{n+2(j-1)}$.

  3. 3.

For $r_{e_{j},r},1\leq j\leq m$, and $e_{j}=(v_{a},v_{b}),b>a$, its coordinate
$[r_{e_{j},r}]_{1}$ in ${\rho}_{1}$ is:
$[r_{e_{j},r}]_{1}=[r_{e_{j},l}]_{1}+([{\widehat{v}}_{b}]_{1}-[{\widehat{v}}_{a}]_{1})+\epsilon=2^{n+2(j-1)}+(2^{b-1}-2^{a-1})+\epsilon$.
Similarly, its coordinate $[r_{e_{j},r}]_{2}$ in ${\rho}_{2}$ is:
$[r_{e_{j},r}]_{2}=[r_{e_{j},l}]_{2}+([{\widehat{v}}_{b}]_{2}-[{\widehat{v}}_{a}]_{2})-\epsilon=2^{n+2(j-1)}+(2^{b-1}-2^{a-1})-\epsilon$.
The intuition is the distance from $r_{e_{j},l}$ to $r_{e_{j},r}$ is close to
the distance from $v_{a}$ to $v_{b}$, but orders are different in two metrics.

Figure 5: Constructed line metrics given an simple $G$.

Check comparable pairwise distances. The distance between any pair of nodes
under metrics ${\rho}_{1}$ and ${\rho}_{2}$ can be easily calculated based on
coordinates $[\cdot]_{1}$ and $[\cdot]_{2}$. We now show that any conflict
quartet of the above constructed instance must have the form of
$\\{{\widehat{v}}_{i},{\widehat{v}}_{j},r_{e,l},r_{e,r}\\}$, where
$e=(v_{i},v_{j})\in E$. We first consider the necessary conditions for two
pairs $(a,b)$ and $(c,d)$ to cause a conflict. W.l.o.g., we can assume that
$[b]>[a]$ and $[d]>[c]$ in both metrics.

  * (1)

To cause a conflict, the distances $[b]-[a]$ and $[d]-[c]$ should be _close_
so that the relation between $\\{[b]_{1}-[a]_{1},[d]_{1}-[c]_{1}\\}$ and
$\\{[b]_{2}-[a]_{2},[d]_{2}-[c]_{2}\\}$ can be different. One can notice that
the distance can be distorted by at most $2\cdot\epsilon$ from one metric to
the other, thus in a more formal way, _close_ means “differ by at most
$4\cdot\epsilon"$.

  * (2)

Another necessary condition for $(a,b)$ and $(c,d)$ to cause a conflict is
that $[b]-[a]$ is not identical to $[d]-[c]$ in any one of the two metrics.
For example, assume that $[b]_{1}-[a]_{1}=[d]_{1}-[c]_{1}$ (equivalently
$[b]_{1}+[c]_{1}=[a]_{1}+[d]_{1})$ and
$[b]_{1}+[c]_{1}=I+t\cdot\epsilon=[a]_{1}+[d]_{1}$. Here $I$ and $t$ are some
integers. When comes to coordinates in the second metric, one can show that
$[b]_{2}+[c]_{2}=I-t\cdot\epsilon=[a]_{2}+[d]_{2}$ as only the polarity of
$\epsilon$ term is changed across two metrics.

Combining those two conditions, we define two pairs are _comparable_ if they
are _different_ and _differ by at most $4\cdot\epsilon$_. A conflict is
possible only when two pairs in the quartet are comparable. We then iterate
over all pairs and check whether there is any other pair with a comparable
pairwise distance. We will also use the _leading term_ (the largest power of
two) of coordinates to find comparable pairs. The leading term of
$[{\widehat{v}}_{i}]s$ and $[r_{e,l}]$s are of different scales, and
$[r_{e,r}]$ has the same leading term of $[r_{e,l}]$. Moreover, if $[b]$ has a
larger leading term than $[a]$, then $[b]\geq 2[a]$.

The necessary condition of two pairs $(a,b)$ and $(c,d)$ (where we assume
$[b]>[a]$, $[d]>[c]$ and $[d]\geq[b]$) having comparable distances is either
1). nodes $d$ and $b$ have the leading terms of the same scale. or 2). nodes
$c$ and $d$ have the leading term of the same scale. The reason is (assuming
$[d]$ has a larger leading term than $[b]$ and $[c]$) that $[d]>=2[c]$ and
$2[b]<=[d]$ implies $[d]-[c]\geq[d]/2\geq[b]\geq[b]-[a]+1$ if none of the
conditions are satisfied. In either case where the necessary condition is
satisfied, there must be two nodes of the form $(r_{e,l},r_{e,r})$ for some
edge $e$. This observation largely reduced the possibilities of comparable
pairs. All possible cases are considered below (we use “$x,y$” to denote
unknown elements and “$\approx$” to denote comparable distances):

  1. 1.

$(x,r_{e,l})$ and $(y,r_{e,r})$ for some edge $e$. We have
$[r_{e,r}]-[y]\approx[r_{e,l}]-[x]\Rightarrow[y]-[x]\approx[r_{e,r}]-[r_{e,l}]$.
Assume $e=(v_{i},v_{j})$, and we have $[y]-[x]\approx 2^{j-1}-2^{i-1}$, this
is true only when $y={\widehat{v}}_{j}$ and $x={\widehat{v}}_{i}$ by checking
the leading term of $y$.

  2. 2.

$(x,y)$ and $(r_{e,l},r_{e,r})$. By similar calculation, we should easily get
$y={\widehat{v}}_{j}$ and $x={\widehat{v}}_{i}$ assuming $e=(v_{i},v_{j})$.

And indeed, $\\{{\widehat{v}}_{i},{\widehat{v}}_{j},r_{e,l},r_{e,r}\\}$ is a
conflict quartet (where $e=(v_{i},v_{j})$) since
$[{\widehat{v}}_{j}]_{1}-[{\widehat{v}}_{i}]_{1}<[r_{e,r}]_{1}-[r_{e,l}]_{1}$
but
$[{\widehat{v}}_{j}]_{2}-[{\widehat{v}}_{i}]_{2}>[r_{e,r}]_{2}-[r_{e,l}]_{2}$.
Now, we can conclude that the quartets in conflict set $\mathcal{C}$ have one-
to-one correspondence to edges in $E$, i.e.,
$\mathcal{C}=\\{({\widehat{v}}_{i},{\widehat{v}}_{j},r_{e,l},r_{e,r}|e=(v_{i},v_{j})\in
E\\}$. Now it is not hard to prove there is a size-preserving reduction from
Minimum Vertex Cover to Strong-MIS (with two line metrics).

There is a vertex cover of size $K$ for $G$ $\Rightarrow$ there is an
inconsistent set of size $K$ for
$(\mathcal{M}=\\{{\rho}_{1},{\rho}_{2}\\};X)$: Assume there is a vertex cover
of $G$ with size $K$ denoted by $V^{\prime}=\\{v_{1},\cdots,v_{K}\\}$. Then
the corresponding set
${\widehat{S}}=\\{{\widehat{v}}_{1},\cdots,{\widehat{v}}_{K}\\}$ is a solution
for $(\mathcal{M}=\\{{\rho}_{1},{\rho}_{2}\\};X)$, since this set covers all
edges and thus all possible conflict quartets. The remaining nodes will have
no conflict quartet.

$``\Leftarrow"$ direction: Conversely, assume there is an optimal inconsistent
set with size $K$. It is clear that there is always an optimal solution to
$(\mathcal{M}=\\{{\rho}_{1},{\rho}_{2}\\};X)$ which only includes
${\widehat{v}}_{i}$s. The reason is that including ${\widehat{v}}_{i}$ can
potentially cover multiple conflict quartets, but $r_{e,l}$ (or $r_{e,r}$)
will only cover at most one conflict. For any solution containing $r_{e,l}$
(or $r_{e,r}$), including one of the endpoints of $e$ will also cover the
conflict (covered by $r_{e,l}$). And it can potentially cover other conflicts
and thus reduce the size of the solution. Assume one optimal solution is
$S^{*}=\\{{\widehat{v}}_{1},\cdots,{\widehat{v}}_{K}\\}$ which covers all
conflict quartets, then the corresponding node set $\\{v_{1},\cdots,v_{K}\\}$
is a vertex cover covering all edges due to the one-to-one correspondence
between edges in $E$ and quartets in $\mathcal{C}$. ∎

###  A.3 Proof of Theorem 3.2

###### Proof.

We prove this theorem via a reduction from the Max 2-SAT problem.

Description of reduction. Suppose we are given an instance $(C,X)$ of the Max
2-SAT problem, where $C=\\{c_{1},...,c_{m_{1}},c_{m_{1}+1},c_{m_{1}+m_{2}}\\}$
is a set of clauses. There are $m_{1}$ clauses with one literal and $m_{2}$
clauses with two literals. And $X=\\{x_{1},...,x_{n}\\}$ is a set of
variables. The decision version of the Max 2-SAT problem is that, given
$(C,X)$ and an integer $K$, is there an assignment to variables such that $K$
clauses are satisfied?

From the instance of Max 2-SAT problem, we construct the following instance of
Strong-MIS $(\mathcal{M}=\\{{\rho}_{1},{\rho}_{2}\\};\widehat{X})$ where
${\rho}_{1}$ and ${\rho}_{2}$ are ultrametrics. In particular, we will set up
each metric via its representing tree as introduced in Definition 2.8. As we
will see below, both representing trees of ${\rho}_{1},{\rho}_{2}$ will have
the same structure; while the only difference is the height functions over
internal nodes.

First, we will describe the tree structure $T$ (which will be common for both
${\rho}_{1}$ and ${\rho}_{2}$). The root of $T$ has $m_{1}+m_{2}+1$ children,
$\\{B,{\widehat{c}}_{1},...,{\widehat{c}}_{m_{1}+m_{2}}\\}$, where
${\widehat{c}}_{i}$s correspond to $i$th clauses in $C$. The node $B$ has
$|{\texttt{Ch}}(B)|=2m_{1}+4m_{2}+1$ children denoted by
$b_{1},...,b_{2m_{1}+4m_{2}+1}$ (here for simplicity, we use
${\texttt{Ch}}(B)$ to denote the children set of $B$). The size of
${\texttt{Ch}}(B)$ is designed to be larger than the total number of literals
(allowing duplicates) appeared in the clause set $C$. We show later that one
can assume a maximum consensus always contain all nodes from
${\texttt{Ch}}(B)$. Each ${\widehat{c}}_{i}$ has at most two children
$l_{i1},l_{i2}\in\\{x_{1},...,x_{n},\bar{x_{1}},...,\bar{x_{n}}\\}$
corresponding to the literals in clause $c_{i}$, and each $l$ has two leaf
nodes $d$s as its children. For example, if clause $c_{i}$ has two literals,
then ${\widehat{c}}_{i}$ will have two children $l_{i1},l_{i2}$; And $l_{i1}$
has two children (leaves) $d_{i1},d_{i2}$, $l_{i2}$ has two children (leaves)
$d_{i3},d_{i4}$. If clause $c_{i}$ has only one literal, then
${\widehat{c}}_{i}$ will have one child $l_{i1}$ which has two children
(leaves) $d_{i1}$, $d_{i2}$. See an illustration of the tree structure $T$ in
Figure 6.

Recall that the leaf set of this representing tree $T$ corresponds to the note
set of the metric. Hence, in the constructed Strong-MIS instance, we have that
the note set is
$\widehat{X}=\\{b_{1},...,b_{2m_{1}+4m_{2}+1},d_{11},d_{12},\cdots,d_{m_{1}1},d_{m_{1}2},\cdots,d_{(m_{1}+m_{2})1},\\\
d_{(m_{1}+m_{2})2},d_{(m_{1}+m_{2})3},d_{(m_{1}+m_{2})4}\\}$ with size
$2m_{1}+4m_{2}+1+2m_{1}+4m_{2}=8m_{2}+4m_{1}+1$.

Figure 6: Given an instance of Max 2-SAT with
$C=x_{1}\wedge\bar{x_{3}}\wedge(\bar{x_{1}}\vee x_{2})\wedge(\bar{x_{2}}\vee
x_{3})$, the representing tree structure of the constructed ultrametrics is
shown on the right. $c_{i}$ corresponds to the $i$th clause in $C$. $l_{i1}$
(and $l_{i2}$) are its literals. The corresponding literals are shown in the
bracket.

Now we equip this tree structure $T$ with two height functions $h_{1}$ and
$h_{2}$ mapping internal nodes of $T$ to real values. It generates metrics
${\rho}_{1}$ and ${\rho}_{2}$, respectively. In particular, recall that given
any two leaves $z$ and $z^{\prime}$, their distance
${\rho}_{i}(z,z^{\prime})=h_{i}({\texttt{LCA}}(z,z^{\prime}))$. We set up
$h_{1},h_{2}$ so that
$h_{1}(x_{1})<h_{1}(\bar{x_{1}})<h_{1}(x_{2})<h_{1}(\bar{x_{2}})<...<h_{1}(x_{n})<h_{1}(\bar{x_{n}})<h_{1}(B)<h_{1}({\widehat{c}}_{1})<...<h_{1}({\widehat{c}}_{m_{1}+m_{2}})$
and
$h_{2}(\bar{x_{1}})<h_{2}(x_{1})<h_{2}(\bar{x_{2}})<h_{2}(x_{2})<...<h_{2}(\bar{x_{n}})<h_{2}(x_{n})<h_{2}({\widehat{c}}_{1})<...<h_{2}({\widehat{c}}_{m_{1}+m_{2}})<h_{2}(B)$.
Note that the precise value of each height does not matter as only the
ordering of pairwise distances matters. We use $(T_{1},h_{1})$ and
$(T_{2},h_{2})$ ($T_{1}$ and $T_{2}$ have the same tree structure as $T$) to
denote the two representing trees for ${\rho}_{1}$ and ${\rho}_{2}$,
respectively.

To see how the maximum consensus problem for
$(\\{{\rho}_{1},{\rho}_{2}\\},\widehat{X})$ relates to the maximum
satisfiability of $(C,X)$, note the following: (1) Intuitively, the height
functions $h_{1}$ and $h_{2}$ guarantee that, for a consensus
$\widehat{X}^{\prime}\subset\widehat{X}$, we cannot include both children of
$x_{i}$ and $\bar{x}_{i}$, the heights of $x_{i}$ and $\bar{x}_{i}$ have
opposite orders and thus inconsistent w.r.t. ${\rho}_{1}$ and ${\rho}_{2}$.
For instance, in the example of Figure 6, one cannot include $d_{11},d_{12}$
(children of $l_{11}(x_{1})$) and $d_{31},d_{32}$ (children of
$l_{31}(\bar{x_{1}})$) in $\widehat{X}^{\prime}$. (2) The heights of the
internal node $B$ guarantee that for each ${\widehat{c}}_{i}$, one can only
choose either one of its leaf nodes or two of its leaf nodes which are the
children of the same literal (See Figure 8). For the instance shown in Figure
6, we can include both $d_{41}$ and $d_{42}$ in $\widehat{X}^{\prime}$ since
they are the children of the same literal $l_{41}$. However, one cannot
include both $d_{41}$ and $d_{43}$ in $\widehat{X}^{\prime}$ because
$h_{1}(B)<h_{1}({\widehat{c}}_{4})$ and $h_{2}({\widehat{c}}_{4})<h_{2}(B)$.

Basically, for the construction, the consensus can include two leaf nodes when
the corresponding clause is satisfied; Otherwise it can only include one leaf
node. Below we show that there is an assignment of $X$ satisfying $K$ clauses
in $C$ _if and only if_ there is a consensus of
$\widehat{X}^{\prime}\subset\widehat{X}$ of cardinality
$|\widehat{X}^{\prime}|=|{\texttt{Ch}}(B)|+m_{1}+m_{2}+K$.

$``\Rightarrow^{\prime\prime}$ direction:

Assume there is an assignment to variables of $\\{C,X\\}$ such that $K$
clauses are satisfied. Then we have a consensus of size
$|{\texttt{Ch}}(B)|+m_{1}+m_{2}+K$ as follows. We first include all $b_{i}$s.
For each satisfied clause, we randomly selected one of its literal with true
value and keep both of its children. For the clauses not satisfied, we keep
any one of its four leaves. The selected node set is strongly consistent,
because (1): there are no leaf nodes from different literals of a clause; 2).
we do not keep both leaf nodes from two literals (say, $x_{i}$ and
$\bar{x_{i}}$) of the same variable as we only keep both leaves of true
literals. The size of the set is $|{\texttt{Ch}}(B)|+m_{1}+m_{2}+K$.

More specifically, w.l.o.g., assume nodes in $\widehat{X}^{\prime}$ are
$\\{b_{1},\cdots,b_{2m_{1}+4m_{2}+1},\cdots,\\\ d_{11},d_{12},\cdots,\\\
d_{K1},d_{K2},\cdots,d_{(m_{1}+m_{2})1}\\}$ (See Figure 7). We can also assume
that the corresponding literals for $l_{11},\cdots,l_{K1}$ are
$x_{1},\cdots,x_{K}$. Then all pairwise distances in ${\rho}_{1}$ form the set
$\\{h_{1}(x_{1}),h_{1}(x_{2}),h_{1}(x_{K}),h_{1}(B),h_{1}(root)\\}$ (and
$\\{h_{2}(x_{1}),\cdots,\\\ h_{2}(x_{K}),h_{2}(B),h_{2}(root)\\}$ for
${\rho}_{2}$). One can check the order of those heights are the same in two
metrics, and thus $\widehat{X}^{\prime}$ is a consensus.

Figure 7: An example of leaf nodes included in $\widehat{X}^{\prime}$. For
each satisfied clause $\\{c_{1},\cdots,c_{K}\\}$, we can include two out of
four leaves (these two leaves have to be the children of the same literal).
For unsatisfied clauses, we can keep one leaf. This leads to a consensus with
$|{\texttt{Ch}}(B)|+m_{1}+m_{2}+K$ nodes. The internal nodes with only one
child can be ignored (e.g., $l_{(m_{1}+m_{2})1}$).

$``\Leftarrow"$ direction: Assume there is maximum consensus of
$(\mathcal{M}=\\{{\rho}_{1},{\rho}_{2}\\};\widehat{X})$ with
$|{\texttt{Ch}}(B)|+m_{1}+m_{2}+K$ nodes. Then we want to show that there is
an assignment satisfying at least $K$ clauses based on the following
observations.

  1. 1.

There is always an optimal maximum consensus that keeps all $b_{i}$s. Simply
including all $b_{i}$s will produce a consensus with
$|{\texttt{Ch}}(B)|=2m_{1}+4m_{2}+1$ nodes. If one optimal solution does not
include all $b_{i}$s, it must have removed at least $2m_{1}+4m_{2}$ $b_{i}$s
to avoid any conflict. In this case, there are only at most $2m_{1}+4m_{2}+1$
nodes left.

  2. 2.

For the restricted tree on the nodes from the maximum consensus (including all
$b_{i}$s), there are only two possible options for a subtree rooted at
${\widehat{c}}_{i}$s (See Figure 8). The reason is that we cannot keep leaf
nodes of both literals (e.g., we cannot include both $d_{31}$ and $d_{33}$ for
the case in Figure 6), which will cause a conflict since
$h_{1}(B)<h_{1}({\widehat{c}}_{i})$ but $h_{2}({\widehat{c}}_{i})<h_{2}(B)$.

  3. 3.

For the literal with both children included, there is no conflict. Therefore,
e.g., if $x_{i}$ has both children included, then $\bar{x_{i}}$ cannot. This
is because the heights of $x_{i}$ and $\bar{x_{i}}$ are not consistent, their
four leaf nodes form a conflict quartet.

Figure 8: Two cases of subtrees rooted at ${\widehat{c}}_{i}$. The indexes of
literals or leaves are not important, so they are omitted.

Based on these observations, there is an optimal solution having exactly $K$
subtrees rooted at ${\widehat{c}}_{i}$s with two leaves selected. The two
leaves must be the children of one literal. Also, there will not be any
contradiction from those $K$ literals with two children selected (i.e.,
$x_{i}$, $\bar{x_{i}}$ cannot both have two children selected) We can assign
true value to these literals, and the $K$ corresponding clauses are satisfied.
∎

###  A.4 Proof of Theorem 3.3

###### Proof.

We prove this theorem via a reduction from Minimum Vertex Cover.

Description of reduction. Given an instance of Minimum Vertex Cover,
$G=(V,E)$, where $V=\\{v_{1},v_{2},...,v_{n}\\}$,
$E=\\{e_{1},e_{2},...,e_{m}\\}$. We construct an instance $(\mathcal{M};X)$ of
Strong-MIS, where $\mathcal{M}=\\{{\rho}_{1},{\rho}_{2}\\}$
(${\rho}_{1},{\rho}_{2}$ are two arbitrary metrics) and
$X=\\{r_{1},...,r_{n},{\widehat{v}}_{1},...,{\widehat{v}}_{n}\\}$. Here
${\widehat{v}}_{1},...,{\widehat{v}}_{n}$ correspond to nodes
$\\{v_{1},v_{2},...,v_{n}\\}$ in $V$.

For these two metrics,
${\rho}_{1}(r_{i},{\widehat{v}}_{j})={\rho}_{2}(r_{i},{\widehat{v}}_{j})=1$,
and ${\rho}_{1}(r_{i},r_{j})={\rho}_{2}(r_{i},r_{j})=1$, for $\forall i,j$.
Those pairwise distances are used as standards which will be compared with
pairwise distances of ${\rho}_{1}({\widehat{v}}_{i},{\widehat{v}}_{j})$ and
${\rho}_{2}({\widehat{v}}_{i},{\widehat{v}}_{j})$, for those pairwise
distances,

${\rho}_{1}({\widehat{v}}_{i},{\widehat{v}}_{j})=\begin{cases}1+\epsilon\text{
if }(v_{i},v_{j})\in E,\\\ 0,\text{ if }i=j,\\\ 1\text{
otherwise.}\end{cases}{\rho}_{2}({\widehat{v}}_{i},{\widehat{v}}_{j})=\begin{cases}1-\epsilon\text{
if }(v_{i},v_{j})\in E,\\\ 0,\text{ if }i=j,\\\ 1\text{
otherwise.}\end{cases}$

Clearly, for a fixed edge $(v_{i},v_{j})\in E$,
$({\widehat{v}}_{i},{\widehat{v}}_{j},r_{k},r_{l}),\forall 1\leq k,l\leq n$ is
a conflict quartet, since
${\rho}_{1}({\widehat{v}}_{i},{\widehat{v}}_{j})>{\rho}_{1}(r_{k},r_{l})=1$
but
${\rho}_{2}({\widehat{v}}_{i},{\widehat{v}}_{j})<{\rho}_{2}(r_{k},r_{l})=1$.
We remark that there is an optimal inconsistent set $S^{*}$ of
$(\mathcal{M};X)$ which does not have any point from $\\{r_{1},...,r_{n}\\}$.
It is because $|S^{*}|<n$ by removing all ${\widehat{v}}_{i}$’s except one;
And to cover any conflict quartet, one has to remove at least $n-1$ $r_{i}$s.

Now, we want to show that there is an optimal vertex cover of size $K$ if and
only if there is an inconsistent subset of size $K$.

$``\Rightarrow"$ direction: If there is a vertex cover of size $K$ for $G$,
denoted by $V^{\prime}=\\{v_{1},...,v_{K}\\}$. Then the corresponding set
${\widehat{S}}=\\{{\widehat{v}}_{1},...,{\widehat{v}}_{K}\\}$ is a
inconsistent set, because for the remaining nodes
$\\{{\widehat{v}}_{i}\,|\,{\widehat{v}}_{i}\in X\backslash{\widehat{S}}\\}$,
their pairwise distances are all 1 in both metrics, therefore they form a
consensus together with $r_{i}$s.

$``\Leftarrow"$ direction: Conversely, if there is a minimum inconsistent set
with size $K$ (notice that $K$ is always smaller than $n$ and only contains
nodes from $\\{{\widehat{v}}_{1},...,{\widehat{v}}_{n}\\}$), denoted as
$S^{*}=\\{{\widehat{v}}_{1},...,{\widehat{v}}_{K}\\}$, then there is a vertex
cover $\\{v_{1},...,v_{k}\\}$. That is because, by removing
${\widehat{v}}_{1},...,{\widehat{v}}_{K}$, the remaining elements form a
consensus set. Thus for any edge $(v_{i},v_{j})\in E$, there is at least one
of ${\widehat{v}}_{i},{\widehat{v}}_{j}$ in $S^{*}$.

∎

###  A.5 Missing Figure in Theorem 3.4

The following figure shows an illustration for the 4-approximation algorithm
for Strong-MIS problem.

Figure 9: An illustration for our algorithm. In iteration $i$, the $k$
pointers are pointing to the head of those $k$ lists. When testing the second
list, there is already a conflict. $\\{a,b,e\\}$ are included in the
inconsistent set $S$. In the beginning of the next iteration $i+1$, it first
skips all the edges with nodes in $S$. Edges in green are considered in each
iteration.

###  A.6 Proof of Claim 4.1

###### Proof.

Given a mixed graph $G$, assume $U=\\{u_{0},u_{1},...,u_{j}\\}$ is the
directed cycle with smallest length and $j>2$. For any edge
$(u_{i},u_{i+1}),0\leq i\leq k$ (addition modulo $k+1$), it is either
undirected or from $u_{i}$ to $u_{i+1}$. W.l.o.g., let $(u_{0},u_{1})$ be a
directed edge. Consider the edge connecting $u_{1}$ and $u_{j}$, there are
three cases. If the edge connecting $u_{1}$ and $u_{j}$ is undirected or from
$u_{1}$ to $u_{j}$, $\\{u_{0},u_{1},u_{j}\\}$ form a directed triangle.
Otherwise (i.e., the edge is from $u_{j}$ to $u_{1}$), then
$\\{u_{1},...,u_{j}\\}$ forms a smaller directed cycle. Both cases contradict
with the assumption of smallest length. ∎

###  A.7 Missing proof of Theorem 4.1

###### Proof.

We prove this theorem via a reduction from the Minimum Vertex Cover problem.
Here we propose a similar construction of Theorem 3.1.

Description of the reduction. Suppose we are given a Minimum Vertex Cover
instance $G=(V,E)$, $V=\\{v_{1},...,v_{n}\\}$, $E=\\{e_{1},...,e_{m}\\}$. We
construct an instance
($\mathcal{M}=\\{{\rho}_{1},{\rho}_{2},{\rho}_{3}\\};X\\}$ of the Weak-MIS
problem, where ${\rho}_{1},{\rho}_{2},{\rho}_{3}$ are line metrics and
$X=\\{{\widehat{v}}_{1},...,{\widehat{v}}_{n},r_{e_{1},l_{1}},r_{e_{1},l_{2}},r_{e_{1},r_{1}},r_{e_{1},r_{2}},...,r_{e_{m},l_{1}},r_{e_{m},l_{2}},r_{e_{m},r_{1}},\\\
r_{e_{m},r_{2}}\\}$. Here, we also use $``[\cdot]_{1}"$, $``[\cdot]_{2}"$, and
$``[\cdot]_{3}"$ to represent the coordinates in ${\rho}_{1}$, ${\rho}_{2}$
and ${\rho}_{3}$, respectively. When the coordinate is the same across all
three metrics or there is no ambiguity, we will omit the subscript and use
$``[\cdot]"$ instead.

The coordinates are constructed as follow, and the intuition is that only
triples like
$\\{({\widehat{v}}_{i},{\widehat{v}}_{j}),(r_{e,l_{1}},r_{e,r_{1}}),(r_{e,l_{2}},r_{e,r_{2}})\\}$
(where $e=(v_{i},v_{j})$) can potentially cause a directed triangle (See
Figure 10 for an example):

  1. 1.

For all of these line metrics, the coordinates $[{\widehat{v}}_{i}]=2^{i-1}$.

  2. 2.

For all of these metrics, $[r_{e_{j},l_{1}}]=2^{n+4j-4}$, and
$[r_{e_{j},l_{2}}]=2^{n+4j-2}$.

  3. 3.

For each edge $e=(v_{i},v_{j})$, in ${\rho}_{1}$,
$[r_{e,r_{1}}]_{1}=[r_{e,l_{1}}]_{1}+[{\widehat{v}}_{i}]_{1}-[{\widehat{v}}_{j}]_{1}-2\epsilon$,
$[r_{e,r_{2}}]_{1}=[r_{e,l_{2}}]_{1}+[{\widehat{v}}_{i}]_{1}-[{\widehat{v}}_{j}]_{1}-\epsilon$;
in ${\rho}_{2}$,
$[r_{e,r_{1}}]_{2}=[r_{e,l_{1}}]_{2}+[{\widehat{v}}_{i}]_{2}-[{\widehat{v}}_{j}]_{2}+\epsilon$,
$[r_{e,r_{2}}]_{2}=[r_{e,l_{2}}]_{2}+[{\widehat{v}}_{i}]_{2}-[{\widehat{v}}_{j}]_{2}+2\epsilon$;
in ${\rho}_{3}$,
$[r_{e,r_{1}}]_{3}=[r_{e,l_{1}}]_{3}+[{\widehat{v}}_{i}]_{3}-[{\widehat{v}}_{j}]_{3}+\epsilon$,
$[r_{e,r_{2}}]_{3}=[r_{e,l_{2}}]_{3}+[{\widehat{v}}_{i}]_{3}-[{\widehat{v}}_{j}]_{3}-\epsilon$.

Figure 10: An example of constructed three line metrics given graph $G=(V,E)$.

Comparable pairwise distances. Similarly as Theorem 3.1, we will use the
concept of _comparable distances_. Here two distances are comparable if they
are _different_ and differ by at most $6\epsilon$. The constant factor for
$\epsilon$ is changed accordingly since the difference between the coordinates
of the same point in two metrics is at most $3\epsilon$ (instead of
$2\epsilon$ in Theorem 3.1). The leading terms of ${\widehat{v}}_{i}$s,
$r_{e,l_{1}}$ (or $r_{e,r_{1}}$) and $r_{e,l_{2}}$ (or $r_{e,r_{2}}$) are in
different scales. For any edge $e_{k}=(v_{i},v_{j})$ (here we overuse $k$ for
simplicity), the comparable pairs are (recall that $(a,b),(c,d)$ are
comparable only when either $[b],[d]$ or $[c],[d]$ have the same leading
term):

  1. 1.

$({\widehat{v}}_{i},{\widehat{v}}_{j})$, $(r_{e_{k},l_{1}},r_{e_{k},r_{1}})$
and $(r_{e_{k},l_{2}},r_{e_{k},r_{2}})$. The distances are around
$2^{j-1}-2^{i-1}$.

  2. 2.

$({\widehat{v}}_{i},r_{e_{k},l_{1}})$ and
$({\widehat{v}}_{j},r_{e_{k},r_{1}})$. The distances are around
$2^{n+4k-4}-2^{i-1}$.

  3. 3.

$({\widehat{v}}_{i},r_{e_{k},l_{2}})$ and
$({\widehat{v}}_{j},r_{e_{k},r_{2}})$. The distances are around
$2^{n+4k-2}-2^{i-1}$.

  4. 4.

$(r_{e_{k},l_{1}},r_{e_{k},l_{2}})$ and $(r_{e_{k},r_{1}},r_{e_{k},r_{2}})$.
The distances are around $2^{n+4k-2}-2^{n+4k-4}$.

A triangle can potentially be directed only when all three underlying edges
are mutually comparable.

For any triangle, there are three cases in total depending on the scale of
distances of three underlying edges
$(x_{1},x_{2}),(y_{1},y_{2}),(z_{1},z_{2})\in X\times X$.

  1. 1.

If the distances of these three pairs all are not comparable, the
$\epsilon$-distortion will not affect the orders of the distances at all.
Therefore, the three metrics should agree on the ordering of these pairwise
distances. And clearly, the triangle is not directed.

  2. 2.

If two of them have comparable distance, e.g., $(x_{1},x_{2})$ and
$(y_{1},y_{2})$. Then w.l.o.g., assume $(z_{1},z_{2})$ has much larger
distance compared with those two. Then the edge in the auxiliary graph from
$(z_{1},z_{2})$ to the other two are all outgoing, thus the triangle is not
directed. Otherwise, if $(z_{1},z_{2})$ has a smaller distance, the edges are
all incoming and the triangle is also not directed.

  3. 3.

Only when all three edges have comparable distances, there will be possibility
that the triangle is directed. If we look at the triangle formed by
$\\{({\widehat{v}}_{i},{\widehat{v}}_{j}),(r_{e,l_{1}},r_{e,r_{1}}),(r_{e,l_{2}},r_{e,r_{2}})|e\in
E,e=(v_{i},v_{j})\\}$. We have relations
$({\widehat{v}}_{i},{\widehat{v}}_{j})<(r_{e,l_{1}},r_{e,r_{1}})$,
$(r_{e,l_{1}},r_{e,r_{1}})<(r_{e,l_{2}},r_{e,r_{2}})$ and
$(r_{e,l_{2}},r_{e,r_{2}})<({\widehat{v}}_{i},{\widehat{v}}_{j})$ by plurality
vote. And they indeed form a directed triangle from
$({\widehat{v}}_{i},{\widehat{v}}_{j})$ to $(r_{e,l_{2}},r_{e,r_{2}})$ to
$(r_{e,l_{1}},r_{e,r_{1}})$, and back to
$({\widehat{v}}_{i},{\widehat{v}}_{j})$.

Therefore, the directed triangles are
$\\{({\widehat{v}}_{i},{\widehat{v}}_{j}),(r_{e,l_{1}},r_{e,r_{1}}),(r_{e,l_{2}},r_{e,r_{2}})\,|\,e=(v_{i},v_{j})\in
E\\}$. Including ${\widehat{v}}_{i}$s in the inconsistent set is better than
including $r_{e,l}$ or $r_{e,r}$ since it can possibly cover multiple directed
triangles. Thus, there is always an optimal solution consisting of only
${\widehat{v}}_{i}$s. One can always replace $r_{e,l}$ and $r_{e,r}$s by
${\widehat{v}}_{i}$s (where ${\widehat{v}}_{i}\in e$) and still cover the
directed triangles. Now we are ready to show that there is a vertex cover of
size $K$ for $G$ if and only if there is a weak inconsistent set of size $K$
for $(\mathcal{M}=\\{{\rho}_{1},{\rho}_{2},{\rho}_{3}\\};X)$.

$``\Rightarrow"$ direction: Assume $V^{\prime}=\\{v_{1},\cdots,v_{K}\\}$ is a
vertex cover for $G$. Then clearly
${\widehat{S}}=\\{{\widehat{v}}_{1},\cdots,{\widehat{v}}_{K}\\}$ is a weak
inconsistent set. This is because ${\widehat{S}}$ covers all potential
directed triangles.

“$\Leftarrow$” direction: We showed that there is always an optimal solution
only consisting of ${\widehat{v}}_{i}$s. Assume the optimal solution is
${\widehat{S}}^{*}=\\{{\widehat{v}}_{1},\cdots,{\widehat{v}}_{K}\\}$. To cover
all directed triangles, for any edge $e=(v_{i},v_{j})\in E$, there must be at
least one corresponding node ${\widehat{v}}_{i}$ or ${\widehat{v}}_{j}$
contained in the inconsistent set. Therefore,
$V^{\prime}=\\{v_{1},\cdots,v_{K}\\}$ is a vertex cover of $G$.

∎

###  A.8 Proof of Lemma 4.2

#### Proving statement (i) of Lemma 4.2.

To prove (i), note that if $w=(p,q)$ splits, then $LCA(p,q)$ is the root $r$
in each of the three representing trees, and thus $U_{?}(p,q)=10$, for
$?\in\\{X,Y,Z\\}$. Now take any two other graph nodes
$w_{1}=(p_{1},q_{1}),w_{2}=(p_{2},q_{2})\in P\times P$. A simple case analysis
shows that no matter these two other pairs split or not, the three graph nodes
$w,w_{1},w_{2}$ cannot form a directed triangle. For example, if neither
$w_{1},w_{2}$, then there will be two directed edges $(w,w_{1})$ and
$(w,w_{2})$ in the auxiliary graph $\mathcal{G}$, and thus no matter what
direction the edge between $w_{1}$ and $w_{2}$ is, the triangle
$w,w_{1},w_{2}$ cannot be directed. This proves (i).

#### Proving statement (ii) of Lemma 4.2.

Note that by (i), to check whether auxiliary graph $\mathcal{G}$ has directed
triangles or not, we only need to consider the subgraph
$\widehat{\mathcal{G}}$ of $\mathcal{G}$ spanned by nodes which do not split.
Hence each node $(p,q)$ will be such that $p,q\in\boxtimes$ where $\boxtimes$
could be ${\mathsf{A}},{\mathsf{B}},{\mathsf{C}},{\mathsf{D}}$ or
${\mathsf{S}}$; in this case, we say that $(p,q)$ is of type-$\boxtimes$. Two
nodes are of the same type if they are both of type-$\boxtimes$ (i.e, both of
type-${\mathsf{A}}$, ${\mathsf{B}}$, etc).

For such a generic non-splitting node $(p,q)$, we list its distance under
ultrametric $U_{X},U_{Y}$, and $U_{Z}$, respectively, which is also the height
of the ${\texttt{LCA}}(p,q)$ in representing trees $T_{X},T_{Y}$ and $T_{Z}$,
respectively. See Figure 11. In particular, for a non-splitting node
$({\widehat{{\mathsf{s}}}},{\widehat{{\mathsf{s}}}}^{\prime})\in{\mathsf{S}}$,
we first only consider the case that
${\widehat{{\mathsf{s}}}},{\widehat{{\mathsf{s}}}}^{\prime}$ do not share
coordinate. (The only non-splitting nodes not covered by the table in Figure
11 is of the form
$({\widehat{{\mathsf{s}}}},{\widehat{{\mathsf{s}}}}^{\prime})$ where
${\widehat{{\mathsf{s}}}}$ and ${\widehat{{\mathsf{s}}}}^{\prime}$ have shared
coordinate.)

non-splitting graph node | $T_{X}$ | $T_{Y}$ | $T_{Z}$
---|---|---|---
$(a,a^{\prime})\in{\mathsf{A}}$ | 5 | 3 | 2
$(b,b^{\prime})\in{\mathsf{B}}$ | 4 | 0 | 4
$(c,c^{\prime})\in{\mathsf{C}}$ | 3 | 2 | 0
$(d,d^{\prime})\in{\mathsf{D}}$ | 1 | 5 | 1
$({\widehat{{\mathsf{s}}}},{\widehat{{\mathsf{s}}}}^{\prime})\in{\mathsf{S}}$ with no shared coordinate | 2 | 4 | 5

Figure 11: Left: each entry in the table gives the distance (height of LCA of
this pair of points) of a non-splitting graph node under ultrametrics $U_{X}$,
$U_{Y}$ and $U_{Z}$, respectively (i.e., w.r.t. trees $T_{X}$, $T_{Y}$ and
$T_{Z}$, respectively). Right: the subgraph induced such nodes in the left
cannot contain any directed triangle.

Based on these distances, the subgraphs induced by such nodes are shown in the
right picture of Figure 11. Note that this subgraph does not contain any
directed triangle. Combining with (i), this means that any directed triangles
$\Delta w_{1}w_{2}w_{3}$, where $w_{i}$s are all _of different types_ , has to
contain a node $({\widehat{{\mathsf{s}}}},{\widehat{{\mathsf{s}}}}^{\prime})$
such that ${\widehat{{\mathsf{s}}}},{\widehat{{\mathsf{s}}}}^{\prime}$ have
shared coordinate(s).

To prove (ii), what remains is to consider a triangle $\Delta w_{1}w_{2}w_{3}$
where at least two of them, say $w_{1}$ and $w_{2}$ are of the same type.
Suppose all $w_{i}$s are of types listed in the table of Figure 11, then it is
easy to see that in this case, the resulting triangle can only be of the
shapes in Figure 12, and thus cannot be a directed triangle. Hence at least
one of $w_{i}$ has to be non-splitting (by statement (i)), yet not included in
the types covered in the table of Figure 11 – in other words, at least one
$w_{i}$ is of the form
$({\widehat{{\mathsf{s}}}},{\widehat{{\mathsf{s}}}}^{\prime})$ where
${\widehat{{\mathsf{s}}}},{\widehat{{\mathsf{s}}}}^{\prime}$ have shared
coordinate(s).

Figure 12: Three possible directed triangles.

Putting the above two paragraphs together, statement (ii) then follows.

#### Proving statement (iii) of Lemma 4.2.

Finally, consider a node
$w=({\widehat{{\mathsf{s}}}},{\widehat{{\mathsf{s}}}}^{\prime})$ of
type-${\mathsf{S}}$, but such that ${\widehat{{\mathsf{s}}}}$ and
${\widehat{{\mathsf{s}}}}^{\prime}$ have shared coordinates. In particular,
${\widehat{{\mathsf{s}}}}$ and ${\widehat{{\mathsf{s}}}}^{\prime}$ could share
$x$-coordinate, share $y$-coordinate, share $z$-coordinate, share both $x$\-
and $y$-coordinates, share both $x$\- and $z$-coordinates, or share both $y$\-
and $z$-coordinates.

non-splitting graph node | $T_{X}$ | $T_{Y}$ | $T_{Z}$
---|---|---|---
$(a,a^{\prime})\in{\mathsf{A}}$ | 5 | 3 | 2
$(b,b^{\prime})\in{\mathsf{B}}$ | 4 | 0 | 4
$(c,c^{\prime})\in{\mathsf{C}}$ | 3 | 2 | 0
$(d,d^{\prime})\in{\mathsf{D}}$ | 1 | 5 | 1
$({\widehat{{\mathsf{s}}}},{\widehat{{\mathsf{s}}}}^{\prime})\in{\mathsf{S}}$ with shared $y$ and $z$ coordinates | 2 | 1 | 3

Figure 13: Left: each entry in the table gives the distance (height of LCA of
this pair of points) of a non-splitting graph node under ultrametrics $U_{X}$,
$U_{Y}$ and $U_{Z}$, respectively (i.e., w.r.t. trees $T_{X}$, $T_{Y}$ and
$T_{Z}$, respectively). Right: the subgraph induced such nodes in the left
contains a directed triangle (highlighted in red) formed by
$w=({\widehat{{\mathsf{s}}}},{\widehat{{\mathsf{s}}}}^{\prime}),(c,c^{\prime}),(d,d^{\prime})$.

By a simple but tedious case analysis, one can verify that in each of these 6
cases, $w=({\widehat{{\mathsf{s}}}},{\widehat{{\mathsf{s}}}}^{\prime})$ will
form a directed with some pair of nodes from
$w_{1},w_{2}\in\\{(a,a^{\prime}),(b,b^{\prime}),(c,c^{\prime}),(d,d^{\prime})\\}$.
For example, suppose ${\widehat{{\mathsf{s}}}}$ and
${\widehat{{\mathsf{s}}}}^{\prime}$ share both $y$\- and $z$\- coordinates.
Then the subgraph induced by
$w=({\widehat{{\mathsf{s}}}},{\widehat{{\mathsf{s}}}}^{\prime})$ and
$\\{(a,a^{\prime}),(b,b^{\prime}),(c,c^{\prime}),\\\ (d,d^{\prime})\\}$ is
shown in Figure 13, and the triangle formed by $w$ and
$(c,c^{\prime}),(d,d^{\prime})$ is a directed triangle. This thus proves
statement (iii).

As commented in the main text, the heights of these nodes are computed by a
computer program to guarantee the three statements.

###  A.9 Proof of Theorem 4.3

###### Proof.

We prove the theorem via a reduction from Minimum Vertex Cover to Weak-MIS.

Description of the reduction. Given an instance of Minimum Vertex Cover,
$G=(V,E)$, $V=\\{v_{1},...,v_{n}\\}$ and $E=\\{e_{1},...,e_{m}\\}$. We
construct an instance $(\mathcal{M}=\\{{\rho}_{1},{\rho}_{2},{\rho}_{3}\\};X)$
of Weak-MIS with 3 metrics on node set
$X=\\{r_{e_{1}},...,r_{e_{m}},{\widehat{v}}_{1},...,{\widehat{v}}_{n}\\}$. We
will assign an index number for each edge, and will use that index to assign
distances between nodes incident to that edge.

For any edge $e_{k}=(v_{i},v_{j})$, we construct the following gadget (Figure
14), where $M=3m$ and $\epsilon\ll 1$.

Figure 14: A directed triangle.

All the other pairwise distances are $2M$. One can check that, in the
auxiliary graph $\mathcal{G}$, a directed triangle (if exists) always
corresponds to an edge $e=(v_{i},v_{j})$, and the triangle is consist of
$({\widehat{v}}_{i},{\widehat{v}}_{j}),({\widehat{v}}_{i},r_{e})$ and
$({\widehat{v}}_{j},r_{e})$. It is because that the only comparable distances
are triples of form
$\\{({\widehat{v}}_{i},{\widehat{v}}_{j}),({\widehat{v}}_{i},r_{e}),({\widehat{v}}_{j},r_{e})\\}$.
Now we prove that there is an vertex cover of size $K$ for $G$ if and only if
there is a (weakly) inconsistent set of size $K$ for
$(\mathcal{M}=\\{{\rho}_{1},{\rho}_{2},{\rho}_{3}\\};X)$.

$``\Rightarrow"$ direction: Assume for graph $G$, there is a vertex cover
$S=\\{v_{1},...,v_{K}\\}$. Then
$\widehat{S}=\\{{\widehat{v}}_{1},...,{\widehat{v}}_{K}\\}$ is a Weak-MIS,
since each directed triangle corresponds to an edge in $G$, and has at least
one relevant node in $S$ ($\widehat{S}$).

$``\Leftarrow"$ direction: If we have a Weak-MIS of size $K$, denoted as
$\widehat{S}^{*}=\\{{\widehat{v}}_{1},...{\widehat{v}}_{K}\\}$ (there is
always an optimal solution only consisting of ${\widehat{v}}_{i}$s). There is
no directed triangle means that for each edge, at least one endpoint is in
$S=\\{v_{1},...,v_{K}\\}$, which is a vertex cover of size $K$.

∎

###  A.10 Summary of Hardness Results

We end this section with a summary table showing hardness results in different
cases.

Problem | Input | Hardness |  Inapprox. factor |  Approx. algorithm
---|---|---|---|---
Strong-MIS | 2 Arbitrary metrics |  NP-complete (Theorem 3.3) |  2 UGC (Corollary 3.1) |  4 (Theorem 3.4)
Strong-MIS | 2 Line metrics |  Weakly NP-complete (Theorem 3.1) | ? | 4
Strong-MIS | 2 Ultrametrics |  NP-complete (Theorem 3.2) | ? | 4
Weak-MIS | 3 Arbitrary metrics | NP-complete |  2 UGC (Theorem 4.3) |  6 (Theorem 4.4)
Weak-MIS | 3 Line metrics |  Weakly NP-complete (Theorem 4.1) | ? | 6
Weak-MIS | 3 Ultrametrics |  NP-complete (Theorem 4.2) | ? | 6

Table 2: Hardness results for different cases.

##  Appendix B NP-complete Problem Repository

Here we list the NP-complete problems that are used in the hardness proofs.

######  Definition B.1 (Minimum Vertex Cover).

[11]
Instance: Graph $G=(V,E)$ and a positive integer $K$.
Question: Does $G$ have a vertex cover of size at most $K$?

A vertex cover is a set of nodes $V^{\prime}\subset V$ that every edge has at
least one endpoint in $V^{\prime}$. This is a classical problem mentioned in
Karp’s 21 np-complete problems.

######  Definition B.2 (Max 2-SAT).

[9]
Instance: Given a boolean expression $E$ of $n$ variables in conjunctive
normal form (CNF) that is the conjunction of $m$ clauses over $n$ variables,
each of which is the disjunction of at most two distinct literals. An integer
$K$.
Question: Is there an assignment to variables such that $K$ clauses are
satisfied?

######  Definition B.3 (Tournament Feedback Vertex Set).

[7]
Instance: A tournament (fully connected directed graph) $T$ and an integer
$K$.
Question: Is there a vertex set $S$ with at most $K$ nodes whose deletion will
result in an acyclic directed graph.

In [7], Dom showed that Feedback Vertex Set problem is NP-complete.

######  Definition B.4 (3-dimensional Matching).

[11]
Instance: Let $X,Y,Z$ be three disjoint sets with the same size. And
${\mathcal{S}}\subset X\times Y\times Z$ consists of triples $(x,y,z)$ where
$x\in X,y\in Y,z\in Z$. Given $(X,Y,Z;{\mathcal{S}})$ and an integer $K$.
Question: Is there a 3-dimensional matching $\Pi\subset{\mathcal{S}}$ with
size at least $K$?

This is also a problem in the list of Karp’s 21 np-complete problems.