The Weighted Sitting Closer to Friends than Enemies Problem in the Line
Julio Aracena Christopher Thraves Caro


The Weighted SCFE Problem in the Line]The Weighted Sitting Closer to Friends than Enemies Problem in the Line
      

CI^2MA Departamento de Ingeniería Matemática, Facultad de Ciencias Físicas y Matemáticas, Universidad de Concepción, Chile.jaracena@ing-mat.udec.cl Julio Aracena was partially supported by ANID-Chile through the project Centro de Modelamiento Matemático (AFB170001) of the PIA Program:“Concurso Apoyo a Centros Científicos y Tecnológicos de Excelencia con Financiamiento Basal”, and by ANID-Chile through Fondecyt project 1151265.


Departamento de Ingeniería Matemática, Facultad de Ciencias Físicas y Matemáticas, Universidad de Concepción, Chile.cthraves@ing-mat.udec.cl


[2000]Primary 05C22, 05C62, 68R10. Secondary 05C85  







The weighted Sitting Closer to Friends than Enemies (SCFE) problem is to find an injection of the vertex set of a given weighted
graph into a given metric space so that, for every pair of incident edges with different weight, the end vertices of the heavier edge are closer 
than the end vertices of the lighter edge.
The Seriation problem is to find a simultaneous reordering of the rows and columns of a symmetric matrix such that the entries are monotone nondecreasing in rows and
columns when moving towards the diagonal. If such a reordering exists, it is called a Robinson ordering.   
In this work, we establish a connection between the SCFE problem and the Seriation problem.
We show that if the extended adjacency matrix of a given weighted graph G has no Robinson ordering then G has no injection in ℝ that solves the SCFE problem. 
On the other hand, if the extended adjacency matrix of G has a Robinson ordering, 
we construct a polyhedron that is not empty if and only if there is an injection of the vertex set of G in ℝ that solves the SCFE problem.

As a consequence of these results, 
we conclude that 
deciding
the existence of (and constructing) such an injection in ℝ for a given 
complete
weighted graph can be done in polynomial time. 
On the other hand, we show that deciding if an incomplete 
weighted graph has such an injection in ℝ
is NP-Complete.


[
    Christopher Thraves Caro
    
============================





§ INTRODUCTION

Consider a data set. The task is to construct a graphic 
representation of
the data set so that similarities between data points are graphically 
expressed.
To complete this task, the only information
available is a similarity matrix of the data set, i.e., a 
symmetric, square matrix 
whose entry ij contains a similarity measure between data points 
i and j (the larger the value the more similar the data points are).
Hence, the task is to draw all data
points in a paper so that for
every 
three data points i, j, and k, if 
i 
is at least as similar to j than k,
then i should be placed closer in the drawing to j than k.
In colloquial words, for each data point j, the farther the other 
data points are, the less similar they are to j.
 
A slightly simpler version of this problem, introduced in 
<cit.>, has been studied under the name of the Sitting 
Closer to Friends than Enemies (SCFE) problem. 
The SCFE problem uses signed graphs as an input. Therefore, the 
similarity matrix 
has entries 1 and -1, representing similarity and dissimilarity, or 
friendship and enmity between the data points, from where 
the problem obtains its name. The SCFE problem has been studied in the 
real line <cit.> 
and in the circumference 
<cit.> (which means that the paper is
the real line or the circumference). In both cases, the real line and
the
circumference, it has been shown 
that deciding the existence of such an injection for a given signed 
graph
is NP-Complete.
Nevertheless, in both cases again, when the problem is restricted to 
complete signed graphs there exists a characterization of the families 
of complete signed graphs 
that admit a solution for the SCFE problem and it can be decided in 
polynomial time <cit.>. 
Therefore, a natural next step is to consider the case when 
similarities range in an extended set of values. 






The SCFE problem in the line seems to be 
closely related to the Seriation problem.
Liiv in <cit.> defines the Seriation 
problem as “an exploratory data analysis 
technique to reorder objects into a 
sequence along a one-dimensional continuum so that it best reveals 
regularity and pattering among the whole series”. 
Seriation has applications in archaeology <cit.>, 
data visualization <cit.>, exploratory analysis 
<cit.>,
bioinformatics <cit.>, and machine learning 
<cit.>, among others. Liiv in 
<cit.>
presents an interesting survey on 
seriation, matrix reordering and its applications.
The first important contribution of this document is to 
show that the SCFE and the Seriation problems are different. Indeed, 


we show that seriation is a necessary condition to 
solve the SCFE problem, but 
it is not sufficient. 

To continue with our exposition, in Section <ref> we introduce the notation and
definitions used along the document. 
The rest of the document is organized as follows. 
In Section <ref>, we present the state of the art and 
contextualize our contributions.
In Section <ref>, we present the characterization 
of weighted graphs with an injection in ℝ that satisfies the
restrictions of the SCFE problem. Furthermore, we present the 
results related with complete weighted graphs. 
In Section <ref>, 
we present the results regarding incomplete weighted graphs.
We conclude in Section <ref> with some final remarks and
future work.  


§ NOTATION AND DEFINITIONS

We use standard notation. A graph is denoted by G=(V,E). We 
consider only undirected graphs, without parallel edges and loopless. 
The set of vertices of G is V and the set of edges is E, a set of 
2-elements subsets of V. We use n and m to denote |V| and 
|E|, respectively. 
Two distinct vertices u and v in V are said to be 
neighbors if 
{u,v}∈ E. In that case, 
we say that they  are connected by an edge
which is denoted by {u,v}. 



A graph is said to be complete if 
every pair of distinct vertices is connected by an edge, otherwise, we say that 
it is incomplete. 

In this document, we work with weighted graphs. We denote by 
w:E→ℝ^+ 
a positive real valued function that assigns w({u,v}), a positive 
real value, to the edge {u,v} in E. 
For our purposes, we consider that w is a similarity measure, i.e., 
for any {u,v}∈ E the value w({u,v}) measures how similar u 
and v are.


We consider that the larger the similarity measure is, the more similar 
the vertices are. 
It is worth mentioning that the fact that the weights are positive is 
just a choice made for simplicity. Actually, if we have negative weights, one can 
translate all weights by a constant and obtain only positive weights. 
All our results are still valid if we remove this assumption. 


Let (ℳ, d) be a metric space. 
A drawing of a graph G=(V,E) into  ℳ is an 
injection D:V→ℳ. 
We define a certain type of drawings that  capture the requirements of 
the SCFE problem.   

Let G=(V,E) be a graph, and w:E→ℝ^+ be a 
positive function on E. 
Let (ℳ, d) be a metric space.
We say that a drawing D of G into ℳ is valid 
distance if,
for all pair {t,u}, {t,v} of incident edges in E such that  
w({t,u}) > w({t,v}),

    d(D(t),D(u)) < d(D(t),D(v)).



In colloquial words, a drawing is valid distance, or simply 
valid, when 
it places vertices t and u strictly closer than t
and v in ℳ 
whenever t and u have a strictly larger similarity measure 
than t and v.  
Now, the weighted SCFE problem in its most general presentation is 
defined as follows. 

Given a weighted graph G and a metric space ℳ, the 
weighted
SCFE problem in ℳ is to decide whether G has a valid 
drawing in 
ℳ, and, 
in case of a positive answer, find one.


In this document, we focus our attention on the case when the metric 
space is the real line, i.e.,
we consider the metric space to be the set of real values ℝ 
with the Euclidean distance.  



Since we present a matrix oriented analysis, we introduce the next two 
matrix related definitions. 
Given a matrix A, the entry in the i-th row and j-th
column of A is denoted by A_ij.  
For every weighted graph G=(V,E) and an ordering π of the vertex set V, 
we define A^π(G), the similarity matrix of G ordered according to π, as follows. Let π_i be the i-th
element of V according to π, then: 



    A^π(G)_ij = 
    
    *     if  i ≠ j {π_i,π_j}∉ E, 
    
    w({π_i,π_j})     i ≠ j {π_i,π_j}∈ E, 
    max_e ∈ Ew(e)     i = j.

This matrix is also known as 
the extended weighted adjacency matrix of G.
The i-th row (and i-th column) contains the 
similarities between vertex π_i and the rest of the vertices of G.
We may use only A^π when the graph G is contextually clear or only A when G and π are
contextually clear. 
Note that any similarity matrix of any weighted graph is symmetric since
w is symmetric.



A similarity matrix of a complete weighted graph does not have 
entries with the symbol *. 
In that case, we say that a similarity matrix is complete, 
otherwise we say that it is incomplete. 

W. S. Robinson in <cit.> introduced Robinsonian matrices. 
A complete similarity matrix A is said to be Robinson
if its entries are monotone nondecreasing in rows and 
columns when moving towards the diagonal, i.e., if for all
integers 1≤ i < j ≤ n, 

    A_ij≤min{A_ij-1,A_i+1j}.

Equivalently, a complete similarity matrix A is Robinson if for all 
integers 1≤ i < l ≤ n and j,k ∈ [i,l]:

    A_il≤min{A_ij,A_kl}.

On the other hand, a complete similarity matrix A is Robinsonian  
if its rows and columns 
can be reordered simultaneously by a permutation π such that A^π is Robinson. 

The Robinson matrix definition can be naturally extended to incomplete 
matrices.  In that case, a similarity matrix is Robinson 
if its specified entries are monotone nondecreasing in rows and 
columns when moving towards the diagonal, 

i.e., 
an incomplete similarity matrix A is Robinson
if for all 
integers 1≤ i < l ≤ n and j,k ∈ [i,l], such that  
A_il≠ *, A_ij≠ * and A_kl≠ *,

    A_il≤min{A_ij,A_kl}.


Again, we say that a similarity matrix is Robinsonian  if
its rows and columns can be simultaneously reordered in such a way that 
it passes to be Robinson.

Finally, we say that an ordering π of the vertex set V of a weighted graph G=(V,E) 
is Robinson if A^π(G) is Robinson. 





§ CONTEXT, RELATED WORK, AND OUR 
CONTRIBUTIONS

Robinsonian matrices were defined by W. S. Robinson in  
<cit.> in a study on how to order chronologically 
archaeological deposits. The Seriation problem introduced in the 
same work  
is to decide whether the similarity matrix of a data set 
is Robinsonian and
reorder it as a Robinson matrix if possible. 
Recognition of complete Robinsonian matrices has been studied by several
authors. Mirkin et al. in <cit.> presented an O(n^4) 
recognition algorithm, where n× n is the 
size of the matrix. On the other hand, using divide and conquer 
techniques, Chepoi et al. in <cit.> introduced an 
O(n^3) recognition algorithm. Later,
Préa and Fortin in <cit.> provided an O(n^2) optimal
recognition algorithm for complete Robinsonian matrices using PQ trees. 

Using the relationship between Robinsonian matrices and unit interval 
graphs presented in <cit.>, Monique Laurent and Matteo 
Seminaroti  in <cit.>
introduced a recognition algorithm for Robinsonian matrices that uses 
Lex-BFS, whose time complexity is 
O(L(m+n)), where m is the number of nonzero entries in the 
matrix,










and L is the number of different 
values in the matrix. 
Later in <cit.>, the same authors presented a 
recognition algorithm with time complexity O(n^2+nmlog n )
that uses similarity-first search, an extension of breadth-first search 
for weighted graphs. 
Again, using the relationship between Robinsonian matrices and unit 
interval graphs, Laurent et al. in <cit.>
gave a characterization of Robinsonian matrices via forbidden patterns.

The Seriation problem also has been studied as an optimization problem.
Given an  n× n matrix D, seriation in the presence of 
errors is to find a Robinsonian matrix R 
that minimizes the error defined as: max ||D_ij-R_ij|| over all 
i and j in {1,2,3,…,n}. Chepoi et al. in 
<cit.> proved that seriation in the presence of 
errors is an NP-Hard problem. 
Later in <cit.>, Chepoi and Seston gave a factor 16 
approximation algorithm. Fortin in <cit.> surveyed
the challenges for Robinsonian matrix recognition. 

The SCFE problem was first introduced by Kermarrec and Thraves in
<cit.>. Besides the introduction of the SCFE problem, 
the authors of  <cit.>
also characterized the set of complete signed graphs with a valid 
drawing
in ℝ and presented a polynomial time recognition algorithm. 
Later, Cygan et al. in <cit.>
proved that the SCFE problem is NP-Complete if it is not restricted to 
complete signed graphs.  Moreover, they gave a different 
characterization
of the complete signed 
graphs with a valid drawing in ℝ. Actually, the authors of 
<cit.> proved that a complete signed graph has a valid 
drawing in ℝ if and only if its positive subgraph is a unit 
interval graph.
The SCFE problem in the real line also was studied as an optimization 
problem by Pardo et al. in <cit.>. In that work, the 
authors defined 
as an error a violation of the inequality in Definition 
<ref> and provided optimization algorithms that 
construct a drawing attempting to minimize the number of errors.

The SCFE problem also has been studied for different metric spaces.
First, Benitez et al. in <cit.> studied the 
SCFE
problem in the circumference. 
The authors of that work proved that the SCFE problem in the 
circumference is NP-Complete and gave a characterization of the complete
signed graphs with a valid drawing. 
Indeed, they showed that a complete signed graph has a valid drawing in 
the circumference if and only if its positive subgraph is a proper 
circular arc graph.  
Later, Becerra in <cit.> studied the SCFE problem in 
trees. The main result of her work was to prove that a complete signed 
graph G has a valid drawing in a tree if and only if its  positive 
subgraph is strongly chordal. 

Spaen et al. in <cit.> studied the SCFE problem from a 
different perspective. They studied the problem of finding
L(n), the smallest dimension k such that any signed graph on n 
vertices has a valid drawing in ℝ^k, with respect
to the Euclidean distance. They showed that log_5 (n-3) ≤ L(n) ≤
n - 2.



  
Our Contributions
Our first contribution is to show that the Seriation and the SCFE 
problems are not the same. Indeed, we show that the SCFE problem implies a stronger condition 
than the Seriation problem. 
 In Lemma <ref>, 
we show that if a weighted graph G=(V,E) has a valid drawing in ℝ, there is
a Robinson ordering of V. 
Nevertheless, in Lemma <ref>, 
we show that there is a weighted graph G=(V,E) with a Robinson ordering
of V, but G does not have a valid drawing in ℝ.






On the other hand, for each weighted graph G with a Robinson ordering of its vertex set,
we construct a polyhedron defined by an inequality system 
M(G)𝐱≤𝐛 which we use to provide a
characterization of the set of weighted graphs with a valid 
drawing in ℝ. 


Indeed, we show in Theorem <ref> that a weighted 
graph G has a valid drawing in ℝ 
if and only if its polyhedron defined by M(G)𝐱≤𝐛 is not 
empty.

Our first result applied to complete weighted graphs allows us to 
conclude in Corollary <ref> that given a complete 
weighted graph G, determining whether G has 
a valid drawing in ℝ, and finding one if applicable, can be 
done in polynomial time.








On the other hand, when the weighted graph is not complete, the previous
result does not apply anymore.
In Corollary 
<ref>, we state that
recognition of incomplete 
Robinsonian 
matrices is NP-complete. Furthermore,
using results shown in <cit.> by Cygan et al.,
we conclude, under the assumption of the Exponential Time Hypothesis,  the nonexistence of a subexponential-time algorithm
that determines if an incomplete similarity matrix is 
Robinsonian. 
Therefore, the construction of the polyhedron 

cannot be done in polynomial 
time (unless P=NP).  

Nevertheless, in Section <ref>,
we provide a recognition algorithm of n× n incomplete Robinsonian matrices with time complexity O(n· 2^2n).





 



§ ROBINSON ORDERINGS AND VALID DISTANCE DRAWINGS
 
In this section we connect Robinson orderings and valid distance drawings. 
We start this section showing 
that, 
if a weighted graph has a valid drawing in 
ℝ its  similarity matrix is Robinsonian. Therefore, 
having a Robinsonian similarity matrix is a necessary condition 
to have a valid distance drawing in ℝ.


Let G=(V,E) be a weighted graph. If G has a valid distance drawing in 
ℝ, then V has a Robinson ordering.  
 

Let G=(V,E) be a  weighted graph with weight function w. Let 
D:V→ℝ be a valid distance drawing of G in ℝ. 
The valid drawing D determines an ordering on the set of vertices V.

Indeed, for u and v in V, we say that u<_D v if D(u) < D(v). 
We show that A(G) is Robinson when it is written using the ordering determined by D 
for its rows and columns.

Enumerate V according to the ordering determined by D. 
Consider any integers i,j, k,l such that 
1≤ i < l ≤ n, j,k ∈ [i,l],
and  A(G)_il≠ *, A(G)_ij≠ * and 
A(G)_kl≠ *. First, we point our that 
A(G)_il≤ 
A(G)_ij, since D is 
valid distance, and d(D(i),D(l)) > d(D(i),D(j)). Equivalently, since D is valid distance and 
d(D(i),D(l)) > d(D(k),D(l)), we have A(G)_il≤ A(G)_kl. 
Therefore, A(G)_il≤min{A(G)_ij,A(G)_kl}.
In conclusion, A(G), the similarity matrix of G written according to the ordering determined 
by D, is Robinson. 
Hence, the ordering determined by D is Robinson. 



Nevertheless, having a Robinson similarity matrix is not enough to have
a valid distance drawing in ℝ. 
In the next, lemma we show the existence of a weighted graph with a
Robinson ordering of its vertices but without valid distance drawing in 
ℝ. 

There exists a complete weighted graph G with Robinson similarity matrix 
but without a valid distance drawing in ℝ.


Let G be the complete weighted graph with vertex set {a,b,c,d,e} 
and similarity matrix

    A(G)=
    [ 5 2 2 1 1; 2 5 3 2 1; 2 3 5 4 1; 1 2 4 5 5; 1 1 1 5 5;   ]

written with rows and columns ordered as a,b,c,d,e.
A(G) is Robinson, nevertheless, we will show by contradiction 
that G does not have a valid drawing in ℝ. 

Assume that G has a valid drawing D in ℝ. Since the order
a,b,c,d,e of the rows and columns of A(G) is the only one that 
makes A(G) Robinson, D has to be such that 

    D(a) < D(b) < D(c) < D(d) < D(e).


Since D is a valid drawing, the following 
inequalities hold: 

    D(b) - D(a)    >    D(c) -D(b) 
    
    D(e)-D(b)    >    D(b) - D(a) 
    
    D(c)-D(b)    >    D(d) - D(c) 
    
    D(e)-D(c)    >    D(c)-D(a) 
    
    D(d)-D(c)    >    D(e)-D(d) .


Without loss of generality, assume that D(a)=0. 
Then, from inequalities (<ref>) and (<ref>) we obtain:

    D(b) < D(c) <2D(b).

On the other hand, from inequalities (<ref>) and (<ref>),
we obtain 2D(c) < D(e) < 2D(d)-D(c), which implies:

    3D(c) < 2D(d).

Finally, inequality (<ref>) is equivalent to 2D(d) < 
4D(c)-2D(b), 
which, together with (<ref>), implies 2D(b) < 
D(c). 
But, the last inequality contradicts inequality (<ref>).




§ THE WEIGHTED SCFE PROBLEM IN THE LINE

The goal of this section is to find a solution for the weighted SCFE 
problem in the real line.  
We 
transform
the weighted SCFE problem in the real line 
into the problem of finding a point in a convex polyhedron.
Actually, given a weighted graph G, we construct a convex 
polyhedron defined by an inequality system M(G)𝐱≤𝐛, where 



each point 𝐱=(x_1,x_2,…,x_n) in the convex polyhedron is
a valid drawing of G in ℝ. Indeed, for any given 
𝐱 in the polyhedron, each variable x_i 
represents the position of vertex i in ℝ for that valid 
drawing. 

Therefore, finding a point in the polyhedron is 
equivalent to find a valid drawing for G in ℝ.








We first remark that if a given weighted graph G has a valid drawing 
in
ℝ, it actually has an infinite number of them. 
Indeed, given a valid drawing in ℝ for a weighted graph G, 
one can obtain a different valid drawing for the same graph by summing 
or
multiplying 
each vertex position by any positive constant. The second case (when 
each
position is multiplied by a positive constant) is important for us, 
because 
it allows us to state the following lemma. 

Let G=(V,E) be a weighted graph with a valid distance drawing in ℝ. Then, 
for any ϵ > 0 there exists a valid distance drawing D_ϵ of G 
in 
ℝ such 
that: 
 
    min_u,v ∈ V  |D_ϵ(u)-D_ϵ(v)| ≥ϵ.



Let G be a weighted graph with a valid drawing D in ℝ. We
consider without loss of generality that v is labeled according to the ordering determined by D, i.e., 1<_D2<_D3<_D… <_D n. 
Consider any ϵ > 0. Let δ = min_ 1 ≤ i < n  
D(i+1)-D(i) be the minimum distance between 
two consecutive vertices in the drawing. Multiply every D(i) 
by ϵ/δ. Therefore, we obtain a new valid drawing 
D_ϵ 
defined as D_ϵ(i)=ϵ D(i)/δ, 
such that min_u,v ∈ V  |D_ϵ(u)-D_ϵ(v)|≥ϵ.



Now, we proceed with the construction of the matrix M(G) and the 
vector 𝐛 of the inequality system M(G)𝐱≤𝐛 that defines our polyhedron.
By Lemma <ref>, the ordering of the vertex set of G defined by a valid 
drawing is Robinson. 


Hence, we may assume that A(G) is Robinson.  

If we want to construct a valid drawing D in ℝ 
for G, the vertices should be ordered in the same way as the rows and 
columns of A(G). 
Hence, if the i-th row (or column) of A(G) contains the 
similarities of vertex i ∈{1,2,3,…, n}, then D has to be so that
D(1) < D(2) < ⋯ < D(n). Therefore, we want x_1<x_2<⋯ 
<x_n. Now, considering Lemma <ref>, we write the 
following set of restrictions for any ϵ > 0:

    x_i-x_i+1≤ -ϵ,   ∀ i ∈{1,2,3,…,n-1}.

These restrictions are called ordering restrictions. 
Lemma <ref> allows us to pick any ϵ > 0 
for these restrictions. We set a value for ϵ, and use that value for the inequalities we define below. 

On the other hand, each row of A(G) provides two types of restrictions.
We call these restrictions right with respect to left and  
left with respect to right restrictions. 
Right with respect to left restrictions are obtained as follows. For 
each
row j and for every index k > j, let i(k) be the largest index 
such
that i(k) < j and A(G)_ji(k) < A(G)_jk.
Therefore, since A(G)_ji(k) < A(G)_jk, vertices j and k are
more similar between them than vertices j and i(k). Hence, in any 
valid drawing  D it must occur D(k)-D(j) < D(j)-D(i(k)).
We transform this strict inequality into the following restriction for a 
sufficiently small ϵ > 0: 

    x_i(k)-2x_j+x_k  ≤ -ϵ,   ∀ j ∈{2,3,…,n-1}∀  k>j.


Left with respect to right restrictions are symmetrical to the previous 
restriction. For each row j and for every index i < j, let k(i) be
the smallest index such that j < k(i) and A(G)_ji >A(G)_jk(i).
Therefore, since A(G)_ji >A(G)_jk(i), vertices i and j are 
more
similar between them than vertices j and k(i). Hence, in any valid 
drawing  D, it must occur D(j)-D(i) < D(k(i))- D(j).
We transform this strict inequality into the following restriction for a 
sufficiently small ϵ > 0: 

    -x_i+2x_j-x_k(i)≤ -ϵ,   ∀ j ∈{2,3,…,n-1}∀  i<j.


It is worth mentioning that some of the inequalities described in 
equations (<ref>) and 
(<ref>) may be obtained from inequalities 
presented in Equation (<ref>) and different 
inequalities described in equations (<ref>) and
(<ref>). 
Hence, some restrictions may be redundant. In an 
attempt to keep the presentation of this document 
clean and simple, we omit a discussion
in this regard. It is worth mentioning though that it does not impact
the
results of this document.






























Given a weighted graph G with n vertices, the matrix
of restrictions of G (or the matrix of coefficients of G),
denoted by  
M(G), is the matrix that 
includes the n-1 ordering restrictions, the at most (n-2)(n-1)/2 
right with respect to left restrictions, and  
the at most  (n-2)(n-1)/2 left with respect to right restrictions. 
In total, the matrix M(G) has h≤ (n-1)^2 rows and n columns.
On the other hand, the vector 𝐛 is a h × 1 vector 
with a -ϵ in every entry. 




An example of a weighted graph, its Robinson similarity matrix, 
and its corresponding matrix of restrictions is given in Figure 
<ref>.









































































Now, we show that for any weighted graph G with Robinson similarity matrix, 
the convex polyhedron defined by M(G)𝐱≤𝐛
is not empty if and only if G has a valid drawing in ℝ. 













































































































Let G be a  weighted graph with Robinson similarity matrix A(G). Let
M(G) be the h × n matrix of restrictions of G obtained from A(G).
Let 𝐛 be the 
h × 1 vector 
with -ϵ < 0 in every entry. Then, 
G has a valid distance drawing in ℝ if and only if
the polyhedron defined by M(G)𝐱≤𝐛 
is not empty. 


Let G be a weighted graph with valid distance drawing in
ℝ. 
Let D be a valid drawing of G in ℝ.
Label the vertices of G according to the order determined by D, i.e., 
the left most vertex in D is vertex 1, the next vertex is 
vertex 2 and so on until vertex n. 
By construction of M(G)𝐱≤𝐛,
for any ϵ > 0, D can be scaled to a valid drawing 
D' such that
the vector (D'(1),D'(2),…,D'(n)) belongs to the polyhedron 
M(G)𝐱≤𝐛.

On the other hand, assume that the polyhedron 
M(G)𝐱≤𝐛 
is not empty. Let x=(x_1,x_2…,x_n) be a point in
M(G)𝐱≤𝐛.
Label the vertices of G according to the columns of its Robinson similarity matrix A(G), 
i.e., vertex i is the vertex 
corresponding to the i-th column of A(G).
Now, consider the drawing D of G in ℝ defined as follows:
D(i)=x_i for all 1≤ i ≤ n.

We show now that D is valid distance. 
Assume that D is not a valid distance drawing. Therefore, 
there exist three vertices i,j and k such that A_ij < A_ik,
but |D(i)-D(j)| ≤ |D(i)-D(k)|. Note that the last inequality 
is not valid if 
D(i) < D(k) < D(j) or if D(j) < D(k) < D(i), therefore, these 
cases are discarded.
If D(i)< D(j)<D(k) or
D(k)<D(j)<D(i), there is a  
contradiction since A_ij< A_ik, and, in that case, A(G)
would not be Robinson. 

Assume that D(j) < D(i) < D(k).
Therefore, |D(i)-D(j)| ≤ |D(i)-D(k)| becomes 
D(i) -D(j) ≤ D(k)-D(i), or equivalently, 0 ≤ D(j)-2D(i)+D(k).
Nevertheless, since  A_ij < A_ik,  
the right with respect to left restriction x_j - 2x_i +x_k ≤ 
-ϵ is included in 
M(G)𝐱≤𝐛. Therefore, since D comes 
from a point in M(G)𝐱≤𝐛,
D(j)-2D(i)+D(k) ≤ -ϵ, which is a contradiction since 
ϵ > 0. 

If we assume now  D(k) < D(i) < D(j), then |D(i)-D(j)| ≤ 
|D(i)-D(k)| becomes 0 ≤ -D(k)+2D(i)-D(j).
Nevertheless, since  A_ij < A_ik, the left with respect to 
right restriction -x_k + 2x_i -x_j ≤ 
-ϵ is included in M(G)𝐱≤𝐛. 
By equivalent arguments than 
before, we achieve a contradiction. 

Therefore, the condition |D(i)-D(j)| ≤ |D(i)-D(k)| 
is not possible, and hence, D is a valid distance drawing. 


If the valid drawings are restricted to be nonnegative, 
then the SCFE problem can be treated as a linear program. 
Because, if the polyhedron defined by the inequality system M(G)𝐱≤𝐛 
is not empty, 
there is always a point 𝐱 in that polyhedron

with x_1=0.
Therefore, the SCFE problem is equivalent to find
min x_1 subject to M(G)𝐱≤𝐛, and 
nonnegative 𝐱.

The last Theorem is stated for a weighted graph with a Robinson
similarity matrix. It is well known that a Robinsonian matrix may have many different Robinson orderings. Therefore, the reader may wonder which of these many Robinson orderings is the one that we can use to apply Theorem <ref>. In the next part of this section, 
we answer that question for complete weighted graphs. Indeed, we show that any Robinson ordering will provide the same answer when Theorem <ref> is applied. 


Now we show that the existence of a valid
distance drawing in ℝ 
corresponding to a Robinson ordering is consistent among all Robinson
orderings of the vertex set of a complete weighted graph.
In other words, we show that, 
given a complete weighted graph G=(V,E), if there is a Robinson
ordering π of V
and a valid distance drawing D of G such that the ordering induced
by D is equal to π, 
then, for any Robinson ordering σ of V there exists a valid
distance drawing Σ
of G such that the ordering induced by Σ is equal to σ.

Given a Robinson ordering π of V, we say that 
π has a 
valid drawing if
there is a valid distance drawing D of G=(V,E) in ℝ such 
that 
the ordering induced by D is equal to π.

To prove our result, we use the fact that all Robinson orderings for a complete similarity matrix
can be represented by a PQ-tree
(see <cit.>).
A PQ-tree on a set V is a tree that represents a set of permutations of V. 
The nodes of a PQ-tree are of three types: leaves, that represent the elements
of V, P nodes, and Q nodes. The children of a P node are not ordered, and any permutation 
of them is allowed. The children of a Q node are ordered and that order can only be reversed.   
Hence, given a PQ-tree 𝒯, we obtain a permutation of V represented by 
𝒯 by applying one of the operations
allowed to each P and Q nodes, and then looking at the leaves to find the resultant permutation.
Let say π is a permutation obtained in this way. If we modify the operation applied
to one node α of 𝒯 and maintain all the other nodes equal, 
we say that the new permutation σ is obtained from π by modifying α. 

For a node α of a PQ-tree 𝒯, 
we denote 𝒯(α) the subtree of 
𝒯 with root α and by S_α the set of leaves of 
𝒯(α). 
A node of a PQ-tree is said to be basic if all its children are 
leaves. Préa et al. in 
<cit.> show that for every node α, and for every
Robinson ordering π 
represented in a PQ-tree 𝒯, S_α is 
consecutive according to π,
i.e., S_α={π_l+1,π_l+2,…,π_l+r} for some 0≤ l and  
0≤ r ≤ n-l, where π_i denotes the i-th vertex according to π.
In addition, we denote by  S_α^I:=π_l+1 and S_α^R:=π_l+r  the first and the last elements of S_α, respectively.
On the other hand, Préa et al. also show that 

    w({u,x})=w({v,x})   ∀  u,v ∈ S_α x 
    ∈ V∖ S_α.


We show now that operations on a Q-node of the PQ-tree
maintain the characteristic of having a valid distance drawing.

Let G=(V,E) be a complete weighted graph, 𝒯 be the PQ-tree that 
represents all  Robinson orderings of V, and α be a 
Q-node 
of 𝒯. 
Let π and σ be two Robinson orderings of V such that
σ is
obtained from π by applying the operation associated to α (i.e., reversing the children of  α). 
Then, π has a valid distance drawing if and only if σ has a valid distance drawing. 


Let G, 𝒯, α, π, and σ be as in 
the statement of the lemma. 
Assume that π has a valid drawing D. 
We show that σ also 
has a valid drawing. 
It is worth noticing that this sense of the equivalence is
enough to show the lemma, since the opposite sense is shown by 
exchanging π and σ and repeating the analysis.  

Let π_1,π_2,…,π_n be the vertex set of G
ordered according to π.
The children of α can be P nodes, Q nodes or leaves.
Without loss of generality, we assume that all of them are P
nodes or Q nodes, since a
leaf can be seen as a Q node with a
single children that is the leaf. Let β_1,β_2,…,
β_h be α's children ordered according to π.
We use the following notation for the elements of  S_β_t: 

    {π_l+R_t-1+1,π_l+R_t-1+2,…,
    π_l+R_t-1+r_t=π_l+R_t},

where R_0=0 and R_t = R_t-1+ r_t, and |S_β_t|=r_t.

Let β̃_1,β̃_2,…,
β̃_h be  α's children ordered according to σ.
We use the following notation for the elements of  S_β̃_t: 

    {σ_l+R̃_t-1+1,σ_l+R̃_t-1+2,…,σ_l+R̃_t-1+r̃_t=σ_l+R̃_t},

where R̃_0=0 and R̃_t = R̃_t-1 +r̃_t where | S_β̃_t|=r̃_t =r_h-t+1.

Note that R̃_t = R_h-R_h-t,  R_t = R̃_h-R̃_h-t and R̃_h=R_h. In addition, S_β̃_t= S_β_h-t+1 and S_β_t= S_β̃_h-t+1.  In particular 
    S_β̃_t^I=π_l+R_t-1+1= S_β_h-t+1^I= σ_l+R̃_h-t+1
 
and 
    S_β̃_t^R=π_l+R_t= S_β_h-t+1^R= σ_l+R̃_h-t+1.

Hence, 

    x ∈ S_β̃_t    ⟺    x ∈{σ_l+R̃_t-1+1, …,σ_l+R̃_t}
       ⟺    x ∈ S_β_h-t+1
       ⟺    x ∈{π_l+R_h-t+1,…,π_l+R_t-h+1}.

 
Assume that σ_i=x is the j-element of β̃_t,  then 

    σ_i= σ_l+R̃_t-1+j⟹ i=l+R̃_t-1+j ⟹ j=i-l-R̃_t-1.

On the other hand, x is the j-element of  β_h-t+1, i.e., x= π_l+R_h-t+j. Hence: 
    σ_i=π_l+R_h-t+j= π_l+R_h-t+i-l-R̃_t-1= π_i+R_h-t-R_h+R_h-t+1.

Therefore, σ is as follows:

    σ_i=
    π_i      i ∈ [1,l],
    π_i+R_h-t-R_h+R_h-t+1    i ∈ [l+R̃_t-1+1,l+R̃_t],  t ∈{1, …, h},
    π_i      i ∈ [l+R̃_h+1,n].


We denote by f:{1, …, n}→{1, …, n} the  implicit bijection defined above in σ_i=π_f(i). 
Next, we recursively define the  drawing Σ such that Σ(σ_l+1)=D(π_l+1) and ∀ i ∈{l+2, …, n}: 
 
    d(Σ(σ_i), Σ(σ_i-1) )=
      
     d(D(π_f(i)), D(π_f(i)-1))    σ_i ∈ S_β̃_t∖{S_β̃_t^I }, 
        t ∈{1, …, h}
    
     d(D(S^R_β_h-t+2), D(S^I_β_h-t+1))    σ_i = S_β̃_t^I, 
        t ∈{2, …, h}.

Thus, we define the following drawing Σ that induces σ: 

    Σ(σ_i)= 
          
    D(π_i)     i ∈ [1,l], 
    Σ(σ_i-1) + D(π_i)-D(π_i-1)      i= l+1, 
    Σ(σ_i-1) + D(π_f(i)) - D(π_f(i)-1)     i ∈ [l+R̃_t-1+2, l+R̃_t], 
        t ∈ [1, h],
    Σ(σ_i-1) + D(π_f(l+R̃_t-2+1))-D(π_f(l+R̃_t))     i = l+R̃_t-1+1, 
        t ∈ [2, h],
    
    D(π_i)     i ∈ [l+R̃_h+1,n].


Observe that: 


  * Σ(σ_l+1)=Σ(σ_l) + D(π_l+1) - D(π_l)= D(π_l)+ D(π_l+1) - D(π_l)=D(π_l+1),

  * i = l+R̃_t-1+1 ⟺σ_i= S_β̃_t^I, π_f(l+R̃_t-2+1)=S_β̃_t-1^I and π_f(l+R̃_t)=S_β̃_t^R.



We show now that Σ is a valid distance drawing
for G that induces σ as an ordering. By contradiction, assume that there exists a triplet σ_i, 
σ_j,
σ_k that breaks Definition <ref>, 
for some values 1≤ i<j<k≤ n.
If the three elements of the triplet do not belong to S_α,  
their positions according to Σ do not change. Therefore, the 
distances between them do not change. Hence, they cannot violate 
Definition <ref>. 
On the other hand, if the three elements of the triplet belong to S_β_t for some 1≤ t ≤ h, 
as we have seen in the previous paragraph, they maintain their distances. Therefore, 
they cannot violate 
Definition <ref>. 

Assume that only one element of the triplet belongs to S_α. For instance, σ_i∈ S_α, while σ_j∉ S_α and σ_k ∉ S_α.
On the other hand, assume that 
d(Σ(σ_i),Σ(σ_j)) ≥ d(Σ(σ_j), Σ(σ_k)), while w(σ_i,σ_j) > w(σ_j,σ_k). Since σ_i and σ_l+1
belong to S_α and σ_j∉ S_α, 
Equation (<ref>) implies
w(σ_l+1,σ_j) = w(σ_i,σ_j). Since, 
d(Σ(σ_l+1),Σ(σ_j))≥ d(Σ(σ_i),Σ(σ_j)), the triplet 
σ_l+1,σ_j,σ_k also breaks Definition 
<ref>.



Now,

    d(Σ(σ_l+1),Σ(σ_j)) = Σ(σ_j) - Σ(σ_l+1)       = D(π_j) - D(π_l+1)
          = d(D(π_l+1),D(π_j)),

and

    d(Σ(σ_j), Σ(σ_k)) = Σ(σ_k) - Σ(σ_j) = D(π_k)- D(π_j) = d(D(π_j),D(π_k)).

Therefore, d(D(π_l+1),D(π_j))≥ d(D(π_j),D(π_k)). 
On the other hand, 
    w(σ_l+1,σ_j) = w(π_l+R_h-1+1,π_j),
 since σ_l=π_l+R_h-1+1 and σ_j=π_j. But, 
Equation (<ref>) implies

    w(π_l+R_h-1+1,π_j) = w(π_l+1,π_j),
 since π_l+R_h-1+1 and π_l belong to S_α, and π_j ∉ S_α. 
In conclusion, 
    w(π_l+1,π_j) = w(π_l+R_h-1+1,π_j) = w(σ_l,σ_j)  > w(σ_j,σ_k) = w(π_j,π_k).
 
Hence, the triplet π_l+1,π_i,π_k breaks Definition 
<ref> in D, which is a contradiction since D is valid distance. 
The analysis of all cases when one element of 
the triplet belongs to S_α are equivalent to this analysis 
by showing that either σ_l+1,σ_j,σ_k or  σ_l+R_h,σ_j,σ_k also breaks Definition 
<ref>. We omit them to simplify the presentation. 



Assume now that two elements of the triplet belong to S_α. Say σ_i and σ_j belong to S_α, while σ_k does not belong 
to S_α. Assume as well 
that 
    d(Σ(σ_i),Σ(σ_j)) ≥ d(Σ(σ_j), Σ(σ_k)),
 while w(σ_i,σ_j) > w(σ_j,σ_k).

Since σ is Robinson, we have that:

    w(σ_l+1,σ_l+R_h) ≥ w(σ_l+1,σ_j) ≥ w(σ_i,σ_j),

and

    w(σ_j,σ_k) ≥ w(σ_l+R_h,σ_k).

Therefore, w(σ_l+1,σ_l+R_h) > w(σ_l+R_h,σ_k).
On the other hand, 
    d(Σ(σ_l+1),Σ(σ_l+R_h)) ≥ d(Σ(σ_l+1),Σ(σ_j)) ≥ d(Σ(σ_i),Σ(σ_j))
 and  

    d(Σ(σ_j), Σ(σ_k)) ≥ d(Σ(σ_l+R_h), Σ(σ_k)).


Hence, 
    d(Σ(σ_l+1),Σ(σ_l+R_h)) ≥ d(Σ(σ_l+R_h), Σ(σ_k))
 and 
the triplet σ_l+1,σ_l+R_h,σ_k also breaks Definition <ref>.
Now,

    d(Σ(σ_l+1),Σ(σ_l+R_h))    =   Σ(σ_l+R_h)-Σ(σ_l+1)
       =    D(π_l+R_h)-D(π_l+1)
       =    d(D(π_l+1),D(π_l+R_h)),

and

    d(Σ(σ_l+R_h), Σ(σ_k))    =   Σ(σ_k) - Σ(σ_l+R_h)
       =    D(π_k) - D(π_l+R_h)
       =    d(D(π_l+R_h),D(π_k)).

Therefore, 
    d(D(π_l+1),D(π_l+R_h)) 
    ≥ d(D(π_l+R_h),D(π_k).
 
On the other hand, applying repeatedly 
Equation (<ref>) 
we obtain:

    w(π_l+R_h,π_l+1)   =   w(σ_l+1,σ_l+R_h)
       >    w(σ_l+R_h,σ_k)
       =    w(π_l+1,π_k)
       =    w(π_l+R_h,π_k).

Therefore, the triplet π_l+1,π_l+R_h,π_k
breaks Definition <ref>. Which is a contradiction
because D is valid distance. The analysis of all cases when two elements of 
the triplet belong to S_α are equivalent to this analysis. We omit them to simplify the presentation. 


Finally, assume that the three elements 
of the triplet belong to S_α.  
These three vertices cannot all be in 
S_β̃_t for any t since, in this 
case, the distances between them according to Σ 
remain the same as in D. Therefore, they could not break 
Definition (<ref>).
Assume that σ_i and σ_j belong to
S_β̃_t
and σ_k belongs to S_β̃_p with 
1≤ p < t ≤ h.
Assume as well that 
d(Σ(σ_i),Σ(σ_j)) ≥ d(Σ(σ_j), 
Σ(σ_k)), while w(σ_i,σ_j) > 
w(σ_j,σ_k).

It is worth noticing, that σ inverts the ordering of 
the children of α. 
Indeed, using the relationship  β̃_t= β_h-t+1, 
we have: 

    S_β̃_t   =   {σ_l+R̃_t-1+1,…,σ_l+R̃_t}= S_β_h-t+1  = {π_l+R_h-t+1,…,π_l+R_h-t+1}

and

    S_β̃_p   =   {σ_l+R̃_p-1+1,…,σ_l+R̃_p}= S_β_h-p+1  = {π_l+R_h-p+1,…,π_l+R_h-p+1}


By Equation (<ref>) 
    w(σ_i,σ_j)>w(σ_j,σ_k)=w(σ_k,σ_l+R̃_t-1+1)=w(σ_l+R̃_t-1+1,σ_l+R̃_p).

 Since D is a valid drawing, 
    d(D(π_i),D(π_j))<d(D(π_l+R_h-t+1),D(π_l+R_h-p+1)).

Thus, 

    d(Σ(σ_i),Σ(σ_j))   =d(D(π_i),D(π_j))<d(D(π_l+R_h-t+1),D(π_l+R_h-p+1)) 
       = d(Σ(σ_l+R̃_t), Σ(σ_l+R̃_p-1+1)) ≤ d(Σ(σ_j), 
    Σ(σ_k)),

 which is a contradiction. 
The analysis of all cases when the three elements of 
the triplet belong to S_α are equivalent to this analysis. We omit them for simplicity of the presentation. 


Now, we show that any operation on a P-node of the PQ-tree
maintains the characteristic of having a valid distance drawing.

Let G=(V,E) be a complete weighted graph, 𝒯 be the
PQ-tree that 
represents all  Robinson orderings of V, and α be a
P-node 
of 𝒯. 
Let π and σ be two Robinson orderings of V such
that 
σ is
obtained from π via a permutation of the children of α.
Then, π has a valid drawing if and only if σ has a
valid 
drawing. 


We use Lemma <ref> in this proof, since 
this lemma is a particular case of the previous lemma. 

Let G, 𝒯, α, π, and σ be as in 
the statement of the lemma. 
Assume that π has a valid drawing D. 
We will show that σ also 
has a valid drawing. 
It is worth noticing that, as in the previous lemma, this sense of the equivalence is enough to show the lemma. 

The children of α can be P nodes, Q nodes or leaves.
Without loss of generality, we assume that all of them are P
nodes or Q nodes, since a
leaf can be seen as a Q node with a
single children that is the leaf. Let β_1,β_2,…,
β_h be α's children ordered according to π. 
It is enough for us to consider that σ is obtained via 
a transposition of two 
consecutive children of α, since any permutation of
S_α 
can be 
expressed as a product of
transpositions of consecutive elements in S_α.
Let β_t and β_t+1 be the two children to be 
transposed that produce σ.
Now, let 𝒯' be a PQ-tree obtained from 𝒯 by replacing β_t and β_t+1
with a Q node that has as children β_t and β_t+1.
Now, it is worth noticing that 𝒯'
encodes π and σ. Furthermore, Lemma <ref>
implies that if π has a valid drawing, then σ
also has a valid drawing, and the proof is completed. 


With these two lemmas together we can state the result. 

Let G=(V,E) be a complete weighted graph and π be any Robinson ordering of V. 
If π has a valid drawing, all Robinson orderings of V have a valid drawing.   



Since
complete 
Robinsonian matrices 
can be recognized in time O(n^2), it is possible to 
construct
the matrix M(G) in polynomial time when G is complete. 
Therefore, we can state the 
following corollary. 

Let G be a complete weighted graph. Deciding whether G has a valid 
drawing in ℝ can be done in polynomial time. Moreover, a 
valid drawing for G in ℝ can be computed also in 
polynomial time if such drawing exists.




§ THE WEIGHTED SCFE PROBLEM FOR INCOMPLETE 
WEIGHTED GRAPHS

The construction presented in the previous section can also be applied to 
incomplete weighted graphs. The only requirement is that the matrix
A is presented as a Robinson matrix. 
Nevertheless, we will see in this section that, 
if the condition of being complete is not requested for the weighted 
graph, it is not possible to determine in polynomial 
time whether its similarity matrix is Robinsonian or not, unless P=NP.
Despite this bad result, we present an exponential-time algorithm 
to recognize incomplete Robinsonian matrices. Hence, once this recognition 
has been done, we can apply the tools developed in the previous section 
to solve the weighted SCFE problem.
It is worth noticing that, in the case of incomplete weighted graphs, we do not have a result equivalent to Theorem <ref>. Hence, we cannot guarantee that after applying 
the methodology developed in the previous section to incomplete weighted graphs, we will obtain a definitive answer.

Cygan et al. in <cit.>
proved the NP-Completeness of the particular case of the SCFE 
problem where the weight in the edges can only take values
+1 or -1. On the other hand, Kermarrec and Thraves proved  
in <cit.> the following theorem rephrased in 
our own words.
 [Lemmas 3 and 4 in  <cit.>]
 Let G=(V,E) be a weighted graph and w:E→{+1,-1} be its weight function. 
Then, G has a valid distance drawing in ℝ 
if and only if there exists an ordering π of V 
that verifies the following two conditions: 




  * For all i<j<k such that {π_i,π_k} and 
{π_j,π_k} belong to E, 

    w({π_j,π_k})=-1      
    w({π_i,π_k})=-1.


  * For all i<j<k such that {π_i,π_k} and 
{π_i,π_j} belong to E,

    w({π_i,π_j})=-1     w({π_i,π_k})=-1.
  




In other words, a weighted graph G=(V,E) with weights +1 or -1 
has a valid distance drawing in the line 
if and only if there exists an ordering π of V such that A^π(G) is 
Robinson.
Hence, using these two results, we can state the following corollary.

Let G be an incomplete weighted graph and A(G) be its similarity matrix. 
Deciding whether A(G) is Robinsonian or not is a NP-Complete problem. 






















































Besides this negative result, Cygan et al. also proved in 
<cit.>  
the existence of a constant C>0  
such that no algorithm
solves the  SCFE problem in the line in time O(2^C(n+m)), unless the  
Exponential Time Hypothesis[The Exponential Time Hypothesis 
states that there exists a constant C>0 such that no algorithm solving the
3-CNF-SAT problem in O(2^CN) exists, where N denotes the number of variables
in the input formula.] (ETH) fails.
Therefore, we conclude that, under the assumption of the ETH,
it is impossible to have a
subexponential-time algorithm 
that determines if the similarity matrix of an 
incomplete weighted graph is Robinsonian. 

On the positive side, 
using similar ideas
to those presented in <cit.>, 
we present an exponential-time algorithm 
that decides if a given incomplete similarity matrix 
is Robinsonian or not.
We start with the following definition.

Let A be an incomplete n× n similarity matrix. 
Let {V,U} be a bipartition of the set {1,2,…,n}.
We say that an element u ∈ U is good for V
if for all k ∈ V and p∈ U

    A_ku≠ *     A_kp≠ *  A_ku≥ A_kp,

and

    A_pu≠ *     A_pk≠ * 
    A_pu≥ A_pk.



Now, we state the following result. 
 
Let A be an incomplete n× n similarity matrix. 
A is Robinsonian if and only if 
there exists an ordering π=π_1, π_2,…,π_n of
the set {1,2,…,n}
such that for every 
1≤ j ≤ n-1, the element π_j+1 is good for 
{π_1, …,π_j }.

 
Let A be Robinsonian and  π=π_1, π_2, …, π_n be a Robinson
ordering of its rows and columns. Therefore, A^π is Robinson. 
We show by contradiction that the ordering π satisfies the conditions
of the lemma. Assume for instance that the first condition is 
broken for some 1≤ j ≤ n-1. 
Therefore, there exists  1≤ k ≤ j and j+1 < p ≤ n such that: 
A_π_kπ_j+1≠ *, 
A_π_kπ_p≠ *, and 
A_π_kπ_j+1 < A_π_kπ_p. 
Since, 
A_π_kπ_j+1=A^π_kj+1, A_π_kπ_p=A^π_kp, and j+1 < p,
we obtain a contradiction with the fact that A^π is Robinson.  
A similar conclusion can be drawn if we assume that 
the second condition of the lemma is 
broken for some 1≤ j ≤ n-1. 
Therefore, the necessary condition for A to be  Robinsonian holds.
 
Assume now that there exists an ordering 
π=π_1, π_2, …,π_n such that
for every 1≤ j ≤ n -1, the element π_j+1 is good 
for the set {π_1,…, π_ j}.
We show that A^π is Robinson. 
Consider integers i and l such that 1≤ i < l ≤ n. 
Consider now any integer j in [i,l]. 
Since the element π_j is good for the set {π_1,π_2,…,π_j-1}, 
the first condition of Definition <ref> implies that 
if A^π_ij≠ * and A^π_il≠ *, then 
A^π_ij≥ A^π_il. Equivalently, 
since the element π_k is good for the set {π_1,π_2,…,π_k-1},
if we consider an integer k∈ [i,l], the second condition of 
Definition <ref> implies that if 
A^π_kl≠ * and A^π_il≠ *, then 
A^π_kl≥ A^π_il. 
Therefore, for any 1≤ i < l ≤ n and j,k ∈ [i,l], we have that 
A^π_il≤min{A^π_ij,A^π_kl}. 
Hence, A^π is Robinson. 


Finally, to determine  if  an  incomplete similarity matrix A is Robinsonian we
use the algorithm presented in <cit.> which 
proceeds as follows: construct a directed graph
H=(S,F) where the vertex set S is formed by  all  subsets of 
{1,2,…, n},  and for every X,Y ⊆{1,2,…,n} there exists
an arc from X to Y if Y∖ X={i} and i is a good element for X.
The arc (X,Y) ∈ F is labeled by i.  Thus, the existence of an ordering 
π such that A^π is Robinson 
is equivalent to the existence of a directed path from a vertex that is a
singleton of {1,2,…, n} to the vertex {1,2…,n}. 
The existence of such directed path in H can be
determined in time O(n· 2^2n), using repeatedly the single source shortest path algorithm presented in <cit.> for all the n vertices representing a singleton.
Furthermore, the Robinson ordering π is determined by the ordering 
of the labels along that directed path.



§ FINAL REMARKS

Interestingly, in this work we show that the Seriation and the
SCFE problems are not the same. Nevertheless, there are cases in which 
they are equivalent. For instance, an exhaustive analysis shows that
if a weighted graph has at most four vertices then its 
similarity matrix is Robinsonian if and only if it has a valid
drawing in ℝ. Whereas, in the proof of 
Lemma <ref>, we present a weighted graph
with five vertices where seriation is not sufficient. 

The Seriation and the SCFE problems are also equivalent if the
number of different weights is not too big. Indeed,
Theorem <ref> states that when the weight function can take only two values, seriation and the SCFE problem are equivalent.
Nevertheless, in the proof of 
Lemma <ref>, we exhibit an example of a weighted
graph  with five different weights where seriation is not 
enough. This final remark rises an interesting question, when this 
separation between the Seriation and the SCFE problems occurs?. Is the 
Seriation problem  
equivalent to the SCFE problem when the graph has four different 
weights?.

On the other hand, in Theorem <ref> we have established 
that, when the weighted graph is complete, if one Robinson ordering 
has a valid distance drawing, then all Robinson orderings have one. 
Such a result is crucial to show that the SCFE problem has a polynomial 
time algorithm when the input is a complete weighted graph.
To prove this Theorem, we use the fact that there is a PQ-tree that 
encodes all Robinson orderings for a complete weighted graph. 
We do not have a result like 
that  for incomplete weighted graphs. Hence, it is not clear 
the existence of a result for incomplete weighted graphs equivalent to
Theorem <ref>. We believe that this is a really interesting 
problem that remains open. Indeed, is it possible to encode all Robinson
Orderings for an incomplete weighted graph in a PQ-tree?.





10

becerra2018trees
R. Becerra and C. Thraves Caro, On the sitting closer to friends
  than enemies problem in trees and an intersection model for strongly chordal
  graphs, arXiv preprint arXiv:1911.11494,  (2019).

benitez2018sitting
F. Benítez, J. Aracena, and C. Thraves Caro, The sitting closer
  to friends than enemies problem in the circumference, arXiv preprint
  arXiv:1811.02699,  (2018).

booth1976testing
K. S. Booth and G. S. Lueker, Testing for the consecutive ones
  property, interval graphs, and graph planarity using pq-tree algorithms,
  Journal of computer and system sciences, 13 (1976), pp. 335–379.

brusco2006branch
M. J. Brusco and S. Stahl, Branch-and-Bound applications in
  combinatorial data analysis, Springer Science & Business Media, 2006.

chepoi1997recognition
V. Chepoi and B. Fichet, Recognition of Robinsonian
  dissimilarities, Journal of Classification, 14 (1997), pp. 311–325.

chepoi2009seriation
V. Chepoi, B. Fichet, and M. Seston, Seriation in the presence of
  errors: NP-hardness of l_∞-fitting Robinson structures to
  dissimilarity matrices, Journal of classification, 26 (2009), pp. 279–296.

chepoi2011seriation
V. Chepoi and M. Seston, Seriation in the presence of errors: A
  factor 16 approximation algorithm for l_∞-fitting Robinson
  structures to distances, Algorithmica, 59 (2011), pp. 521–568.

cygan2015sitting
M. Cygan, M. Pilipczuk, M. Pilipczuk, and J. O. Wojtaszczyk, Sitting
  closer to friends than enemies, revisited, Theory of Computing Systems, 56
  (2015), pp. 394–405.

ding2004linearized
C. Ding and X. He, Linearized cluster assignment via spectral
  ordering, in Proceedings of the twenty-first international conference on
  Machine learning, ACM, 2004, p. 30.

fortin2017robinsonian
D. Fortin, Robinsonian matrices: Recognition challenges, Journal
  of Classification, 34 (2017), pp. 191–222.

hubert2001combinatorial
L. Hubert, P. Arabie, and J. Meulman, Combinatorial data analysis:
  Optimization by dynamic programming, vol. 6, SIAM, 2001.

kermarrec2011can
A.-M. Kermarrec and C. Thraves Caro, Can everybody sit closer to
  their friends than their enemies?, in Proceedings of the 36th International
  Symposium on Mathematical Foundations of Computer Science, Springer, 2011,
  pp. 388–399.

laurent2017lex
M. Laurent and M. Seminaroti, A Lex-BFS-based recognition
  algorithm for Robinsonian matrices, Discrete Applied Mathematics, 222
  (2017), pp. 151–165.

laurent2017similarity
M. Laurent and M. Seminaroti, Similarity-first search: A new
  algorithm with application to Robinsonian matrix recognition, SIAM Journal
  on Discrete Mathematics, 31 (2017), pp. 1765–1800.

laurent2017structural
M. Laurent, M. Seminaroti, and S.-i. Tanigawa, A structural
  characterization for certifying Robinsonian matrices, The Electronic
  Journal of Combinatorics, 24(2) (2017).

liiv2010seriation
I. Liiv, Seriation and matrix reordering methods: An historical
  overview, Statistical Analysis and Data Mining: The ASA Data Science
  Journal, 3 (2010), pp. 70–91.

graphsandgenes84
B. G. Mirkin and S. N. Rodin, Graphs and Genes, Springer-Verlag,
  1984.

pardo2015embedding
E. G. Pardo, M. Soto, and C. Thraves Caro, Embedding signed graphs
  in the line, Journal of Combinatorial Optimization, 29 (2015), pp. 451–471.

petrie1899sequences
W. M. F. Petrie, Sequences in prehistoric remains, Journal of the
  Anthropological Institute of Great Britain and Ireland,  (1899),
  pp. 295–301.

prea2014optimal
P. Préa and D. Fortin, An optimal algorithm to recognize
  Robinsonian dissimilarities, Journal of Classification, 31 (2014),
  pp. 351–385.

roberts69
F. S. Roberts, Indifference graphs, in Proof Techniques in Graph
  Theory, F. Harary, ed., Academic Press, New York, 1969, pp. 139–146.

robinson_1951
W. S. Robinson, A method for chronologically ordering archaeological
  deposits, American Antiquity, 16 (1951), pp. 293 – 301.

spaen2017rk
Q. Spaen, C. Thraves Caro, and M. Velednitsky, The dimension of
  valid distance drawings of signed graphs, Discrete & Computational
  Geometry, 63 (2020), pp. 158–168.

THORUP2004330
M. Thorup, Integer priority queues with decrease key in constant
  time and the single source shortest paths problem, Journal of Computer and
  System Sciences, 69 (2004), pp. 330 – 353.

tien2008methods
Y.-J. Tien, Y.-S. Lee, H.-M. Wu, and C.-H. Chen, Methods for
  simultaneously identifying coherent local clusters with smooth global
  patterns in gene expression profiles, BMC bioinformatics, 9 (2008), p. 155.




