---
abstract: 'Given a directed graph $D=(V,A)$ we define its intersection graph $I(D)=(A,E)$ to be the graph having $A$ as a node-set and two nodes of $I(D)$ are adjacent if their corresponding arcs share a common node that is the tail of at least one of these arcs. We call these graphs facility location graphs since they arise from the classical uncapacitated facility location problem. In this paper we show that facility location graphs are hard to recognize and they are easy to recognize when the underlying graph is triangle-free. We also determine the complexity of the vertex coloring, the stable set and the facility location problems on that class.'
author:
- Mourad Baïou
- Laurent Beaudou
- Zhentao Li
- Vincent Limouzy
bibliography:
- 'paper-FLG.bib'
title: On a class of intersection graphs
---

Introduction
============

In this paper we study the following class of intersection graphs. Given a directed graph $D=(V,A)$, we denote by $I(D)=(A,E)$ the [*intersection graph of $D$*]{} defined as follows:

-   the node-set of $I(D)$ is the arc-set of $D$,

-   two nodes $a=(u,v)$ and $b=(w,t)$ of $I(D)$ are adjacent if one of the following holds: $u=w$ or $v=w$ or $t=u$ or $(u,v)=(t,w)$ (see Figure \[adjac\]).

\(a) at (0,0); (b) at ($ (a) + (2,0) $); (d) at ($ (a) + (6,0) $); (e) at ($ (d) + (0,-1) $); (c) at ($ (d) + (0,1) $); (g) at ($ (d) + (2,0) $); (h) at ($ (g) + (0,-1) $); (f) at ($ (g) + (0,1) $); (i) at ($ (g) + (3,.5) $); (j) at ($ (i) + (-.75,-1) $); (k) at ($ (i) + (.75,-1) $); (l) at ($ (i) + (2,.5) $); (m) at ($ (l) + (0,-2) $); (n) at ($ (c) + (1,1) $); (o) at ($ (i) + (0,1.5) $); (p) at ($ (l) + (0,1) $); (q) at ($ (a) + (1,-3) $); (r) at ($ (i) + (0,-3.5) $); (a1) at ($ (a) + (2,0.5) $); (b1) at ($ (a1) + (-.75,-1) $); (c1) at ($ (a1) + (+.75,-1) $); (l1) at ($ (g) + (6,0) $); (m1) at ($ (l1) + (-2,0) $);

(a1) circle (1.5pt); (b1) circle (1.5pt); (c1) circle (1.5pt);

\(c) circle (1.5pt); (d) circle (1.5pt); (e) circle (1.5pt); (f) circle (1.5pt); (g) circle (1.5pt); (h) circle (1.5pt); (l) circle (1.5pt); (m) circle (1.5pt);

\(e) – (d) node\[midway, left\] [$a$]{}; (d) – (c) node\[midway, left\] [$b$]{};

\(f) – (g) node\[midway, left\] [$b$]{}; (g) – (h) node\[midway, left\] [$a$]{};

(a1) – (b1) node\[midway, left\] [$a$]{}; (a1) – (c1) node\[midway, right\] [$b$]{};

\(l) to\[bend right\] (m); (l1) node\[left\] [$a$]{}; (m1) node\[right\] [$b$]{}; (m) to\[bend right\] (l) ;

We focus on two aspects: the recognition of these intersection graphs and some combinatorial optimization problem in this class. De Simone and Mannino [@Simone] considered the recognition problem and provided a characterization of these graphs based on the structure of the (directed) neighborhood of a vertex. Unfortunately this characterization does not yield a polynomial time recognition algorithm. Intersection graphs we consider arise from the [*uncapacitated facility location problem*]{} (UFLP) defined as follows. We are given a directed graph $D=(V,A)$, costs $f(v)$ of opening a facility at node $v$ and cost $c(u,v)$ of assigning $v$ to $u$ (for each $(u,v) \in A$). We wish to select a subset of facilities to open and an assignment of each remaining nodes to a selected facility so as to minimize the cost of opening the selected facilities plus the cost of arcs used for assignment.

This problem can be formulated as a linear integer program as follows.

$$\mbox{min } \sum_{(u,v)\in A}c(u,v)x(u,v)+\sum_{v\in V}f(v)y(v)$$

$$\left\{ \begin{aligned}
\sum_{(u,v)\in A}x(u,v) + y(u) = 1 \quad & \forall u\in V,\\
x(u,v)\leq y(v) \quad & \forall (u,v)\in A,\\
x(u,v)\geq 0 \quad & \forall (u,v)\in A, \\
y(v)\geq 0 \quad & \forall v\in V,\\
x(u,v)\in \{0,1\} \quad & \forall (u,v)\in A,\\
y(v)\in \{0,1\} \quad & \forall v\in V.
\end{aligned} \right.$$

If we remove the variables $y(v)$ for all $v$ from the formulation above, we get

$$\mbox{min } \sum_{(u,v)\in A}(c(u,v)-f(u))x(u,v)+\sum_{v\in V}f(v)$$

$$\left\{ \begin{aligned}
\sum_{(u,v)\in A}x(u,v)  \leq 1 \quad  & \forall u\in V,\\
x(u,v)+\sum_{(v,w)\in A}x(v,w)  \leq 1 \quad & \forall (u,v)\in A,\\
x(u,v)\geq 0 \quad & \forall (u,v)\in A,\\
x(u,v)\in \{0,1\} \quad & \forall (u,v)\in A.
\end{aligned} \right.$$

This is exactly the maximal clique formulation of the [*maximum stable set problem*]{} associated with $I(D)$, where the weight of each node $(u,v)$ of $I(D)$ is $f(u)-c(u,v)$. This correspondence is well known in the literature (see in [@AVS; @CorTh; @Simone]). We may consider several combinatorial optimization problems on directed graph that may be reduce to the maximum stable set problem on an undirected graph. For example in [@Chv-Eben], Chvátal and Ebenegger reduce the max cut problem in a directed graph $D=(V,A)$ to the maximum stable set problem in the following intersection graph called the [ *line graph of a directed graph*]{}: we assign a node to each arc $a\in
A$ and two nodes are adjacent if the head of one (corresponding) arc is the tail of the other. They prove that recognizing such graphs is <span style="font-variant:small-caps;">np</span>-complete. Balas [@Balas] considered the asymmetric assignment problem. He defined an intersection graph of a directed graph $D$ where nodes are arcs of $D$ and two nodes are adjacent if the two corresponding arcs have the same tail, the same head or the same extremities without being parallel. Balas uses this correspondence to develop new facets for the asymmetric assignment polytope.

We may generalize the notion of line graphs to directed graphs in many ways. The simplest involves deciding

1.  if arcs that share a head are adjacent,

2.  if arcs that share a tail are adjacent, and

3.  if two arcs are adjacent if the head of one arc is the tail of the other.

It is not too difficult to show the recognition problem is easy if we choose non-adjacency for (3).

Choosing non-adjacency for (3) means that we could separate all vertices $v$ of a digraph $D$ into two vertices (one for all arcs entering that vertex and one for all arcs leaving it) and the line graph of the resulting digraph $D'$ is the same as the line graph of $D$. Furthermore, the line graph of $D'$ is the line graph of its underlying digraph. So all classes obtained by choosing non-adjacency for (3) are easy to recognize as it simply involves recognizing if a line graph is bipartite [@beineke_1970] (where some sides of the bipartition are possibly forced to have degree 1 from out choice of (1) and (2)).

So suppose arcs of type (3) are adjacent. Choosing adjacency for (1) and (2) gives the line graphs of the underlying undirected graph, and these are easy to recognize [@beineke_1970]. Choosing non-adjacency for both (1) and (2) leads to the line graphs defined by Chvátal and Ebenegger and it is <span style="font-variant:small-caps;">np</span>-complete to recognize them [@Chv-Eben]. And picking exactly one of (1) and (2) to be adjacent and non-adjacency for the other leads to the same class of graphs (as we can simply reverse all arcs of a digraph before taking its line graph) and we wish to determine the complexity of recognizing this very last class.

Finally, note that since the stable set problem in our class is equivalent to the facility location problem, one may use all the material developed for facility location problem to solve the stable set problem in these graphs. It is well known that in practice the facility location problem may be solved efficiently via several approaches: polyhedra, approximation algorithms and heuristics.

This paper is organized as follows. Section \[def\] contains some basic definition and notations. Other definitions and notations will be given when needed. In section \[RLFG\], we show that facility location graphs are hard to recognize and in Section \[RTFLG\] we show that the subclass of triangle-free facility location graphs are recognizable in polynomial time. Section \[RP\] is devoted to some combinatorial optimization problem in facility location graphs. In particlular we show that the maximum stable set problem remains <span style="font-variant:small-caps;">np</span>-complete in triangle-free facility location graphs but the vertex coloring problem is solvable in polynomial time in this class. We also discuss the facility location problem and show it is <span style="font-variant:small-caps;">np</span>-complete in some restricted class of graphs. We provide concluding remarks in Section \[conc\].

Definitions and notations {#def}
=========================

Let $G$ be an undirected graph, we say that $G$ is a [*facility location*]{} (FL) graph if there exists a directed graph $D$ such that $G=I(D)$. Any FL graph will be denoted by $I(D)$, this notation helps to indicate the directed graph $D$ from which our FL graph may be obtained. Such a graph $D$ is called the [*preimage*]{} of $G$.

Let $D=(V,A)$ be a directed graph. Given an arc $a=(u,v)\in A$, the node $u$ is called the [*tail*]{} of $a$ and $v$ is called the [ *head*]{} of $a$. Sometimes we use the notation $t(a)$ (respectively $h(a)$) for the tail (respectively the head) of $a$. A [*sink*]{} is a node which is a tail of no arc in $A$. A [*branch*]{} in a directed graph is an arc $(u,v)$ where $v$ is a sink and is the head of only $(u,v)$.

A [*cycle*]{} $C$ in $D$ is a cycle in the underlying undirected graph of $D$. I.e., an ordered sequence of arcs $a_1, a_2,
\dots,a_p,a_{p+1}$, where $a_i$ and $a_{i+1}$ are incident, for $i=1,\dots,p$, with $a_{p+1}=a_1$. If $a_1$ and $a_p$ are not incident, then this sequence is called a [*path*]{}. We denote by $A(C)$ the arcs of $C$ and by $V(C)$ its nodes, that are the endnodes of the arcs in $A(C)$. The nodes of $V(C)$ may be partitioned into three sets (1) $\dot{C}$, the nodes that are the tail of two arcs in $A(C)$, (2) $\hat{C}$, the nodes that are the head of two arcs in $A(C)$ and (3) $\tilde{C}$, the nodes that are the tail of one arc and the head of the other arc in $A(C)$. When $\hat{C}$ (or $\dot{C}$) is empty, the cycle $C$ is the classical [*directed*]{} cycle. Similarly the nodes of a path $P$, except its extremities, may be partitioned into three sets $\dot{P}$, $\hat{P}$ and $\tilde{P}$. When $\hat{P}=\dot{P}=\emptyset$, $P$ is called a [*directed path*]{}. We define a cycle $C$ in an undirected graph as a sequence of ordered nodes, instead of ordered edges, this is useful when we study the correspondence between $I(D)$ and $D$. The nodes of $C$ are denoted by $A(C)$ and its edges by $E(C)$. A [*path*]{} is defined similarly.

Define $x_1,\dots,x_n$ to be $n$ Boolean variables. Define a [*literal*]{} $\lambda_i$ be either a Boolean variable $x_i$ or its negation $\bar{x_i}$. A [*clause*]{} $C$, is a disjunction of literals $\lambda_i$, that is $C=\lambda_{i_1}\vee\dots\vee\lambda_{i_k}$. $F=C_1\wedge\dots\wedge C_m$ is a conjunction of $m$ clauses. In the [*satisfiablity problem*]{} <span style="font-variant:small-caps;">sat</span>, we want to decide if there exists values $x_i$ such that an input conjunction of disjunctions (of literals) $F$ evaluates to [*true*]{}. If such values exist, we say $F$ is [*satisfiable*]{}. If each clause is a disjunction of at most three literals then the problem is called 3-satisfiability. The problem 3-<span style="font-variant:small-caps;">sat</span> has been shown <span style="font-variant:small-caps;">np</span>-complete by Karp [@karp].

An undirected graph $G$ is triangle-free if it does not contain a clique of size 3. A [*wheel*]{} $W_n$ is a graph obtained from a cycle $C_n$by adding a vertex adjacent to all vertices of the cycle.

Recognizing facility location graphs is <span style="font-variant:small-caps;">np</span>-complete {#RLFG}
=================================================================================================

The main result of this section is the following:

\[NP-complete\] Recognizing facility location graphs is <span style="font-variant:small-caps;">np</span>-complete.

The proof of this theorem is given in subsection \[proof-NP-complete\]. We first give a sketch of this proof and some useful lemmas before providing the detailed proof.

Proof sketch
------------

We will reduce the problem 3-<span style="font-variant:small-caps;">sat</span> to the recognition of FL graphs. We assume we are given an instance of the problem 3-<span style="font-variant:small-caps;">sat</span>. That is, we have $n$ Boolean variables $x_1,\dots,x_n$ and a Boolean formula $F=C_1\wedge\dots\wedge C_m$, where each clause $C_j=\lambda_{j_1}\vee\lambda_{j_2}\vee\lambda_{j_3}$, for $j=1\dots,m$. From $F$ we construct an undirected graph $G_F$ and we show that $F$ is satisfiable if and only if $G_F$ is a facility location graph.

We build $G_F$ using gadgets for variables and clauses. Values for variables are stored, replicated and negated through the “branches” of the variable gadgets. These branches are then connected to the clauses gadgets of clauses that contain these variables (and their negation).

More precisely, the construction of $G_F$ follows three steps: (1) for each variable $x_i$, we construct a graph called $\textsc{Gad}^1_i$ (<span style="font-variant:small-caps;">Gad</span> stands for gadget), (2) for each clause $C_j$, another gadget called $\textsc{Gad}^2_j$ is constructed and (3) we connect the graphs $\textsc{Gad}^1_i$ and $\textsc{Gad}^2_j$ to produce $G_F$. Each graph $\textsc{Gad}^1_i$ contains $2m$ branches where each branch express the fact that the variable $x_i$ (or $\bar{x}_i$) is present in the clause $C_j$, $j=1,\dots,m$. Each graph $\textsc{Gad}^2_j$ contains exactly three branches where each branch expresses the litterals of this clause $\lambda_{j_1}$, $\lambda_{j_2}$ and $\lambda_{j_3}$.

The three following subsections are devoted to the construction of the graphs $\textsc{Gad}^1_i$, $\textsc{Gad}^2_j$ and $G_F$.

The construction of the graphs $\textsc{Gad}^1_i$
-------------------------------------------------

\[wheel-obs\] There are 15 directed graphs whose intersection graph is the wheel $W_5$. We list 5 of them that will be useful for our reduction. From these graphs, we obtain all the remaining directed graphs by identifying the head of the pending arc with the tail of one of the arcs entering this pending arc.

\(a) at (-2,1.5); (b) at ($ (a) + (126:1.5) $); (c) at ($ (a) + (-162:1.5) $); (d) at ($ (a) + (-90:1.5) $); (e) at ($ (a) + (-18:1.5) $); (f) at ($ (a) + (54:1.5) $);

\(b) – (c) – (d) – (e) – (f) – (b); (a) – (b); (a) – (c); (a) – (d); (a) – (e); (a) – (f);

\(a) circle (1.5pt); (b) circle (1.5pt); (c) circle (1.5pt); (d) circle (1.5pt); (e) circle (1.5pt); (f) circle (1.5pt);

\(a) node\[above\] [$a$]{}; (b) node\[left\] [$b$]{}; (c) node\[left\] [$c$]{}; (d) node\[below\] [$d$]{}; (e) node\[right\] [$e$]{}; (f) node\[right\] [$f$]{};

\(x) at (3,2.25); (y) at (2,3); (z) at (1,2.25); (t) at (2,1.5); (u) at (2,0); (v) at (2,-0.5);

\(y) – (z) node\[midway,above left\][$d$]{}; (y) – (x) node\[midway,above right\][$c$]{}; (z) – (t) node\[midway,below left\][$e$]{}; (x) – (t) node\[midway,below right\][$b$]{}; (t) – (y) node\[midway,right\][$a$]{}; (t) – (u) node\[midway,right\][$f$]{}; (v) node\[below\] [$I_5$]{};

\(x) circle (1.5pt); (y) circle (1.5pt); (z) circle (1.5pt); (t) circle (1.5pt); (u) circle (1.5pt);

\(x) at (0,2.25); (y) at (-1,3); (z) at (-2,2.25); (t) at (-1,1.5); (u) at (-1,0); (v) at (-1,-0.5);

\(y) – (z) node\[midway,above left\][$c$]{}; (y) – (x) node\[midway,above right\][$b$]{}; (z) – (t) node\[midway,below left\][$d$]{}; (x) – (t) node\[midway,below right\][$f$]{}; (t) – (y) node\[midway,right\][$a$]{}; (t) – (u) node\[midway,right\][$e$]{}; (v) node\[below\] [$I_4$]{};

\(x) circle (1.5pt); (y) circle (1.5pt); (z) circle (1.5pt); (t) circle (1.5pt); (u) circle (1.5pt);

\(x) at (-3,2.25); (y) at (-4,3); (z) at (-5,2.25); (t) at (-4,1.5); (u) at (-4,0); (v) at (-4,-0.5);

\(y) – (z) node\[midway,above left\][$b$]{}; (y) – (x) node\[midway,above right\][$f$]{}; (z) – (t) node\[midway,below left\][$c$]{}; (x) – (t) node\[midway,below right\][$e$]{}; (t) – (y) node\[midway,right\][$a$]{}; (t) – (u) node\[midway,right\][$d$]{}; (v) node\[below\] [$I_3$]{};

\(x) circle (1.5pt); (y) circle (1.5pt); (z) circle (1.5pt); (t) circle (1.5pt); (u) circle (1.5pt);

\(x) at (-6,2.25); (y) at (-7,3); (z) at (-8,2.25); (t) at (-7,1.5); (u) at (-7,0); (v) at (-7,-0.5);

\(y) – (z) node\[midway,above left\][$f$]{}; (y) – (x) node\[midway,above right\][$e$]{}; (z) – (t) node\[midway,below left\][$b$]{}; (x) – (t) node\[midway,below right\][$d$]{}; (t) – (y) node\[midway,right\][$a$]{}; (t) – (u) node\[midway,right\][$c$]{}; (v) node\[below\] [$I_2$]{};

\(x) circle (1.5pt); (y) circle (1.5pt); (z) circle (1.5pt); (t) circle (1.5pt); (u) circle (1.5pt);

\(x) at (-9,2.25); (y) at (-10,3); (z) at (-11,2.25); (t) at (-10,1.5); (u) at (-10,0); (v) at (-10,-0.5);

\(y) – (z) node\[midway,above left\][$e$]{}; (y) – (x) node\[midway,above right\][$d$]{}; (z) – (t) node\[midway,below left\][$f$]{}; (x) – (t) node\[midway,below right\][$c$]{}; (t) – (y) node\[midway,right\][$a$]{}; (t) – (u) node\[midway,right\][$b$]{}; (v) node\[below\] [$I_1$]{};

\(x) circle (1.5pt); (y) circle (1.5pt); (z) circle (1.5pt); (t) circle (1.5pt); (u) circle (1.5pt);

Consider the two undirected graphs $I$ and $I'$ of Figure \[fig:demi\_inv\]. These two graphs are isomorphic, they are obtained from the wheel $W_5$ by adding four nodes. This restricts the number of possible preimage for the wheel to only 2. When we join the nodes $j$ and $j'$ we obtain the desired graph called <span style="font-variant:small-caps;">Inv</span> which is again the intersection graph of exactly two directed graphs. The graph <span style="font-variant:small-caps;">Inv</span> will be useful for the construction of $\textsc{Gad}^2_j$.

\(a) at (-2,1.5); (b) at ($ (a) + (126:1.5) $); (c) at ($ (a) + (-162:1.5) $); (d) at ($ (a) + (-90:1.5) $); (e) at ($ (a) + (-18:1.5) $); (f) at ($ (a) + (54:1.5) $); (g) at ($ (b) + (90:1.5) $); (h) at ($ (f) + (90:1.5) $); (i) at ($ (d) + (-2,0) $); (j) at ($ (d) + (2,0) $); (x) at ($(d) + (0,-1)$);

\(b) – (c) – (d) – (e) – (f) – (b); (c) – (i) – (d) – (c); (d) – (j) – (e) – (d); (a) – (b); (a) – (c); (a) – (d); (a) – (e); (a) – (f); (b) – (g); (f) – (h); (x) node\[below\] [$I$]{};

\(a) circle (1.5pt); (b) circle (1.5pt); (c) circle (1.5pt); (d) circle (1.5pt); (e) circle (1.5pt); (f) circle (1.5pt); (g) circle (1.5pt); (h) circle (1.5pt); (i) circle (1.5pt); (j) circle (1.5pt);

\(a) node\[above\] [$a$]{}; (b) node\[left\] [$b$]{}; (c) node\[left\] [$c$]{}; (d) node\[below\] [$d$]{}; (e) node\[right\] [$e$]{}; (f) node\[right\] [$f$]{}; (g) node\[above\] [$g$]{}; (h) node\[above\] [$h$]{}; (i) node\[left\] [$i$]{}; (j) node\[right\] [$j$]{};

\(a) at (4,1.5); (b) at ($ (a) + (126:1.5) $); (c) at ($ (a) + (-162:1.5) $); (d) at ($ (a) + (-90:1.5) $); (e) at ($ (a) + (-18:1.5) $); (f) at ($ (a) + (54:1.5) $); (g) at ($ (b) + (90:1.5) $); (h) at ($ (f) + (90:1.5) $); (i) at ($ (d) + (-2,0) $); (j) at ($ (d) + (2,0) $); (x) at ($(d) + (0,-1)$);

\(b) – (c) – (d) – (e) – (f) – (b); (c) – (i) – (d) – (c); (d) – (j) – (e) – (d); (a) – (b); (a) – (c); (a) – (d); (a) – (e); (a) – (f); (b) – (g); (f) – (h); (x) node\[below\] [$I'$]{};

\(a) circle (1.5pt); (b) circle (1.5pt); (c) circle (1.5pt); (d) circle (1.5pt); (e) circle (1.5pt); (f) circle (1.5pt); (g) circle (1.5pt); (h) circle (1.5pt); (i) circle (1.5pt); (j) circle (1.5pt);

\(a) node\[above\] [$a'$]{}; (b) node\[left\] [$b'$]{}; (c) node\[left\] [$c'$]{}; (d) node\[below\] [$d'$]{}; (e) node\[right\] [$e'$]{}; (f) node\[right\] [$f'$]{}; (g) node\[above\] [$g'$]{}; (h) node\[above\] [$h'$]{}; (i) node\[left\] [$j'$]{}; (j) node\[right\] [$i'$]{};

Recall that $W_5$ may be the intersection of 15 directed graphs as described by Remark \[wheel-obs\]. Let us discuss the possible directed graphs having $I$ as their intersection graph. The subgraph of $I$ induced by the nodes $a,b,c,d,e,f$ is a wheel $W_5$ and thus is the intersection of 15 directed graphs obtained from those of Figure \[fig:w5isflg\] as described by Remark \[wheel-obs\]. In $I$ there are two pendent nodes $g$ and $h$ adjacent to two neighbors $b$ and $f$ in $I$. This implies that the adjacency between $b$ and $f$ cannot be of the form as represented in the graphs $I_2$, $I_3$ and $I_4$ of Figure \[fig:w5isflg\]. Hence we have only two possible directed graphs $I_1$ or $I_5$, since in neither of these two graphs we may identify the head of the pending arc with the tail of one of the arcs entering this pending arc. Moreover, there is one way of adding the arcs $i$ and $j$ in each case. Consequently there are only two graphs $D_1$ and $D_2$ such that $I(D_1)=I(D_2)=I$. These graphs are represented in Figure \[fig:demi\_inv1\]. It is obvious that there are also two directed graphs whose intersection graph is $I'$. For convenience these two graphs will be shown in Figure \[fig:demi\_inv2\].

\(x) at (4,2.25); (y) at (3,3); (z) at (2,2.25); (t) at (3,1.5); (u) at (3,0); (v) at (3,-1.5); (p) at (3,4.5); (q) at (0.5,2.25); (w) at (5.5,2.25); (k) at (2,-1);

\(y) – (z) node\[midway,left, above\][$e$]{}; (y) – (x) node\[midway,right, above\][$d$]{}; (z) – (t) node\[midway,left, below\][$f$]{}; (x) – (t) node\[midway,right, below\][$c$]{}; (t) – (y) node\[midway,right\][$a$]{}; (t) – (u) node\[midway,right\][$b$]{}; (p) – (y) node\[midway,right\][$j$]{}; (x) – (w) node\[midway, below\][$i$]{}; (q) – (z) node\[midway,above\][$h$]{}; (u) – (v) node\[midway,right\][$g$]{}; (k) node\[below\] [$D_1$]{};

\(x) circle (1.5pt); (y) circle (1.5pt); (z) circle (1.5pt); (t) circle (1.5pt); (u) circle (1.5pt); (p) circle (1.5pt); (q) circle (1.5pt); (v) circle (1.5pt); (w) circle (1.5pt);

\(x) at (10,2.25); (y) at (9,3); (z) at (8,2.25); (t) at (9,1.5); (u) at (9,0); (v) at (9,-1.5); (p) at (9,4.5); (q) at (6.5,2.25); (w) at (11.5,2.25); (k) at (8,-1);

\(y) – (z) node\[midway,left, above\][$d$]{}; (y) – (x) node\[midway,right, above\][$c$]{}; (z) – (t) node\[midway,left, below\][$e$]{}; (x) – (t) node\[midway,right, below\][$b$]{}; (t) – (y) node\[midway,right\][$a$]{}; (t) – (u) node\[midway,right\][$f$]{}; (p) – (y) node\[midway,right\][$i$]{}; (w) – (x) node\[midway, below\][$g$]{}; (z) – (q) node\[midway,above\][$j$]{}; (u) – (v) node\[midway,right\][$h$]{}; (k) node\[below\] [$D_2$]{};

\(x) circle (1.5pt); (y) circle (1.5pt); (z) circle (1.5pt); (t) circle (1.5pt); (u) circle (1.5pt); (p) circle (1.5pt); (q) circle (1.5pt); (v) circle (1.5pt); (w) circle (1.5pt);

\(x) at (4,2.25); (y) at (3,3); (z) at (2,2.25); (t) at (3,1.5); (u) at (3,0); (v) at (3,-1.5); (p) at (3,4.5); (q) at (0.5,2.25); (w) at (5.5,2.25); (k) at (2,-1);

\(y) – (z) node\[midway,left, above\][$e'$]{}; (y) – (x) node\[midway,right, above\][$d'$]{}; (z) – (t) node\[midway,left, below\][$f'$]{}; (x) – (t) node\[midway,right, below\][$c'$]{}; (t) – (y) node\[midway,right\][$a'$]{}; (t) – (u) node\[midway,right\][$b'$]{}; (p) – (y) node\[midway,right\][$i'$]{}; (x) – (w) node\[midway, below\][$j'$]{}; (q) – (z) node\[midway,above\][$h'$]{}; (u) – (v) node\[midway,right\][$g'$]{}; (k) node\[below\] [$D'_1$]{};

\(x) circle (1.5pt); (y) circle (1.5pt); (z) circle (1.5pt); (t) circle (1.5pt); (u) circle (1.5pt); (p) circle (1.5pt); (q) circle (1.5pt); (v) circle (1.5pt); (w) circle (1.5pt);

\(x) at (10,2.25); (y) at (9,3); (z) at (8,2.25); (t) at (9,1.5); (u) at (9,0); (v) at (9,-1.5); (p) at (9,4.5); (q) at (6.5,2.25); (w) at (11.5,2.25); (k) at (8,-1);

\(y) – (z) node\[midway,left, above\][$d'$]{}; (y) – (x) node\[midway,right, above\][$c'$]{}; (z) – (t) node\[midway,left, below\][$e'$]{}; (x) – (t) node\[midway,right, below\][$b'$]{}; (t) – (y) node\[midway,right\][$a'$]{}; (t) – (u) node\[midway,right\][$f'$]{}; (p) – (y) node\[midway,right\][$j'$]{}; (w) – (x) node\[midway, below\][$g'$]{}; (z) – (q) node\[midway,above\][$i'$]{}; (u) – (v) node\[midway,right\][$h'$]{}; (k) node\[below\] [$D'_2$]{};

\(x) circle (1.5pt); (y) circle (1.5pt); (z) circle (1.5pt); (t) circle (1.5pt); (u) circle (1.5pt); (p) circle (1.5pt); (q) circle (1.5pt); (v) circle (1.5pt); (w) circle (1.5pt);

Let us call <span style="font-variant:small-caps;">Inv</span> (<span style="font-variant:small-caps;">Inv</span> stands for inverter) the graph obtained from $I$ and $I'$ by identifying the nodes $j$ and $j'$. We use $j$ for the name of the resulting node, see Figure \[fig:inv\].

\(a) at (-2,1.5); (b) at ($ (a) + (126:1.5) $); (c) at ($ (a) + (-162:1.5) $); (d) at ($ (a) + (-90:1.5) $); (e) at ($ (a) + (-18:1.5) $); (f) at ($ (a) + (54:1.5) $); (g) at ($ (b) + (90:1.5) $); (h) at ($ (f) + (90:1.5) $); (i) at ($ (d) + (-2,0) $); (j) at ($ (d) + (2,0) $); (a’) at (2,1.5); (b’) at ($ (a') + (126:1.5) $); (c’) at ($ (a') + (-162:1.5) $); (d’) at ($ (a') + (-90:1.5) $); (e’) at ($ (a') + (-18:1.5) $); (f’) at ($ (a') + (54:1.5) $); (g’) at ($ (b') + (90:1.5) $); (h’) at ($ (f') + (90:1.5) $); (i’) at ($ (d') + (2,0) $);

\(a) circle (1.5pt); (b) circle (1.5pt); (c) circle (1.5pt); (d) circle (1.5pt); (e) circle (1.5pt); (f) circle (1.5pt); (g) circle (1.5pt); (h) circle (1.5pt); (i) circle (1.5pt); (j) circle (1.5pt); (a’) circle (1.5pt); (b’) circle (1.5pt); (c’) circle (1.5pt); (d’) circle (1.5pt); (e’) circle (1.5pt); (f’) circle (1.5pt); (g’) circle (1.5pt); (h’) circle (1.5pt); (i’) circle (1.5pt);

\(b) – (c) – (d) – (e) – (f) – (b); (c) – (i) – (d) – (c); (d) – (j) – (e) – (d);

(b’) – (c’) – (d’) – (e’) – (f’) – (b’); (c’) – (j) – (d’) – (c’); (d’) – (i’) – (e’) – (d’);

\(a) – (b); (a) – (c); (a) – (d); (a) – (e); (a) – (f); (b) – (g); (f) – (h);

(a’) – (b’); (a’) – (c’); (a’) – (d’); (a’) – (e’); (a’) – (f’); (b’) – (g’); (f’) – (h’);

\(a) node\[above\] [$a$]{}; (b) node\[left\] [$b$]{}; (c) node\[left\] [$c$]{}; (d) node\[below\] [$d$]{}; (e) node\[right\] [$e$]{}; (f) node\[right\] [$f$]{}; (g) node\[above\] [$g$]{}; (h) node\[above\] [$h$]{}; (i) node\[left\] [$i$]{}; (j) node\[above\] [$j$]{}; (a’) node\[above\] [$a'$]{}; (b’) node\[left\] [$b'$]{}; (c’) node\[above left\] [$c'$]{}; (d’) node\[below\] [$d'$]{}; (e’) node\[right\] [$e'$]{}; (f’) node\[right\] [$f'$]{}; (g’) node\[above\] [$g'$]{}; (h’) node\[above\] [$h'$]{}; (i’) node\[right\] [$i'$]{};

(inv) at (8,2) [$~~~$]{}; (gg) at (6,2); (gg’) at (10,2); (gg) circle (1.5pt); (gg’) circle (1.5pt); (inv.east) circle (1.5pt); (inv.west) circle (1.5pt); (gg) node\[above\] [$g$]{}; (gg’) node\[above\] [$g'$]{}; (inv.east) node\[above right\] [$b'$]{}; (inv.west) node\[above left\] [$b$]{};

(gg) – (inv.west); (inv.east) – (gg’);

From the discussion above there are only two directed graphs that for convenience we call $\overleftrightarrow{\textsc{Inv}}$ and $\overline{\textsc{Inv}}$, such that $\textsc{Inv}=I(\overleftrightarrow{\textsc{Inv}})=I(\overline{\textsc{Inv}})$. The graph $\overleftrightarrow{\textsc{Inv}}$ (respectively $\overline{\textsc{Inv}}$) is obtained from $D_1$ and $D'_1$ (respectively $D_2$ and $D'_2$) by identifying $j$ and $j'$. Notice that the other possibilities of identifying $j$ and $j'$ will not lead to the graph $\textsc{Inv}$.

Now we are ready to build graphs $\textsc{Gad}^1_i$ that correspond to the variables $x_i$, for each $i$ in $\{1,\dots,n\}$. For each variable $x_i$ we construct $m$ copies of the graph $I$, where the nodes $a,\ldots,j$ of each copy are renamed, respectively, $a^i_1,\ldots,j^i_1$ up to $a^i_m,\ldots,j^i_m$. The graph $\textsc{Gad}^1_i$ is obtained by identifying the node $j^i_l$ with $i^i_{l+1}$ and we call $i^i_{l+1}$ the resulting node, for $l=1,\dots,m-1$. Also we rename the node $j^i_m$ by $i^i_{m+1}$, see Figure \[fig:gadget1\].

\(a) at (-2,1.5); (b) at ($ (a) + (126:1.5) $); (c) at ($ (a) + (-162:1.5) $); (d) at ($ (a) + (-90:1.5) $); (e) at ($ (a) + (-18:1.5) $); (f) at ($ (a) + (54:1.5) $); (g) at ($ (b) + (90:1.5) $); (h) at ($ (f) + (90:1.5) $); (i) at ($ (d) + (-2,0) $); (j) at ($ (d) + (2,0) $); (a’) at (2,1.5); (b’) at ($ (a') + (126:1.5) $); (c’) at ($ (a') + (-162:1.5) $); (d’) at ($ (a') + (-90:1.5) $); (e’) at ($ (a') + (-18:1.5) $); (f’) at ($ (a') + (54:1.5) $); (g’) at ($ (b') + (90:1.5) $); (h’) at ($ (f') + (90:1.5) $); (i’) at ($ (d') + (2,0) $); (am) at (10,1.5); (bm) at ($ (am) + (126:1.5) $); (cm) at ($ (am) + (-162:1.5) $); (dm) at ($ (am) + (-90:1.5) $); (em) at ($ (am) + (-18:1.5) $); (fm) at ($ (am) + (54:1.5) $); (gm) at ($ (bm) + (90:1.5) $); (hm) at ($ (fm) + (90:1.5) $); (im) at ($ (dm) + (-2,0) $); (im1) at ($ (dm) + (2,0) $);

\(a) circle (1.5pt); (b) circle (1.5pt); (c) circle (1.5pt); (d) circle (1.5pt); (e) circle (1.5pt); (f) circle (1.5pt); (g) circle (1.5pt); (h) circle (1.5pt); (i) circle (1.5pt); (j) circle (1.5pt); (a’) circle (1.5pt); (b’) circle (1.5pt); (c’) circle (1.5pt); (d’) circle (1.5pt); (e’) circle (1.5pt); (f’) circle (1.5pt); (g’) circle (1.5pt); (h’) circle (1.5pt); (i’) circle (1.5pt); (am) circle (1.5pt); (bm) circle (1.5pt); (cm) circle (1.5pt); (dm) circle (1.5pt); (em) circle (1.5pt); (fm) circle (1.5pt); (gm) circle (1.5pt); (hm) circle (1.5pt); (im) circle (1.5pt); (im1) circle (1.5pt);

\(b) – (c) – (d) – (e) – (f) – (b); (c) – (i) – (d) – (c); (d) – (j) – (e) – (d);

(b’) – (c’) – (d’) – (e’) – (f’) – (b’); (c’) – (j) – (d’) – (c’); (d’) – (i’) – (e’) – (d’);

(bm) – (cm) – (dm) – (em) – (fm) – (bm); (cm) – (im) – (dm) – (cm); (dm) – (im1) – (em) – (dm);

\(a) – (b); (a) – (c); (a) – (d); (a) – (e); (a) – (f); (b) – (g); (f) – (h);

(am) – (bm); (am) – (cm); (am) – (dm); (am) – (em); (am) – (fm); (bm) – (gm); (fm) – (hm);

(a’) – (b’); (a’) – (c’); (a’) – (d’); (a’) – (e’); (a’) – (f’); (b’) – (g’); (f’) – (h’);

(i’) – (im);

($ (a) + (25:0.4) $) node [$a_1^i$]{}; (b) node\[left\] [$b_1^i$]{}; (c) node\[left\] [$c_1^i$]{}; (d) node\[below\] [$d_1^i$]{}; (e) node\[right\] [$e_1^i$]{}; (f) node\[right\] [$f_1^i$]{}; (g) node\[above\] [$g_1^i$]{}; (h) node\[above\] [$h_1^i$]{}; (i) node\[left\] [$i_1^i$]{}; (j) node\[below\] [$i_2^i$]{}; ($ (a') + (25:0.4) $) node [$a_2^i$]{}; (b’) node\[left\] [$b_2^i$]{}; (c’) node\[above left\] [$c_2^i$]{}; (d’) node\[below\] [$d_2^i$]{}; (e’) node\[right\] [$e_2^i$]{}; (f’) node\[right\] [$f_2^i$]{}; (g’) node\[above\] [$g_2^i$]{}; (h’) node\[above\] [$h_2^i$]{}; (i’) node\[below\] [$i_3^i$]{}; ($ (am) + (20:0.5) $) node [$a_m^i$]{}; (bm) node\[left\] [$b_m^i$]{}; (cm) node\[above left\] [$c_m^i$]{}; (dm) node\[below\] [$d_m^i$]{}; (em) node\[right\] [$e_m^i$]{}; (fm) node\[right\] [$f_m^i$]{}; (gm) node\[above\] [$g_m^i$]{}; (hm) node\[above\] [$h_m^i$]{}; (im) node\[below\] [$i_m^i$]{}; (im1) node\[right\] [$i_{m+1}^i$]{};

The discussion above implies the following lemma, see Figures \[fig:inv\_depic1\] and \[fig:inv\_depic2\].

\[GAD1\] For each directed graph $D$ with $I(D)=\textsc{Gad}^1_i$ exactly one of the following two assumptions holds:

-   $h(b^i_j)=t(g^i_j)$ and $t(f^i_j)=h(h^i_j)$ for each $j=1,\dots,m$,

-   $t(b^i_j)=h(g^i_j)$ and $h(f^i_j)=t(h^i_j)$ for each $j=1,\dots,m$.

The construction of the graphs $\textsc{Gad}^2_j$
-------------------------------------------------

We will use the graph $\textsc{Inv}$ of the previous subsection to construct $\textsc{Gad}^2_j$. We have three triangles $\Delta_1=\{r_j,a_j,f_j\}$, $\Delta_2=\{s_j,b_j,c_j\}$ and $\Delta_3=\{t_j,e_j,d_j\}$ with the addition of a branch pending from each node of these triangles, that is we add the edges $r_jr'_j$, $a_jf'_j$; $s_js'_j$, $b_jb'_j$; $t_jt'_j$, $e_je'_j$, $d_jd'_j$. These triangles are connected using their branches. We choose one triangle say $\Delta_1$ and we connect it to $\Delta_2$ and $\Delta_3$ via two graphs identical to $\textsc{Inv}$ using two of its branches $a_ja'_j$ and $f_jf'_j$. The triangles $\Delta_2$ and $\Delta_3$ are connected by identifying the branches $c_jc'_j$ and $d_jd'_j$ (the nodes $c'_j$ and $d'_j$ are removed), see Figure \[fig:gadget2\].

(r’) at (0,0); (r) at ($ (r') + (0,-2) $); (a) at ($ (r) + (-120:2) $); (f) at ($ (r) + (-60:2) $); (g) at ($ (a) + (-120:3) $) [$~~~$]{}; (h) at ($ (f) + (-60:3) $) [$~~~$]{}; (b) at ($ (a) + (-120:6) $); (e) at ($ (f) + (-60:6) $); (s) at ($ (b) + (-120:2) $); (c) at ($ (b) + (-60:2) $); (d) at ($ (e) + (-120:2) $); (t) at ($ (e) + (-60:2) $); (s’) at ($ (s) + (-120:2) $); (t’) at ($ (t) + (-60:2) $);

(cen) at (12,-7); (n) at ($ (cen) + (90:2) $); (sw) at ($ (cen) + (-150:2) $); (se) at ($ (cen) + (-30:2) $); (n’) at ($ (cen) + (90:4) $); (sw’) at ($ (cen) + (-150:4) $); (se’) at ($ (cen) + (-30:4) $);

\(r) – (r’); (t) – (t’); (s) – (s’); (r) – (a) – (f) – (r); (s) – (b) – (c) – (s); (t) – (d) – (e) – (t); (d) – (c); (g.east) – (a); (g.west) – (b); (h.east) – (e); (h.west) – (f);

\(a) circle (1.5pt); (b) circle (1.5pt); (c) circle (1.5pt); (d) circle (1.5pt); (e) circle (1.5pt); (f) circle (1.5pt); (r) circle (1.5pt); (r’) circle (1.5pt); (s) circle (1.5pt); (s’) circle (1.5pt); (t) circle (1.5pt); (t’) circle (1.5pt); (g.east) circle (1.5pt); (h.east) circle (1.5pt); (g.west) circle (1.5pt); (h.west) circle (1.5pt);

(g.east) node\[above\] [$a'$]{}; (g.west) node\[left\] [$b'$]{}; (h.east) node\[right\] [$e'$]{}; (h.west) node\[above\] [$f'$]{}; (a) node\[above left\] [$a$]{}; (b) node\[above left\] [$b$]{}; (c) node\[above right\] [$c$]{}; (d) node\[above left\] [$d$]{}; (e) node\[above right\] [$e$]{}; (f) node\[above right\] [$f$]{}; (r) node\[above right\] [$r$]{}; (r’) node\[above\] [$r'$]{}; (s) node\[above left\] [$s$]{}; (s’) node\[below left\] [$s'$]{}; (t) node\[right\] [$t$]{}; (t’) node\[below right\] [$t'$]{};

Before establishing the main lemma of this section let us notice the following remark.

\[Delta\] Call $\Delta$ the undirected graph defined by a triangle with three branches pending from each of its three nodes. There are only three possible directed graphs, $D_1$, $D_2$, $D_3$ such that $\Delta=I(D_1)=I(D_2)=I(D_3)$, as shown in Figure \[fig:k3s\]

\(a) at (0,2); (b) at ($ (a) + (-1.5,-2) $); (c) at ($ (a) + (0,-2) $); (d) at ($ (a) + (1.5,-2) $); (e) at (4,1.5); (f) at ($ (e) + (0,1.5) $); (g) at ($ (e) + (-0.75,-1.5) $); (h) at ($ (e) + (0.75,-1.5) $); (k) at (8,2); (i) at ($ (k) + (-1.3,-2) $); (j) at ($ (k) + (1.3,-2) $); (m) at (12,2); (l) at ($ (m) + (0,2) $); (n) at ($ (m) + (0,-2) $); (o) at ($ (b) + (0,-2) $); (p) at ($ (c) + (0,-2) $); (q) at ($ (d) + (0,-2) $); (r) at ($ (g) + (0,-2) $); (s) at ($ (h) + (0,-2) $); (t) at ($ (f) + (0,2) $); (u) at ($ (i) + (-120:2) $); (w) at ($ (j) + (-60:2) $); (v) at ($ (k) + (90:2) $); (p1) at ($ (c) + (0,-2.5) $); (s1) at ($ (h) + (-0.5,-2.5) $); (s1) at ($ (h) + (-0.5,-2.5) $); (v1) at (8,-2.5);

\(a) circle (1.5pt); (b) circle (1.5pt); (c) circle (1.5pt); (d) circle (1.5pt); (e) circle (1.5pt); (f) circle (1.5pt); (g) circle (1.5pt); (h) circle (1.5pt); (i) circle (1.5pt); (j) circle (1.5pt); (k) circle (1.5pt); (o) circle (1.5pt); (p) circle (1.5pt); (q) circle (1.5pt); (r) circle (1.5pt); (s) circle (1.5pt); (t) circle (1.5pt); (u) circle (1.5pt); (v) circle (1.5pt); (w) circle (1.5pt);

\(a) – (b); (a) – (c); (a) – (d);

\(b) – (o); (c) – (p); (d) – (q); (p1) node\[below\] [$D_1$]{};

\(f) – (e); (e) – (h); (e) – (g);

\(t) – (f); (g) – (r); (h) – (s); (s1) node\[below\] [$D_2$]{};

\(i) – (j); (j) – (k); (k) – (i);

\(u) – (i); (w) – (j); (v) – (k); (v1) node\[below\] [$D_3$]{};

\[GAD2\] Let $D$ be a directed graph such that $I(D)=\textsc{Gad}^2_j$. Then the two following assumptions hold:

-   The arcs $r'_j$, $s'_j$ and $t'_j$ cannot all enter the arcs $r_j$, $s_j$ and $t_j$, respectively,

-   Any other configuration for theses three adjacencies is possible.

\(i) Assume that in $D$ all the arcs $r'_j$, $s'_j$ and $t'_j$ enter the arcs $r_j$, $s_j$ and $t_j$, respectively. That is $h(r'_j)=t(r_j)$, $h(s'_j)=t(s_j)$ and $h(t'_j)=t(t_j)$. Therefore, from Remark \[Delta\], none of the triangles $\Delta_1$, $\Delta_2$ and $\Delta_3$ has the configuration $D_1$ of Figure \[fig:k3s\]. We may also check that $\Delta_2$ and $\Delta_3$ cannot have the same configuration, that is cannot be both of the form $D_2$ or $D_3$ of Figure \[fig:k3s\]. Hence assume that $\Delta_2$ has the form of $D_2$ and $\Delta_3$ has the form of $D_3$. Since the arc $e_j'$ must enter the arc $e_j$ it follows from Lemma \[GAD1\] that $$\begin{aligned}
 \label{1r}
 f'_j \mbox{ must enter the arc } f_j.
 \end{aligned}$$ Since $c_j$ enters the arc $d_j$ and using the fact that $s'_j$ enters $s_j$ we conclude that $b_j$ must enter the arc $b'_j$. Now using again Lemma \[GAD1\] we obtain $$\begin{aligned}
 \label{2r}
 a_j  \mbox{ must enter the arc } a'_j.
 \end{aligned}$$ Now combining the two facts and we have that $\Delta_1$ must be of the form $D_2$ of Figure \[fig:k3s\] and that the arc $r_j$ must enter $r'_j$, which is not possible.

\(ii) The proof of this assumption is presented in the appendix. It lists all the possible configurations of $D$ in Figure \[fig:preimages\_gad2\]

The construction of the graph $G_F$
-----------------------------------

Let $F=C_1\wedge\dots\wedge C_m$, where each clause $C_j=\lambda_{j_1}\vee\lambda_{j_2}\vee\lambda_{j_3}$, for $j$ in $\{1,\dots,m\}$. Each $\lambda_{j_k}$ correspond to the variable $x_{j_k}$ or its negation $\bar{x}_{j_k}$. From $F$ we construct an undirected graph $G_F$ as follows. Let $\textsc{Gad}^1_i$ be the undirected graph associated with each Boolean variable $x_i$, $i=1,\dots,n$. And let $\textsc{Gad}^2_j$ be the undirected graph associated with each clause $C_j$, $j=1,\dots,m$. In the construction of $G_F$, there is no connection between the graphs $\textsc{Gad}^1_i$ themselves and between the graphs $\textsc{Gad}^2_j$ themselves. The only connections are between $\textsc{Gad}^1_i$ and $\textsc{Gad}^2_j$ where the variable $x_i$ or $\bar{x}_i$ appears in the clause $C_j$. Moreover these connections are made through their branches. Specifically, for each clause $C_j=\lambda_{j_1}\vee\lambda_{j_2}\vee\lambda_{j_3}$ we do the following:

-   if $\lambda_{j_1} = x_{j_1}$, we identify vertex $r_j$ with vertex $g_j^{j_1}$ and vertex $r'_j$ with vertex $b_j^{j_1}$,

-   if $\lambda_{j_1} = \bar{x}_{j_1}$, we identify vertex $r_j$ with vertex $h_j^{j_1}$ and vertex $r'_j$ with vertex $f_j^{j_1}$,

-   if $\lambda_{j_2} = x_{j_2}$, we identify vertex $s_j$ with vertex $g_j^{j_2}$ and vertex $s'_j$ with vertex $b_j^{j_2}$,

-   if $\lambda_{j_2} = \bar{x}_{j_2}$, we identify vertex $s_j$ with vertex $h_j^{j_2}$ and vertex $s'_j$ with vertex $f_j^{j_2}$,

-   if $\lambda_{j_3} = x_{j_3}$, we identify vertex $t_j$ with vertex $g_j^{j_3}$ and vertex $t'_j$ with vertex $b_j^{j_3}$,

-   if $\lambda_{j_3} = \bar{x}_{j_3}$, we identify vertex $t_j$ with vertex $h_j^{j_3}$ and vertex $t'_j$ with vertex $f_j^{j_3}$.

Proof of Theorem \[NP-complete\] {#proof-NP-complete}
--------------------------------

Since the problem 3-<span style="font-variant:small-caps;">sat</span> is NP-complete, it is sufficient to prove that the Boolean formula $F$, as defined in the previous subsection, is true if and only if the graph $G_F$ is a facility location graph.

Assume that the graph $G_F$ is a facility location graph and let $D$ be a directed graph such that $I(D)=G_F$. Define an assignment of the Boolean variables $x_i$, $i=1\dots,n$ as follows: $$x_i=\left\lbrace
\begin{array}{ll}
1 & \mbox{ if  the arc }g^i_1 \mbox{ enters the arc } b^i_1 \mbox{ in } D,\\
0 & \mbox{otherwise}
\end{array}
\right.$$

Notice that from Lemma \[GAD1\] whenever the arc $g^i_1$ enters the arc $b^i_1$, then $g^i_j$ enters the arc $b^i_j$ for each $j=1,\dots,m$. Let $C_j$ be any clause of $F$. From Lemma \[GAD2\] (i), we must have that $r_j$ enters $r'_j$, or $s_j$ enters $s'_j$ or that $t_j$ enters $t'_j$ in any directed graph whose intersection graph is $\textsc{Gad}^2_j$. We may assume that $r_j$ enters $r'_j$. By the definition of $G_F$ the branch $r_jr'_j$ is identified with $g^i_jb^i_j$ when $x_i$ is present in $C_j$ and in this case $x_i=1$ and so $C_j$=1. Otherwise the branch $r_jr'_j$ is identified with $h^i_jf^i_j$ when $\bar{x}_i$ is present in $C_j$. So the arc $h^i_j$ enters the arc $f^i_j$ and from Lemma \[GAD1\] we have that the arc $b^i_j$ enters the arc $g^i_j$ and by definition we have $x_i=0$, which implies that $C_j=1$.

Now assume that there is an assignment of the variables $x_i$, $i=1,\dots,n$ satisfying $F$. Let us construct a directed graph $D$ such that $G_F=I(D)$. For each graph $\textsc{Gad}^1_i$ we build a directed graph such that each arc $g^i_j$ enters the arc $b^i_j$ when $x_i=1$ and each arc $b^i_j$ enters $g^i_j$ when $x_i=0$. This is possible from Lemma \[GAD1\]. Now given a clause $C_j=\lambda_{j_1}\vee\lambda_{j_2}\vee\lambda_{j_3}$, from Lemma \[GAD2\] the graph $D$ cannot exist only when the assumption (i) of Lemma \[GAD2\] is not satisfied. But one can check that this may happen only when $\lambda_{j_1}=\lambda_{j_2}=\lambda_{j_3}=0$, which is not possible.

Recognizing triangle-free facility location graphs {#RTFLG}
==================================================

Notice that the maximum cliques on the graph $G_F$ built by our reduction in the section have size 3. Hence it is natural to ask if recognizing triangle-free facility location graphs remains difficult. In this section we show that this recognition may be done in polynomial time.

In subsection \[struc\] we examine the structure of general FL graphs. In subsection \[app-tri-free\], we restrict ourselves to triangle-free graphs and we give the main result of this section.

Some structural properties {#struc}
--------------------------

In [@BBpg], Baïou and Barahona gave a characterization of preimages of cycles.

[@BBpg] \[cycle\] Given a directed graph $D=(V,A)$, a subset of arcs $C\subseteq A$ induce a chordless cycle of size at least four in $I(D)$, if and only if $C$ may be partitioned into two subsets $C'$ and $C''$, such that $C'$ is a cycle in $D$ and there is a 1-to-1 correspondence between the nodes in $\hat{C'}$ and the arcs in $C''$, where each arc $(v,\bar{v})$ of $C''$ correspond to a node $v\in\hat{C'}$ where (i) $\bar{v}\in V\setminus V(C')$ or (ii) $\bar{v}\in \tilde{C'}$ with $\bar{v}$ is one of the two neighbors of $v$ in $C'$, see Figure \[cycles\] for an example.

\(a) at (0,2); (b) at ($ (a) + (2,-2) $); (c) at ($ (b) + (0,-2) $); (d) at ($ (c) + (-2,-2) $); (e) at ($ (d) + (-2,2) $); (f) at ($ (e) + (0,2) $); (g) at ($(d)+(0.5,1.5)$);

\(a) circle (1.5pt); (b) circle (1.5pt); (c) circle (1.5pt); (d) circle (1.5pt); (e) circle (1.5pt); (f) circle (1.5pt);

\(a) – (b) node\[midway,right\][$a_1$]{}; (b) – (c) node\[midway,right\][$a_2$]{}; (c) – (d) node\[midway,right\][$a_3$]{};

\(e) – (d) node\[midway,left\][$a_4$]{}; (f) – (e) node\[midway,left\][$a_5$]{}; (a) – (f) node\[midway,left\][$a_6$]{}; (d) to\[bend left=45\] (c); (g) node\[above\][$b$]{};

Notice that we may have $C''=\emptyset$. In this case $C$ is a directed cycle in $D$. Notice the following remark.

\[pendent\] Let $G$ be an undirected graph. Let $e=uv$ an edge of $G$ where $u$ has degree one and $v$ has degree two. Then $G$ is a FL graph if and only if $G-u$ is also a FL graph.

\[sink\] If $G$ is a FL graph, then there exists a digraph $D$ such that $G=I(D)$ and every sink node in $D$ has exactly one entering arc.

Since $G$ is a FL graph, there exists a directed graph $D'$ such that $G=I(D')$. If $u$ is a sink node with the entering arcs $(u_1,u),\dots,(u_k,u)$, $k\geq 2$. We may split the node $u$ and so each arc $(u_i,u)$ is replaced by $(u_i,u_i')$, where each node $u_i'$ is a sink with only one entering arc. If $D$ is the resulting directed graph we have that $G=I(D)$.

\[degre2\] Given an undirected graph $G$. If there is an edge $e=bc$ in $G$ such that $b$ and $c$ both have degree two and no common neighbour, then the following statements are equivalent:

1.  $G$ is a FL graph,

2.  $G - e$ is a FL graph.

Let us call $a$ the other neighbour of $b$ and $d$ the other neighbour of $c$ (see Figure \[trans\]).

[*(i) $\Rightarrow$ (ii)*]{}. Assume that $G$ is a FL graph and hence $G=I(D)$. Assume that the arcs $a$ and $c$ have no common vertex in $D$, in this case the arc $b$ must share exactly one endnode with $a$ and one endnode with $c$. Replace the arc $b=(r,s)$ by $b=(r',s)$ (respectively $b=(r,s')$) when $r$ (respectively $s$) is an endnode of $c$. The nodes $r'$ and $s'$ are new nodes. Call the resulting graph $D'$. We have $G - e=I(D')$.

Now assume that $a$ and $c$ have a common endnode. Let $a=(u,v)$ and $c=(w,t)$. Since $a$ and $c$ are not adjacent we must have $v=t$ and $u\not=w$. Let $b=(r,s)$. If $r\not=v$, then as in the previous case we replace the arc $b=(r,s)$ by $b=(r',s)$ (respectively $b=(r,s')$) when $r$ (respectively $s$) is an endnode of $c$ and we obtain a new graph $D'$ with $G - e=I(D')$. If $r=v$, replace the arc $c=(w,t)$ by $c=(w,t')$, and if in addition we have $s=w$ we replace the arc $b=(r,s)$ by $b=(r,s')$, where $s'$ and $t'$ are two new nodes. It is easy to check that we obtain a new graph $D'$ with $G-e=I(D')$.

[*(ii) $\Rightarrow$ (i).*]{} Now assume that $G - e=I(D')$. Let $G''$ be the graph obtained from $G-e$ by adding a node $b''$ and the edge $b''c$. To avoid confusion, we rename the node $b$ by $b'$, see Figure \[trans\]. From Remark \[pendent\], we know there exists a directed graph $D''$ such that $G''=I(D'')$.

\(a) at (0,2); (b) at ($ (a) + (0,3) $); (c) at ($ (b) + (3,0) $); (d) at ($ (a) + (3,0) $); (e) at ($ (a) + (10,0) $); (f) at ($ (e) + (0,3) $); (g) at ($ (f) + (3,0) $); (h) at ($ (g) + (0,-1.5) $); (i) at ($ (h) + (0,-1.5) $); (j) at (-2,1.5); (k) at (5,1.5); (l) at ($ (e) + (-2,-0.5) $); (m) at ($ (i) + (+2,-0.5) $);

\(a) circle (1.5pt); (b) circle (1.5pt); (c) circle (1.5pt); (d) circle (1.5pt); (e) circle (1.5pt); (f) circle (1.5pt); (g) circle (1.5pt); (h) circle (1.5pt); (i) circle (1.5pt);

\(j) to \[bend left\] (k); (l) to \[bend left\] (m); (a) – (b); (b) – (c); (c) – (d);

\(e) – (f); (g) – (h); (h) – (i);

\(a) node\[left\] [$a$]{}; (b) node\[above\] [$b$]{}; (c) node\[above\] [$c$]{}; (d) node\[right\] [$d$]{}; (e) node\[left\] [$a$]{}; (f) node\[above\] [$b'$]{}; (g) node\[above\] [$b''$]{}; (h) node\[right\] [$c$]{}; (i) node\[right\] [$d$]{};

By Lemma \[sink\] we may pick $D''$ such that every sink has a most one entering arc.

Let $b'=(r,s)$ and $b''=(t,u)$.

The nodes $b'$ and $b''$ have no node in common. Indeed, if $b'$ and $b''$ have a common node it must be that $s=u$, and since in $G''$ the nodes $b'$ and $b''$ are not adjacent. And $s$ must be a sink since $b'$ and $b''$ have no common neighbour. It follows that $s$ is a sink having at least two entering nodes, which is a contradiction.

Moreover, we may assume that $a\not=(s,r)$ and $c\not=(u,t)$. If $a=(s,r)$. Since $a$ is the unique neighbor of $b'=(r,s)$, we may replace the arc $b'$ by $b=(r,s')$ with $s'$ a new node. The same arguments hold when $c=(u,t)$.

Therefore, the connections between the arcs $b'$ and $a$ and between $b''$ and $c$ are of three types as shown in the Figure \[connection\] below.

\(a) at (0,2); (b) at ($ (a) + (0,-3) $); (c) at ($ (b) + (3,0) $); (d) at ($ (a) + (7,0) $); (e) at ($ (d) + (0,-3) $); (f) at ($ (d) + (3,0) $); (g) at ($ (f) + (4,0) $); (h) at ($ (g) + (3,0) $); (i) at ($ (h) + (0,-3) $); (j) at ($ (b) + (1.5,-1.5) $); (k) at ($ (e) + (1.5,-1.5) $); (l) at ($ (g) + (1.5,-4.5) $);

\(a) circle (1.5pt); (b) circle (1.5pt); (c) circle (1.5pt); (d) circle (1.5pt); (e) circle (1.5pt); (f) circle (1.5pt); (g) circle (1.5pt); (h) circle (1.5pt); (i) circle (1.5pt);

\(b) circle(0.25); (c) circle(0.25); (d) circle(0.25); (f) circle(0.25); (g) circle(0.25); (a) – (b) node\[midway,right\][$a(c)$]{}; (b) – (c) node\[midway,below\][$b'(b'')$]{}; (d) – (e) node\[midway,right\][$a(c)$]{}; (d) – (f) node\[midway,above\][$b'(b'')$]{}; (g) – (h) node\[midway,above\][$b'(b'')$]{}; (h) – (i) node\[midway,right\][$a(c)$]{}; (j) node\[below\] [(I)]{}; (k) node\[below\] [(II)]{}; (l) node\[below\] [(III)]{};

In some cases a simple identification of the arcs $b'$ and $b''$ give rise to a graph $D$ with $I(D)=G$. Identifying the arcs $b'=(r,s)$ and $b''=(t,u)$ means that we remove them and we shrink $r$ with $t$ and $s$ with $u$, where $r'$ and $s'$ are the resulting nodes, respectively. Finally we put $b=(r',s')$. The cases where such an operation may be done are summarized in the Table \[tab:comp\] below.

  -- ------- ----- ------ -------
                          
              (I)   (II)   (III)
       (I)                
      (II)                
      (III)               
  -- ------- ----- ------ -------

  : Compatibility between types[]{data-label="tab:comp"}

If a connection of type (II) occurs, say between $a$ and $b'$, we may replace the arc $a=(r,v)$ by $a=(s,v)$. The head of $a$ is unchanged but its tail now coincide with the head of $b'$. This transformation will not alter $G''$, that is $G''$ is again the intersection graph of the resulting directed graph. Moreover the connection between $a$ and $b'$ is now of type (III). Therefore the only remaining case to study is when the connection between $a$ and $b'$ and between $c$ and $b''$ are both of type (III). Recall that $c$ is adjacent to only $b''$ and $d$ in $G''$. Let $d=(v,w)$. If the head of the arc $c$ is $v$ in $D''$, we set $c=(t,v)$. Again $G''$ is the intersection graph of this new directed graph and the connection of $c$ and $b''$ is of type (II). Now assume that $w=u$, in this case we may set $b''$ to be the arc going from the head of $c$ to $t$ and we obtain a connection of type (I) between, $b''$ and $c$.

Notice that Lemma \[degre2\] is not true when $b$ and $c$ are two adjacent nodes of degree two with a common neighbor $a$, that is $a,b,c$ is a triangle. In fact, the graph shown in Figure \[2tri\] (a) is not a FL graph, but the graph obtained by removing the edge $e=bc$ is a FL graph. And the graph shown in Figure \[2tri\](b) is a FL graph, but if we remove the edge $e=bc$ the resulting graph is not anymore a FL graph. But we may easily check that when $a$ has only one neighbor different from $b$ and $c$, then Lemma \[degre2\] holds.

\(a) at (0,2); (b) at ($ (a) + (0,-2) $); (c) at ($ (b) + (2,1) $); (d) at ($ (c) + (0,-2) $); (e) at ($ (c) + (2,1) $); (f) at ($ (e) + (0,-2) $); (g) at ($ (e) + (4,1) $); (h) at ($ (g) + (0,-2) $); (j) at ($ (g) + (2,-1) $); (k) at ($ (j) + (0,-2) $); (l) at ($ (k) + (0,-2) $); (i) at ($ (k) + (-2,-1) $); (m) at ($ (j) + (2,-1) $); (n) at ($ (j) + (4,0) $); (o) at ($ (n) + (0,-2) $); (p) at ($ (d) + (0,-1.5)$); (q) at ($ (l) + (1,-0.5) $);

\(a) circle (1.5pt); (b) circle (1.5pt); (c) circle (1.5pt); (d) circle (1.5pt); (e) circle (1.5pt); (f) circle (1.5pt); (g) circle (1.5pt); (h) circle (1.5pt); (i) circle (1.5pt); (j) circle (1.5pt); (k) circle (1.5pt); (l) circle (1.5pt); (m) circle (1.5pt); (n) circle (1.5pt); (o) circle (1.5pt);

\(a) – (b); (a) – (c); (b) – (c); (c) – (d); (c) – (e); (e) – (f); (c) – (f); (j) – (g); (j) – (h); (j) – (k); (k) – (l); (k) – (i); (i) – (l); (k) – (m); (j) – (m); (m) – (n); (m) – (o); (n) – (o); (c) node\[above\][$a$]{}; (e) node\[above\][$b$]{}; (f) node\[below\][$c$]{}; (m) node\[above\][$a$]{}; (n) node\[above\][$b$]{}; (o) node\[below\][$c$]{}; (p) node\[below\][(a)]{}; (q) node\[below\][(b)]{};

Application to triangle-free facility location graphs {#app-tri-free}
-----------------------------------------------------

\[fork\] Let $G$ be a connected triangle-free graph that does not contain two adjacent nodes having both degree two. If $G$ is a FL graph, that is there exists a directed graph $D=(V,A)$ with $G=I(D)$, then for each vertex $v\in V$ we have (i) $v$ is the tail of at most one arc or (ii) $v$ is the tail of exactly two arcs $(v,v_1)$ and $(v,v_2)$ and there is no arc leaving $v_1$ and $v_2$.

Since $G$ is triangle-free, $v$ is the tail of at most two arcs. Therefore we may assume it is the tail of exactly two arcs $(v,v_1)$ and $(v,v_2)$. Notice that there is no arc entering $v$, otherwise $G$ contains a triangle. Assume that for each node $v_i$, the arc $(v_i,v'_i)$ exists. Notice that there are no other arcs leaving $v_1$ or $v_2$. Call $b=(v,v_1)$ and $c=(v,v_2)$. We have that $b$ and $c$ are two adjacent nodes in $G$ having degree two.

\[triangle-free\] Let $G$ be a triangle-free graph. Define $G'$ to be the graph obtained from $G$ by removing each edge $e=bc$ where $b$ and $c$ have degree two. Then $G$ is a FL graph if and only if $G'$ admits at most one cycle.

From Lemma \[degre2\], we may assume that $G$ does not contain an edge $e=bc$ where $b$ and $c$ have degree two.

[*Necessity.*]{} Let $G$ be a triangle-free facility location graph, that is there exist a directed graph $D=(V,A)$, with $G=I(D)$. Also assume that there are no two adjacent nodes of degree two. Suppose that there is a connected component of $G$ containing two cycles $C_1$ and $C_2$. We may assume that both $C_1$ and $C_2$ are chordless cycles. By Lemma \[cycle\], $C_1$ may be partitioned into $C'_1$ and $C''_1$ and $C_2$ may be partitioned into $C'_2$ and $C''_2$. We have that $C'_1$ and $C'_2$ are two cycles in $D$ and $C''_1$ and $C''_2$ are as defined in Lemma \[cycle\].

From Lemma \[fork\], we have $\dot{C'_1}=\dot{C'_2}=\emptyset$. That is both $C'_1$ and $C'_2$ are directed cycles and that $C''_1=C''_2=\emptyset$. Notice that $C_1$ and $C_2$ have no node in common, otherwise $C'_1$ and $C'_2$ must share at least one arc, and since they are both directed cycles, we must create a triangle in $G$. Since $C_1$ and $C_2$ belong to the same connected component we must have a path $P$ in $G$ connecting a vertex $u$ of $C_1$ and a vertex $v$ of $C_2$. Let $P=(v_1=(u_1,u'_1),
v_2=(u_2,u'_2),\dots,v_{p-1}=(u_{p-1},u'_{p-1}), v_p=(u_p,u'_p))$, with $u=v_1$ and $v=v_p$. Then $u'_1=u'_2$ and $u'_{p-1}=u'_p$. In this case, $P$ cannot be a directed path in $G$. It follows, that there exists at least one node $u_k$ that contradicts Lemma \[fork\].

[*Sufficiency.*]{} Consider a connected component of $G$. Suppose that it consists of a tree. Let us construct a directed graph $D$ with $G=I(D)$. Pick any node $r$ as a root. Let $r=(u_0,v_0)$. Let $r_1,\dots,r_k$ be the children of $r$ in $G$, we set $r_i=(v_i,u_0)$ for $i=1,\dots,k$. Now each node $r_i$ play the role of $r$ and we repeat this step. This procedure ends with a directed graph $D$ such that $G=I(D)$.

Suppose that there is a cycle $C$. This cycle must be chordless. Let $C'$ be a directed cycle where each arc in $C'$ correspond to a node in $C$. The rest of this component consist of disjoint trees each intersect $C$ in one node. If this node is chosen to be the root of the tree, then the procedure above may be applied to get a directed graph $D$ such that $G=I(D)$.

As a consequence we obtain the following result.

Given an undirected triangle-free graph $G=(V,E)$, we may decide whether or not $G$ is a facility location graph in $O(|E|)$.

In $O(|E|)$ we may remove all the edges $e=bc$ with both $b$ and $c$ of degree two. Then we apply a breadth-first search in $O(|E|)$. If a node is encountered more than twice or there are two nodes that were encountered twice, then there are two cycles. Otherwise $G$ is a facility location graph.

Consequences and related problems {#RP}
=================================

 The vertex coloring problem
----------------------------

A [*vertex color*]{} of a graph is an assignment of colors to the nodes of the graph such that no two adjacent nodes receive the same color. The minimum number needed for a such coloring is called the [*chromatic number*]{} and denoted by $\chi(G)$. It is well known that finding $\chi(G)$ is <span style="font-variant:small-caps;">np</span>-complete for triangle-free graphs. A direct consequence of the previous section shows that $\chi(G)\leq 3$ when $G$ is a triangle-free facility location graph.

Let $G=(V,E)$ be a triangle-free facility location problem and $G'$ the graph defined in Theorem \[triangle-free\]. It follows that each connected component of $G'$ contains at most one cycle. If there is an odd cycle then $\chi(G')=3$, otherwise $\chi(G')=2$. Let us extend the coloring of $G'$ to $G$. The reconstructing of $G$ from $G'$ implies that at each step we add an edge $e=bc$ between two pendent nodes of $G'$. We keep calling the graph obtained at each step $G'$, until the last step that produce $G$. Let $b'$ and $c'$ be, respectively, the unique neighbors of $b$ and $c$ in $G'$. If $b$ and $c$ have not the same color then we add $e=bc$ without altering the existing coloring. Assume that $b$ and $c$ have the same color. If $b'$ and $c'$ have different colors, then we may assign the color of $c'$ to $b$, or the color of $b'$ to $c$. Finally if $b'$ and $c'$ have the same color, then we pick arbitrarily $b$ or $c$ and we assign him a third available color.

From the discussion above, we have the following:

\[coloration\] If $G$ is a triangle-free facility location graph, then $\chi(G)\leq
3$. Moreover, $\chi(G)$ may be computed in $O(|E|)$.

A natural question arises: whether or not coloring facility locations graphs is polynomial. Unfortunately the answer is no. This will be shown using a reduction from the edge coloring problem. Given an undirected graph $G=(V,E)$ an [*edge color*]{} of $G$ is a coloring of the edges that gives two different colors for each pair of incident edges.

Coloring facility locations graphs is <span style="font-variant:small-caps;">np</span>-complete.

Given a undirected graph $G=(V,E)$ and positive integer $k$, the problem of deciding wether or not we can color the edges of $G$ with $k$ colors has been proved to be <span style="font-variant:small-caps;">np</span>-complete by Holyer in [@Hoy]. We will reduce this problem to the problem of whether or not we can color the nodes of a facility location graph with $k$ colors. Precisely, from $G=(V,E)$ we build a directed graph $D$ such that the edges of $G$ may be colored with $k$ colors if and only if the nodes of $I(D)$ may be colored with $k$ colors.

Let $E=\{e_1,\dots,e_m\}$. We build $D$ as follows: for each edge $e_i=uv\in E$ we add a node $v_i$ and the arcs $(u,v_i)$ and $(v,v_i)$. For each node $v_i$ we add $k-1$ arcs $(v_i,v_{i_1}),\dots,(v_i,v_{i_{k-1}})$, where $v_{i_1},\dots,v_{i_{k-1}}$ are new nodes.

Assume that $G$ admits an edge coloring with $k$ colors. Assign the color of each edge $e_i=uv$ to the nodes $(u,v_i)$ and $(v,v_i)$ of $I(D)$ and color the nodes $(v_i,v_{i_1}),\dots,(v_i,v_{i_{k-1}})$ with the other $k-1$ colors. This is a vertex coloring of $I(D)$ with $k$ colors. Now assume $I(D)$ admits a vertex coloring with $k$ colors. Since each node $(v_i,v_{i_1}),\dots,(v_i,v_{i_{k-1}})$ of $I(D)$ must receive a different colors (because they form a clique in $I(D)$) we have that both nodes $(u,v_i)$ and $(v,v_i)$ must have the same color, then assign this color ro the edge $e_i=uv$ of $G$. The resulting coloring is an edge coloring of $G$ with $k$ colors or less.

The stable set problem
----------------------

Given an undirected graph $G=(V,E)$, a subset of nodes $S\subseteq V$ of an undirected graph is called a [*stable set*]{} if there is no edge between any two nodes of $S$. The [*maximum stable set problem*]{} is to find a stable set of maximum size. This size is usually called the [*stability number*]{} and denoted by $\alpha(G)$. If we associate a weight $w(v)$ to each vertex $v\in V$, then the [ *maximum weighted stable set problem*]{} if to find a stable set $S$ with $\sum_{v\in S}w(v)$ maximum.

The maximum stable set problem is <span style="font-variant:small-caps;">np</span>-complete for triangle-free graph. One may show this result using the following transformation due to Poljak [@Poljak]. Given any undirected graph $G=(V,E)$ replace any edge $e=uv$ in $E$ by a path $uu',u'u'',u''v$. The resulting graph $\textsc{Sub}_G$ is triangle-free and $\alpha(\textsc{Sub}_G)=\alpha(G)+|E|$. This shows that the maximum stable set problem is <span style="font-variant:small-caps;">np</span>-complete in triangle-free graphs. Using Theorem \[triangle-free\] we have that $\textsc{Sub}_G$ is also a facility location graph, since the removal of the edges $u'u''$ yields a graph where each connected component is a star. As a consequence we obtain the following result,

\[tfg-complete\] The maximum stable set problem is <span style="font-variant:small-caps;">np</span>-complete in triangle-free facility location graphs.

Since from Theorem \[coloration\] one may color the vertices of any triangle-free facility location graph with 3 colors in $O(|E|)$, this immediately implies a 3-approximation algorithm for the maximum stable set problem. This remains true for the maximum weighted stable set problem. In fact, let $V_1$, $V_2$, $V_3$ be a partition of $V$ where each subset $V_i$ is stable. Let $V'_i\subseteq V_i$, be the nodes of $V_i$ having only positive weights, for $i=1,\dots,3$. Let $w(V'_1)=\mbox{max }\{w(V'_2), w(V'_3)\}$ and $S^*$ the stable set of maximum weight. We have $$w(S^*)\leq w(V'_1)+w(V'_2)+w(V'_3)\leq 3w(V'_1).$$

The facility location problem
-----------------------------

Recall that the uncapacitated facility location problem (UFLP) associated with a directed graph $D$ is equivalent to the maximum weighted stable set problem with respect to $I(D)$. Therefore, from Theorem \[tfg-complete\] we have the following corollary.

The uncapacitated facility location problem associated with directed graph $D$ is <span style="font-variant:small-caps;">np</span>-complete even when $D$ does not contain the four graphs of Figure \[fig:triangle\] as subgraphs.

\(a) at (0,2); (b) at ($ (a) + (-1.5,-2) $); (c) at ($ (a) + (0,-2) $); (d) at ($ (a) + (1.5,-2) $); (e) at (4,1.5); (f) at ($ (e) + (0,1.5) $); (g) at ($ (e) + (-0.75,-1.5) $); (h) at ($ (e) + (0.75,-1.5) $); (k) at (8,2); (i) at ($ (k) + (-1.3,-2) $); (j) at ($ (k) + (1.3,-2) $); (m) at (12,2); (l) at ($ (m) + (0,2) $); (p1) at ($ (c) + (0,-1.5) $); (s1) at ($ (h) + (-0.5,-1.5) $); (v1) at (8,-1.5); (o) at (12,1.5); (p) at ($ (o) + (0,1.5) $); (q) at ($ (o) + (0,-1.5) $); (o1) at ($ (v1) + (4,0) $);

\(a) circle (1.5pt); (b) circle (1.5pt); (c) circle (1.5pt); (d) circle (1.5pt); (e) circle (1.5pt); (f) circle (1.5pt); (g) circle (1.5pt); (h) circle (1.5pt); (i) circle (1.5pt); (j) circle (1.5pt); (k) circle (1.5pt); (o) circle (1.5pt); (p) circle (1.5pt); (q) circle (1.5pt);

\(a) – (b); (a) – (c); (a) – (d);

(p1) node\[below\] [$T_1$]{};

\(f) – (e); (e) – (h); (e) – (g);

(s1) node\[below\] [$T_2$]{};

\(i) – (j); (j) – (k); (k) – (i);

(v1) node\[below\] [$T_3$]{};

\(o) to\[bend left=45\] (p); (p) to\[bend left=45\] (o); (o) – (q);

(o1) node\[below\] [$T_4$]{};

In the following we will show that the UFLP remains <span style="font-variant:small-caps;">np</span>-complete even for a more restricted class of graphs.

An undirected graph $G=(V,E)$ is called [*cubic*]{} is the degree of each vertex is 3. A [*bridge*]{} is an edge such that its deletion increase the number of connected components. A [*bridgeless*]{} graph is a graph with no bridge. We have the following well know result.

[@GJS] \[GJ\] The maximum stable set problem in cubic graphs is <span style="font-variant:small-caps;">np</span>-complete.

In [@GJS] it has been shown that the [*minimum vertex cover*]{} problem is <span style="font-variant:small-caps;">np</span>-complete, here we look for a subset of nodes with minimum cardinality, such that each edge has at least one endnode in this set. Notice that if $S$ is a minimum vertex cover, then $\bar{S}=V\setminus S$ is a maximum stable set. Then both problems minimum vertex cover and maximum stable set are equivalent in the same graph without any transformation. We also notice that the proof in [@GJS] use a reduction of 3-<span style="font-variant:small-caps;">sat</span> to the minimum vertex cover problem. The graph constructed from a 3-<span style="font-variant:small-caps;">sat</span> instance is bridgeless and each node has at most degree 3. Moreover, each node with degree 2 has two non-adjacent nodes of degree 3. Thus we can remove this nodes and connect its two neighbors. It is easy to check that if one can solve the minimum vertex cover problem in this new graph, then one may solve it in the original graph too. From this discussion and Theorem [@GJS] we have the following corollary.

\[coro-GJS\] The maximum stable set problem in a bridgeless cubic graph is <span style="font-variant:small-caps;">np</span>-complete.

In addition to the forbidden subgraphs $T_1$, $T_2$, $T_3$ and $T_4$ we also add the subgraphs $F_1$ and $F_2$ of Figure \[fig:3in\], and the UFLP remains <span style="font-variant:small-caps;">np</span>-complete.

\(a) at (0,2); (b) at ($ (a) + (0,1.5) $); (c) at ($ (a) + (1,1.5) $); (d) at ($ (a) + (-1,1.5) $); (e) at ($ (a) + (0,-1.5) $);

(a2) at ($ (a) + (4,0) $); (c2) at ($ (c) + (4,0) $); (d2) at ($ (d) + (4,0) $); (e2) at ($ (e) + (4,0) $);

(s1) at ($ (e) + (0,-0.5) $); (s2) at ($ (e2) + (0,-0.5) $);

\(a) circle (1.5pt); (b) circle (1.5pt); (c) circle (1.5pt); (d) circle (1.5pt); (e) circle (1.5pt); (a2) circle (1.5pt); (c2) circle (1.5pt); (d2) circle (1.5pt); (e2) circle (1.5pt);

\(b) – (a); (c) – (a); (d) – (a); (a) – (e);

(c2) – (a2); (d2) – (a2); (a2) to\[bend left=45\] (e2); (e2) to\[bend left=45\] (a2);

(s1) node\[below\] [$F_1$]{}; (s2) node\[below\] [$F_2$]{};

\[UFLP-NP\] The uncapacitated facility location problem is <span style="font-variant:small-caps;">np</span>-complete for graphs that do not contain any of $T_1$, $T_2$, $T_3$, $T_4$, $F_1$ and $F_2$ as a subgraph.

Let $G=(V,E)$ be an undirected bridgeless cubic graph. From $G$ define the subdivision of it, $\textsc{Sub}_G$, as in the previous subsection, that is each edge $e=uv\in E$ is replaced by path of size three. Now we construct a directed graph $D$ containing none of the graphs $T_1$, $T_2$, $T_3$, $T_4$, $F_1$ and $F_2$ as a subgraph and such that $I(D)=\textsc{Sub}_G$. Thus from Corollary \[coro-GJS\] the maximum weighted stable set problem is <span style="font-variant:small-caps;">np</span>-complete in bridgeless cubic graphs, and by equivalence we have that UFLP is also <span style="font-variant:small-caps;">np</span>-complete in graphs satisfying the theorem’s hypothesis. Now let us give the construction of $D$.

From Petersen’s theorem [@pet], the graph $G$ contains a perfect matching $M$. Let $G'$ be the graph obtained by removing $M$. Each component of $G'$ is a chordless cycle. Let $C=v_0,v_1,\dots,v_p$ be one of these cycles. In $\textsc{Sub}_G$ this cycle corresponds to a cycle $C'=v_0,v_1,v_2,\dots,v_{3p},v_{3p+1},v_{3p+2}$. Let us construct a directed graph $D$ with $I(D)=\textsc{Sub}_G$. Each cycle $C'$ of $\textsc{Sub}_G$ may be defined in $D$ by the directed cycle where the arc $v_i$ enters the arc $v_{i+1}$ for each $i=0,\dots,3p+1$, and the arc $v_{3p+2}$ enters the arc $v_0$ (an arc $a$ enters an arc $b$ means that the head of $a$ coincide with the tail of $b$). To complete the definition of $D$ we need to consider all the edges of $M$ and their subdivisions. Let $e=uv\in M$ and $u_1,u_2,u_3,u_4$ the corresponding path in $\textsc{Sub}_G$. Complete the construction of $D$ by creating for every such edge $e$ two arcs $u_2$ and $u_3$ having the same tail where $u_2$ enters the arc $u_1$ and $u_3$ enters the arc $u_4$. This transformation is depicted in Figure \[illust\].

By construction we have that $I(D)=\textsc{Sub}_G$ and that each node is the head of at most two arcs, hence $F_1$ is not present in $D$ and it is easy to see that with construction $F_2$ cannot occur. Also there are no $T_1$, $T_2$, $T_3$ and $T_4$ in $D$ since $\textsc{Sub}_G$ is triangle-free, see Figure \[illust\].

Concluding remarks {#conc}
==================

In this paper we studied the class of facility location graphs. These graphs come from the classical and well studied uncapacitated facility location problem. We have shown that the recognition problem of these graphs is <span style="font-variant:small-caps;">np</span>-complete in general and polynomially solvable in free-triangle graphs. As a consequence, we observed that the stable set problem still <span style="font-variant:small-caps;">np</span>-complete on a more restricted class than triangle-free graphs and that three colors suffice to color the vertex set of a triangle-free facility location graph. We also studied the complexity of two problems (1) the vertex coloring problem in facility location graphs and (2) the uncapacitated facility location problem in graphs that do not contain as a subgraph the graphs $T_1$, $T_2$, $T_3$ , $T_4$, $F_1$ and $F_2$. Let us discuss a natural attempt for restricting more this class of graphs.

We know from [@BBdo1; @Stauffer] that if the graph $F_3$ of Figure \[Y\] is forbidden, then UFLP is polynomially solvable. Now consider a graph without any of the subgraphs $T_1,\dots,T_4$, $F_1$ and $F_2$ and containing the subgraph $F_3$. There is at least an arc leaving the node $u$ of $F_3$, otherwise by definition any feasible solution of UFLP must contain $u$ and in that case $u$ may be splitted into several copies depending on the number of arcs entering it. The arc leaving $u$ must have a head that do not belong to $F_3$, which lead to the graph $F_4$ of Figure \[Y\]. Now if we consider a directed graph $D$ with no $F_4$ and since we do not have $F_1$ and $F_2$, the intersection graph $I(D)$ is claw-free and hence the maximum stable set problem is polynomially solvable [@Minty; @Sbihi; @Faenza]. Equivalently, the UFLP is polynomially solvable if, in addition to the hypothesis of Theorem \[UFLP-NP\], we forbid also the subgraph $F_4$.

\(a) at (0,2); (c) at ($ (a) + (1,1.5) $); (d) at ($ (a) + (-1,1.5) $); (e) at ($ (a) + (0,-1.5) $);

(a1) at ($ (a) + (4,1.5) $); (c1) at ($ (c) + (4,1.5) $); (d1) at ($ (d) + (4,1.5) $); (e1) at ($ (e) + (4,1.5) $); (f) at ($ (e1) + (0,-1.5) $);

(s1) at ($ (e) + (0,-0.5) $); (s2) at ($ (f) + (0,-0.5) $);

\(a) circle (1.5pt); (c) circle (1.5pt); (d) circle (1.5pt); (e) circle (1.5pt); (a1) circle (1.5pt); (c1) circle (1.5pt); (d1) circle (1.5pt); (e1) circle (1.5pt); (f) circle (1.5pt);

\(c) – (a); (d) – (a); (a) – (e);

(c1) – (a1); (d1) – (a1); (a1) – (e1); (e1) – (f);

\(e) node\[right\] [$u$]{}; (e1) node\[right\] [$u$]{}; (s1) node\[below\] [$F_3$]{}; (s2) node\[below\] [$F_4$]{};

Acknowledgements {#acknowledgements .unnumbered}
================

The authors wish to thank Reza Naserasr for fruitful discussions.

Appendix {#appendix .unnumbered}
========

Figures to explicitely prove Lemma \[GAD2\].
