Submitted to
manuscript (Please, provide the manuscript number!)

On the Minimum Chordal Completion Polytope
David Bergman

arXiv:1612.01966v1 [] 6 Dec 2016

Operations and Information Management, University of Connecticut, Storrs, Connecticut 06260
david.bergman@business.uconn.edu

Carlos H. Cardonha
IBM Research, Brazil, São Paulo 04007-900
carloscardonha@br.ibm.com

Andre A. Cire
Department of Management, University of Toronto Scarborough, Toronto, Ontario M1C-1A4, Canada,
acire@utsc.utoronto.ca

Arvind U. Raghunathan
Mitsubishi Electric Research Labs, 201 Broadway, Cambridge,
raghunathan@merl.com

A graph is chordal if every cycle of length at least four contains a chord, that is, an edge connecting two
nonconsecutive vertices of the cycle. Several classical applications in sparse linear systems, database management, computer vision, and semidefinite programming can be reduced to finding the minimum number
of edges to add to a graph so that it becomes chordal, known as the minimum chordal completion problem
(MCCP). In this article we propose a new formulation for the MCCP which does not rely on finding perfect
elimination orderings of the graph, as has been considered in previous work. We introduce several families
of facet-defining inequalities for cycle subgraphs and investigate the underlying separation problems, showing that some key inequalities are NP-Hard to separate. We also show general properties of the proposed
polyhedra, indicating certain conditions and methods through which facets and inequalities associated with
the polytope of a certain graph can be adapted in order to become valid and eventually facet-defining for
some of its subgraphs or supergraphs. Numerical studies combining heuristic separation methods based on
a threshold rounding and lazy-constraint generation indicate that our approach substantially outperforms
existing methods for the MCCP, solving many benchmark graphs to optimality for the first time.
Key words : Networks/graphs; Applications: Networks/graphs ; Programming: Integer: Algorithms:
Cutting plane/facet
History :

1

Bergman et al.: On the Minimum Chordal Completion Polytope
Article submitted to ; manuscript no. (Please, provide the manuscript number!)

2

1.

Introduction

Given a simple undirected graph G = (V, E), the minimum chordal completion problem (MCCP)
asks for the minimum number of edges to add to E so that the graph becomes chordal ; that is,
every cycle of length at least four in G has an edge connecting two non-consecutive vertices (i.e.,
a chord ). Figure 1(b) depicts an example of a minimum chordal completion of the graph in Figure
1(a), where a chord {v1 , v3 } is added because of the chordless cycle (v0 , v1 , v4 , v3 ). The problem is
also referred to as the minimum triangulation problem or the minimum fill-in problem.
The MCCP is a classical combinatorial optimization problem with a variety of applications spanning both the computer science and the operations research literature. Initial algorithmic aspects
for directed graphs were investigated by Rose et al. (1976) and Rose and Tarjan (1978), motivated
by problems arising in Gaussian elimination of sparse linear equality systems. The most general
version of the MCCP was only proven NP-Hard later by Yannakakis (1981), and since then minimum graph chordalization methods have been applied in database management (Beeri et al. 1983,
Tarjan and Yannakakis 1984), sparse matrix computation (Grone et al. 1984, Fomin et al. 2013),
artificial intelligence (Lauritzen and Spiegelhalter 1990), computer vision (Chung and Mumford
1994), and in several other contexts; see, e.g., the survey by Heggernes (2006). Most recently, solution methods for the MCCP have gained a central role in semidefinite and nonlinear optimization,
in particular for exploiting sparsity of linear and nonlinear constraint matrices (Nakata et al. 2003,
Kim et al. 2011, Vandenberghe and Andersen 2015).
The literature on exact computational approaches for the MCCP is, however, surprisingly scarce.
A large stream of research in the computer science community has focused on the identification of
polynomial-time algorithms for structured classes of graphs, such as the works by Chang (1996),
Broersma et al. (1997), Kloks et al. (1998), and Bodlaender et al. (1998). For general graphs,
Kaplan et al. (1999) proposed the first exact fixed-parameter tractable algorithm for the MCCP,
and recently Fomin and Villanger (2012) presented a substantially faster procedure with subexponential parameterized time complexity. Such algorithms are typically extremely challenging
to implement and have not been used in computational experiments involving existing datasets.

Bergman et al.: On the Minimum Chordal Completion Polytope
Article submitted to ; manuscript no. (Please, provide the manuscript number!)

v1

v0

Figure 1

v2

3

v1

v4

v0

v2

v1

v4

v0

v2

v3

v3

v3

(a)

(b)

(c)

v4

(a) An example graph by Heggernes (2006). (b) A minimum chordal completion of the graph. (c) A
minimal, non-optimal chordal completion of the graph.

In regards to practical optimization approaches, the primary focus has been on heuristic methodologies with no optimality guarantees, including techniques by Mezzini and Moscarini (2010),
Rollon and Larrosa (2011), and Berry et al. (2006, 2003). The state-of-the-art heuristic, proposed
by George and Liu (1989), is a simple and efficient algorithm based on ordering the vertices by
their degree. Previous articles have also developed methodologies for finding a minimal chordal
completion. Note that a minimal chordal completion is not necessarily minimum, as depicted in
Figure 1(c), but does provide a heuristic solution to the MCCP.
To the best of our knowledge, the first mathematical programming model for the MCCP is
derived from a simple modification of the formulation by Feremans et al. (2002) for determining
the tree-widths of graphs. The model is based on a result by Fulkerson and Gross (1965), which
states that a graph is chordal if and only it has a perfect elimination ordering, to be detailed further
in this paper. Yüceoğlu (2015) has recently provided a first polyhedral analysis and computational
testing of this formulation, deriving facets and other valid inequalities for specific classes of graphs.
Alternatively, Bergman and Raghunathan (2015) introduced a Benders approach to the MCCP
that relies on a simple class of valid inequalities, outperforming a simple constraint programming
backtracking search algorithm.
Our Contributions In this paper we investigate a novel computational approach to the MCCP
that extends the preliminary work of Bergman and Raghunathan (2015). Our technique is based
on a mathematical programming model composed of exponentially many constraints – the chordal

Bergman et al.: On the Minimum Chordal Completion Polytope
Article submitted to ; manuscript no. (Please, provide the manuscript number!)

4

inequalities – that are defined directly on the edge space of the graph and do not depend on the
perfect elimination ordering property, as opposed to earlier formulations. We investigate the polyhedral structure of our model, which reveals that the proposed inequalities are part of a special class
of constraints that induce exponentially many facets for cycle subgraphs. This technique can be
generalized to lift other inequalities and greatly strengthen the corresponding linear programming
relaxation.
Building on these theoretical results, we propose a hybrid solution method that alternates a lazyconstraint generation with a heuristic separation procedure. The resulting approach is compared to
the current state-of-the-art models in the literature, and it is empirically shown to improve solution
times and known optimality gaps for standard graph benchmarks, often by orders of magnitude.
Organization of the Paper. After introducing our notation in §2, in §3 we describe a new integer
programming (IP) formulation for the MCCP and characterize its polytope in §4, also proving
dimensionality results and simple upper bound facets. §5 provides an in-depth analysis of the polyhedral structure of cycle graphs, introducing four classes of facet-defining inequalities. In §6 we
prove general properties of the polytope, including some results relating to the lifting of facets.
Finally, in §7 we propose a hybrid solution technique that considers both a lazy-constraint generation and a heuristic separation method based on a threshold rounding procedure, and also present
a simple primal heuristic for the problem. We provide a numerical study in §8, indicating that
our approach substantially outperforms existing methods, in particular solving many benchmark
graphs to optimality for the first time.

2.

Notation and Terminology

For the remainder of the paper, we assume that each graph G = (V, E) is connected, undirected,

and does not contain self-loops or multi-edges. For any set S, S2 denotes the family of two-element

subsets of S. Each edge e ∈ E ⊆ V2 is a two-element subset of vertices in V . The complement edge

set (or fill edges) E c of G is the set of edges missing from G, that is, E c = V2 \E. We denote by
m and mc the cardinality of the edge set and of the complement edge set of G, respectively (i.e.,

Bergman et al.: On the Minimum Chordal Completion Polytope
Article submitted to ; manuscript no. (Please, provide the manuscript number!)

5

m = |E | and mc = |E c |). The graph induced by a set V 0 ⊆ V is the graph G[V 0 ] = (V 0 , E 0 ) whose
0
edge set is such that E 0 = E ∩ V2 . If multiple graphs are being considered in a context, we include
“(G)” in the notation to avoid ambiguity; i.e., V (G0 ) and E(G0 ) represent the vertex and edge set
of a graph G0 , respectively. Moreover, for every integer k ≥ 0, we let [k] := {1, 2, . . . , k }.
For any ordered list C = (v0 , v1 , . . . , vk−1 ) of k distinct vertices of V , let V (C) = {v0 , v1 , . . . , vk−1 }
be the set of vertices composing C and let |V (C)| be the size |C | of C. The exterior of C is the
family
ext(C) = {{vk−1 , v0 }} ∪

[

{{vi−1 , vi }},

i∈[k−1]

and the interior of C is the family of two-element subsets of V (C) that do not belong to ext(C),
that is,



V (C)
int(C) =
\ ext(C).
2
We call C a cycle if ext(C) ⊆ E. If C is a cycle, any element of int(C) is referred to as a chord. A
cycle C for which the induced graph G[V (C)] contains no chords is a chordless cycle. G is said to
be chordal if the maximum size of any chordless cycle is three. A chordless cycle with k vertices is
called a k-chordless cycle.
Let G = (V, E). Every subset of fill edges F ⊆ E c is a completion of G, and G + F represents the
graph that results from the addition of edges in F to E; that is, G + F := (V, E ∪ F ). A chordal
completion of G is any subset of fill edges F ⊆ E c for which the completion G + F is chordal. A
minimal chordal completion F is a chordal completion such that, for any proper subset F 0 ⊂ F , F 0
is not a chordal completion for G. A minimum chordal completion is a minimal chordal completion
of minimum cardinality, and the minimum chordal completion problem (MCCP) is about the
identification of such a subset of E c .
Example 1. Consider the graph in Figure 1(a). This graph has three chordless cycles, C1 =
(v0 , v1 , v2 , v3 ), C2 = (v1 , v2 , v3 , v4 ) and C3 = (v0 , v1 , v4 , v3 ). Figure 1(c) shows a chordal completion
consisting of edges {v0 , v2 }, {v2 , v4 }, and {v0 , v4 }. Removing any of these edges will result in a graph
that is not chordal, so this chordal completion is minimal. Figure 1(b) shows a smaller minimal
chordal completion, a minimum chordal completion consisting only of edge {v1 , v3 }.

Bergman et al.: On the Minimum Chordal Completion Polytope
Article submitted to ; manuscript no. (Please, provide the manuscript number!)

6

3.

IP Formulation for the MCCP

We now describe the basic IP formulation investigated in this paper. Given a graph G = (V, E),
each binary variable xf in our model indicates whether the fill edge f ∈ E c is part of a chordal
c

completion for G. That is, if we define the set E(x) := {f ∈ E c : xf = 1} for each vector x ∈ [0, 1]m ,
the set of feasible solutions to our model is given by
n
o
c
X(G) := x ∈ {0, 1}m : G + E(x) is chordal .
Thus, each x ∈ X(G) equivalently represents the characteristic vector of a chordal completion
of G. We use G(x) to denote G + E(x), i.e., G(X) = (V, E ∪ E(x)), and x(F ) to represent the
characteristic vector of completion F ⊆ E c , i.e., x(F )f = 1 if f ∈ F and x(F )f = 0 otherwise.
Let C be the family of all possible ordered lists composed of distinct vertices of V , i.e., every C ∈ C
can be written as a sequence C = (v0 , v1 , . . . , vk−1 ) for some k ≤ |V |. Also, let FG (C) = F (C) ⊆ E c
be the set of fill edges that are missing in ext(C) for C to induce a cycle in G, that is,
F (C) := ext(C) \ E.
We propose the following model for the MCCP:

minimize

X

xf

(IPC)

f ∈E c


s.t.

X

xf − (|C | − 3) 

f ∈int(C)


X

xf − |F (C)| + 1 ≥ 0, for all C ∈ C ,

(I1)

f ∈F (C)

with int(C) ∩ E = ∅
c

x ∈ {0, 1}m .
The set of inequalities (I1) will be denoted by chordal inequalities henceforth. Note that every
sequence C such that F (C) = ∅ and int(C) ∩ E = ∅ describes a cycle in G, and its associated
inequality (I1) simplifies to
X

xf ≥ |C | − 3.

f ∈int(C)

Lemma 1 shows that inequalities (I1) are valid in this special case.

Bergman et al.: On the Minimum Chordal Completion Polytope
Article submitted to ; manuscript no. (Please, provide the manuscript number!)

7

Lemma 1. If C is a chordless cycle of G such that |C | ≥ 4, then any chordal completion of G
contains at least |C | − 3 edges that belong to int(C).
Proof.

We proceed by induction on k, the cardinality of sequence C = (v0 , v1 , . . . , vk−1 ). For

k = 4, if fewer than 4 − 3 = 1 edges (i.e., 0 edges) belonging to int(C) are added to G, the graph
trivially remains not chordal. Assume now k ≥ 5. By definition, any chordless completion of G
must contain at least one edge in int(C), so let us suppose without loss of generality that a chord
{v0 , vp } is added to G for some 1 < p < k − 1.

If p = 2 (or p = k − 2), then C 0 = (v0 , v2 , . . . , vk−1 ) is a chordless cycle of length k − 1. By the
inductive hypothesis, any chordal completion requires at least (k − 1) − 3 = k − 4 edges in int(C 0 )
(which are also in int(C)). By symmetry, the same analysis and result hold if p = k − 2. Therefore
any chordal completion of G employing chord {v0 , vp } for p = 2 (or p = k − 2) requires at least
1 + k − 4 = k − 3 edges in int(C).
Finally, let 3 ≤ p ≤ k − 3. In this case, chord {v0 , vp } cuts C and creates two chordless cycles:
C 1 = (v0 , v1 , . . . , vp ) and C 2 = (v0 , vp , vp+1 , . . . , vk−1 ). By the inductive hypothesis, any chordless
completion of G requires at least p − 3 edges in int(C 1 ) and at least k − p + 2 − 3 = k − p − 1 edges
in int(C 2 ); as int(C 1 ) ∩ int(C 2 ) = ∅ and int(C 1 ) ∪ int(C 2 ) ⊂ int(C), any chordal completion of G
employing chord {1, vp } for 3 ≤ p ≤ k − 3 also requires at least (1) + (p − 3) + (k − p − 1) = k − 3
edges in int(C), as desired.



Based on the previous lemma, we show below that the set of inequalities (I1) is valid for all
sequences in C and, as a consequence, that (IPC) is a valid formulation for the MCCP.
Proposition 1. The model (IPC) is a valid formulation for the MCCP.
Proof.

We first show that there is an one-to-one correspondence between X(G) and solutions

to (IPC). Let x∗ be a feasible solution to (IPC) and suppose that the graph G + E(x∗ ) contains
a chordless cycle C with more than 3 vertices. By definition,

∗
f ∈int(C) xf

P

= 0 < |C | − 3, thus

contradicting the feasibility of x∗ . Conversely, let E ∗ ⊆ E c be such that G + E ∗ is chordal, and
c

suppose x∗ = {x ∈ {0, 1}m : xf = 1 ⇔ f ∈ E ∗ } is infeasible to (IPC). Assume that one of the violated

Bergman et al.: On the Minimum Chordal Completion Polytope
Article submitted to ; manuscript no. (Please, provide the manuscript number!)

8

inequalities is associated with sequence C ∗ ; note that

P

f ∈F (C ∗ ) xf

= |F (C ∗ )|, as the associated

inequality would be trivially satisfied otherwise. Therefore, C ∗ is a cycle in G + E ∗ and we must
have

P

f ∈int(C ∗ ) xf

< |C | − 3, which, by Lemma 1, contradicts the fact that G + E ∗ is chordal.

Finally, since the one-to-one correspondence holds and the objective function of (IPC) minimizes
the number of added edges, the result follows.

4.



MCCP Polytope Dimension and Simple Upper Bound Facets

This section begins our investigation of the convex hull of the feasible set of chordal completions
X(G), which will lead to special properties that can be exploited by computational methods for
the MCCP. We identify the dimension of the polytope and provide a proof that the simple upper
bound inequalities xf ≤ 1 are facet-defining.
Theorem 1. If G = (V, E) is not a complete graph (and hence not trivially chordal),
a. conv(X(G)) is full-dimensional;
b. xf ≤ 1 is facet-defining for all f ∈ E c .
Proof.

c

c

We first show (a). Let e ∈ {0, 1}m be the vector consisting only of ones and ej ∈ {0, 1}m

be the unit vector for coordinate j. By definition, G + E(e) is the complete graph (which is
trivially chordal), whereas G + E(e − ej ) is the complete graph with only the edge associated with
coordinate j missing. Graphs G + E(e − ej ) are chordal for every ej ; this follows because the graph

induced by the set of vertices in any cycle C of cardinality k ≥ 4 contains at least k2 − 1 edges

2
and, consequently, |int(C)| ≥ k2 − 1 − k = k −3k−2
, which is greater than or equal to 1 for k ≥ 4.
2
c

The set of mc + 1 vectors {e} ∪ {e − e1 , e − e2 , . . . , e − em } is affinely independent and contained in
the set X(G), and so it follows that conv(X(G)) is a full-dimensional polytope.
0

For (b), let f ∈ E c and notice that the set of mc vectors {e} ∪ {e − ef : f 0 ∈ E c \ {f }} is affinely
independent and satisfy xf = 1.

5.



Cycle Graph Facets

We restrict our attention now to cycle graphs, i.e., graphs consisting of a single cycle. Cycle graphs
are the building blocks of computational methodologies for the MCCP, since finding a chordal

Bergman et al.: On the Minimum Chordal Completion Polytope
Article submitted to ; manuscript no. (Please, provide the manuscript number!)

9

completion of a graph naturally concerns identifying chordless cycles and eliminating them by
adding chords. We present four classes of facet-defining inequalities for cycle graphs in this section.
Let G = (V, E) be a cycle graph associated with a k-vertex chordless cycle C = (v0 , . . . , vk−1 ), i.e.,
V = V (C) and E = ext(C). Assume all additions and subtractions involving indices of vertices are
modulo-k. The proofs presented in this section show only the validity of the inequalities; arguments
proving that they are facet-defining for cycle graphs are presented in Section EC.1.
Proposition 2. Let G = (V, E) be a cycle graph associated with cycle C = (v0 , . . . , vk−1 ), k ≥ 4.
The chordal inequality (I1) associated with C, which in this case simplifies to
X

xf ≥ |C | − 3,

f ∈int(C)

is facet-defining for conv(X(G)).



The proof of the validity of the inequality in Proposition 2 follows directly from Lemma 1.
Proposition 3. If k ≥ 4, the inequality
X

x{vi−1 ,vi+1 } +

xf ≥ 1,

for all i ∈ {1, . . . , k }

(I2)

f :vi ∈f,{vi−1 ,vi+1 }∩f =∅

is valid and facet-defining for conv(X(G)).
Suppose that (I2) is violated by some x ∈ conv(X(G)), i.e., that for some {vi−1 , vi , vi+1 } ⊂
P
V , x{vi−1 ,vi+1 } + f :vi ∈f,{vi−1 ,vi+1 }∩f =∅ xf = 0. As k ≥ 4, a shortest path P from vi−1 to vi+1 in G(x)
Proof.

that does not include vi traverses at least two edges. The sequence defined by the concatenation
of P with (vi−1 , vi , vi+1 ) defines thus a k 0 -chordless cycle of G(x) for k 0 ≥ 4, a contradiction.



For the next proposition, some additional notation is in order. For any two vertices vi and vj
with i < j, let dC (vi , vj ) := min{j − i, k − j + i} be the “distance” between vi and vj in C, and
assume dC (vi , vj ) := dC (vj , vi ) if i > j.
Proposition 4. If k ≥ 5, the inequality
X
f ∈{{vi ,vj }∈E c : dC (vi ,vj )=2}

is valid and facet-defining for conv(X(G)).

xf ≥ 2

(I3)

Bergman et al.: On the Minimum Chordal Completion Polytope
Article submitted to ; manuscript no. (Please, provide the manuscript number!)

10

Proof.

Inequality (I3) states that at least two out of the |C | pairs of vertices of distance 2 must

appear in any chordal completion of G. Without loss of generality, let f 0 = {v0 , vj1 } be the edge of
int(C) composing some completion F of G that connects the “closest” vertices with respect to dC .
If j1 ≥ 3, then C 0 = (v0 , v1 , . . . , vj1 ) is a chordless cycle in G + F , a contradiction; therefore, j1 = 2.
As k ≥ 5, C 0 = (v0 , v2 , v3 , . . . , vk−1 ) is a chordless cycle in G + F with at least 4 vertices, so at least
one edge of int(C 0 ) must be present in G + F . Let f 00 = {vi0 , vj0 2 } be the edge of int(C 0 ) that connects
the “closest” vertices with respect to dC 0 . An argument similar to the one used above shows that f 00
connects two vertices of distance 2 in C 0 , so we have two cases to analyse. First, if f 00 6= {v0 , v2 }, the
result follows directly. Otherwise, we either have |C 0 | = 4, in which case dC 0 (v0 , v2 ) = dC (v0 , v2 ) = 2,
as desired, or we have a chordless cycle C 00 = (v0 , v3 , . . . , vk−1 ) in G + F with at least 4 vertices,
on which we can apply the same arguments; as an eventual sequence of cycles emerging from this
construction will eventually lead to a cycle of length 4, the result holds.



Proposition 5. If k ≥ 5, the inequality
X

xf ≥ |C | − 4,

for all i, j ∈ {1, . . . , k }, dC ({vj , vi }) ≥ 2

(I4)

f ∈int(C) \ {{vj−1 ,vj+1 },{vj ,vi }}

is valid and facet defining for conv(X(G)).
Proof.

Given vertices vi and vj such that dC ({vj , vi }) ≥ 2, inequality (I4) enforces the inclusion

of at least |C | − 4 edges of int(C) \ {{vj−1 , vj+1 }, {vj , vi }} in any chordal completion of G. Without
loss of generality, let j = 0 and let i be any value in [2, k − 3]. Suppose by contradiction that there
exists x0 ∈ X(G) such that
X

x0f < |C | − 4.

(1)

f ∈int(C) \ {{vk−1 ,v1 },{v0 ,vi }}

By Lemma 1, we have that
X

x0f ≥ |C | − 3.

f ∈int(C)

This implies that

x0vk−1 ,v1

=

x0v0 ,vi

= 1, for otherwise inequality 1 would be violated. Thus, the

sequences C 1 = (v0 , v1 , . . . , vi ) and C 2 = (v0 , vi , vi+1 , . . . , vk−1 ) are cycles in G(x0 ). Again, by

Bergman et al.: On the Minimum Chordal Completion Polytope
Article submitted to ; manuscript no. (Please, provide the manuscript number!)

11

Lemma 1, at least C ` − 3 fill edges must be present in int(C ` ), ` = 1, 2. This is only possible if at
least i − 2 edges of int(C 1 ) and at least |C | − i − 2 edges of int(C 2 ) belong to the set of fill edges
described by x0 . As int(C 1 ) ∩ int(C 2 ) = ∅ and int(C 1 ) ∪ int(C 2 ) ⊆ int(C), we have that
X

x0f ≥

f ∈int(C) \ {{vi−1 ,vi+1 },{v0 ,vi }}

contradicting thus inequality (1).

X
f ∈int(C 1 )

x0f +

X

x0f ≥ |C | − 4,

f ∈int(C 2 )



Example 2. Let G be a cycle graph associated with 6-cycle C = (v0 , v1 , v2 , v3 , v4 , v5 ). An example
of inequality (I2) with i = 1 is

x{v0 ,v2 } + x{v1 ,v3 } + x{v1 ,v4 } + x{v1 ,v5 } ≥ 1,
which enforces the inclusion of at least one edge f = {v1 , vk }, k ∈ {3, 4, 5}, for every chordal completion of G that does not contain edge (v0 , v2 ).
Inequality (I3) translates to
x{v5 ,v1 } + x{v0 ,v2 } + x{v1 ,v3 } + x{v2 ,v4 } + x{v3 ,v5 } + x{v4 ,v0 } ≥ 2,
which enforces that at least 2 of the 6 pairs of vertices that are separated by one vertex must
appear in any chordal completion of G.
Finally, inequality (I4) for i = 4 and j = 1 is given by
x{v0 ,v3 } + x{v0 ,v4 } + x{v1 ,v3 } + x{v1 ,v5 } + x{v2 ,v4 } + x{v2 ,v5 } + x{v3 ,v5 } ≥ 2,
which enforces that at least 2 of the edges in int(C) \ {{v0 , v2 }, {v1 , v4 }} must be included in any
chordal completion of G.

6.

General Polyhedral Properties

This section provides theoretical insights into the polyhedral structure of the MCCP polytope. In
particular, the first result, provided in Theorem 2, shows that any inequality proven to be valid
on an induced subgraph can be extended into a valid inequality for the original graph. This result

Bergman et al.: On the Minimum Chordal Completion Polytope
Article submitted to ; manuscript no. (Please, provide the manuscript number!)

12

is important for the development of practical solution methodology because it shows that finding
valid inequalities/facets on particular substructures, such as cycles, can help in the generation of
valid inequalities for larger graphs containing these substructures. Theorem 3 shows how facets
for cycles can be lifted to facets of graphs that are subgraphs of cycles, leading to the result in
Corollary 1 relating to when the inequalities (I1) in their general form in model (IPC) are facetdefining. The final result of the section, Theorem 4, proves and describes how facets for small cycles
can be lifted to facets of larger cycles.
First, we show a lemma that will be used in the proof of Theorem 2.
Lemma 2. If G = (V, E) is chordal, then G[W ] is chordal for any W ⊆ V .
Proof.

A chordless cycle C in G[W ] must be a chordless cycle in G. Thus, if G[W ] is not chordal,

then G cannot be as well.



Theorem 2. Let G = (V, E) be an arbitrary graph and W ⊆ V be any subset of vertices. If
a0 x0 ≥ b is a valid inequality for X(G[W ]), then ax ≥ b is a valid inequality for X(G), where af = a0f
if f ∈ E C (G[W ]) and af = 0 otherwise.
Proof.

By way of contradiction, suppose that a0 x0 ≥ b is valid for X(G[W ]) and let F be a

chordal completion of G such that ax(F ) < b. From the construction of a, we have ax(F ) = a0 x(F ∩
E(G[W ])) < b, and by Lemma 2, G[W ] + F ∩ E(G[W ]) must be chordal and, consequently, we must
have a0 x(F ∩ E(G[W ])) ≥ b, establishing thus a contradiction.



We now present a result that goes in the opposite direction of Theorem 2. Namely, it shows how
facet-defining inequalities for a cycle graph G can be transformed into facet-defining inequalities
for subgraphs of G; note that subgraphs of cycle graphs consist of collections of paths. This result
allows us to show that inequality (I1) is facet-defining for subgraphs of cycle graphs.
Theorem 3. Let G0 = (V, E 0 ) be a cycle graph associated with the cycle C = (v0 , v1 , . . . , vk−1 ) ∈ C
and G = (V, E) be a subgraph of G0 such that G0 = G + FG (C), FG (C) = E 0 \ E. If ax ≥ b is

Bergman et al.: On the Minimum Chordal Completion Polytope
Article submitted to ; manuscript no. (Please, provide the manuscript number!)

v0

v1

v0

v4

Figure 2

13

v2

v1

v4

v2

v3

v3

(a)

(b)

(a) A graph G with V = {v0 , v1 , v2 , v3 , v4 } and E = {{v0 , v1 }, {v3 , v4 }}. Solid lines represent graph edges
and dashed lines are fill edges whose addition to G makes a chordal cycle of length 5. (b) Cycle graph
with 5 vertices.

C

facet-defining for conv(X(G0 )), a ≥ 0, and a0 ∈ R|E | , with a0f = af if f ∈ E C \ FG (C) and a0f = 0
otherwise, the inequality

a0 x ≥ b 


X

xf − |FG (C)| + 1

f ∈FG (C)

is facet-defining for conv(X(G)).



Theorem 3 (proved in Section EC.2) immediately leads to the following result:
Corollary 1. For any graph G = (V, E) and for any sequence C ∈ C such that int(C) ∩ E = ∅,
the chordal inequality (I1) is facet-defining for the MCCP polytope of G[V (C)].
Example 3. Consider the graph G in Figure 2(a); solid lines represent graph edges in this
example. As in the statement of Theorem 3, we have
C = (v0 , v1 , v2 , v3 , v4 ) , E(G) = {{v0 , v1 }, {v3 , v4 }} , and FG (C) = {{v1 , v2 }, {v2 , v3 }, {v4 , v0 }} .
Graph G + F (C) is 5-chordless cycle. One facet-defining inequality for this cycle, according to
Proposition 2, is the simplified version of the chordal inequality, given by
x{v0 ,v2 } + x{v0 ,v3 } + x{v1 ,v3 } + x{v1 ,v4 } + x{v2 ,v4 } ≥ 2.
Corollary 1 stipulates that the inequality below is facet defining for G:

x{v0 ,v2 } + x{v0 ,v3 } + x{v1 ,v3 } + x{v1 ,v4 } + x{v2 ,v4 } ≥ 2 · x{v1 ,v2 } + x{v2 ,v3 } + x{v4 ,v0 } − 3 + 1 .
By Theorem 2, these inequalities will also be valid even if G is a subgraph of a larger graph.

Bergman et al.: On the Minimum Chordal Completion Polytope
Article submitted to ; manuscript no. (Please, provide the manuscript number!)

14

vi

f∗

ax ≥ b
vj

Figure 3

Depiction of inequality lifting from Theorem 4.

We now define a method for lifting facet-defining inequalities defined on smaller cycles into
facet-defining inequalities for large cycles. This is done by considering the inclusion of chords into
the inequalities, which reveals a lifting property of MCCPs that can be used to strengthen known
inequalities. We present this result in Theorem 4, which is proved in Section EC.2.
Theorem 4. Let G = (V, E) be a cycle graph associated with the cycle C = (v0 , v1 , . . . , vk−1 ) and
let f ∗ = {vs , vt } ∈ E c , 0 ≤ s < t ≤ k − 1, be any chord of C. If the inequality ax ≥ b, a ≥ 0, is
facet-defining for the MCCP polytope of cycle graph G0 = (V 0 , E 0 ) associated with the cycle C 0 =
(vs , vs+1 , . . . , vt ) (i.e., G0 = G[V (C 0 )] + {f ∗ }), then
a0 x ≥ b · x f ∗
is facet-defining for conv(X(G)), where a0f = af if f ∈ int(C 0 ) and a0f = 0 otherwise.



Figure 3 provides a depiction of Theorem 4. If ax ≥ b is facet-defining for any induced subcycle
obtained by adding edge f ∗ , then ax ≥ b · xf ∗ will be facet-defining for the original cycle graph.
Example 4. Consider the graph in Figure 2(b), and let G0 = G[{v1 , v2 , v3 , v4 }] + {{v1 , v4 }} be a
cycle graph associated with cycle C 0 = (v1 , v2 , v3 , v4 ). From Proposition 2, we have that the following
chordal inequality is facet-defining for conv(X(G0 )):
X
f ∈int(C 0 )

xf = x{v1 ,v3 } + x{v2 ,v4 } ≥ |C 0 | − 3 = 1.

Bergman et al.: On the Minimum Chordal Completion Polytope
Article submitted to ; manuscript no. (Please, provide the manuscript number!)

15

This inequality can be modified in order to become facet-defining for conv(X(G)) through Theorem 4, yielding

x{v1 ,v3 } + x{v2 ,v4 } ≥ x{v1 ,v4 } =⇒ x{v1 ,v3 } + x{v2 ,v4 } − x{v1 ,v4 } ≥ 0.

7.

Solution Method for the MCCP

We now describe a procedure to solve formulation (IPC) for general graphs based on the structural
results showed in the previous sections. Since the model has exponentially many constraints, our
solution technique is based on a hybrid branch-and-bound procedure that applies separation, lazyconstraint generation, and a primal heuristic to the problem.
7.1.

Separation complexity

Given a graph G = (V, E), we first consider the problem of identifying inequalities violated by a
c

completion of G. Recall that, for a vector x ∈ {0, 1}m , we define E(x) := {f ∈ E c : xf = 1}.
c

Proposition 6. Let x∗ ∈ {0, 1}m be a solution vector and G0 = (V, E 0 ) = G + E(x∗ ). If G0 is
not chordal, then at least one inequality of each family (I1)-(I3) (and possibly one of family (I4))
violated by x∗ can be found in O(|V |3 (|E 0 | + |V | log |V |)).
Proof.

An immediate consequence of Proposition 1 is that some inequality (I1) is violated if and

only if G0 has a chordless cycle. Such a cycle can be identified according to the following procedure:
For each triple of vertices (v, w, u) in V such that {{v, w}, {w, u}} ⊆ E 0 and {v, u} 6∈ E 0 , find the
shortest path p between v and u that does not traverse w. If such a path exists, cycle C := (p, w) is
chordless and has length at least 4. Given such a chordless cycle C, one violated inequality of each
type (I1)-(I3) (and type (I4) as well if |C | ≥ 5) can be derived in linear time in |C |. Since there are
|V |3 triples and the shortest path between u and v (that does not include w) can be found using

Dijkstra’s algorithm in time O(|E 0 | + |V | log |V |) (Cormen et al. 2009), the result follows.



The separation problem of (I1)-(I4) over fractional points is, however, much more challenging.
We state the results below concerning this question.

Bergman et al.: On the Minimum Chordal Completion Polytope
Article submitted to ; manuscript no. (Please, provide the manuscript number!)

16

c

Theorem 5. Given a fractional point x∗ ∈ [0, 1]m :
a. The separation problem of (I1) is NP-Complete.
b. Inequalities (I2) can be separated in O(|V |5 ).
c. Inequalities (I3) can be separated in O(|V |8 ).
d. The separation problem of (I4) is NP-Complete.
Proof.

Due to space limitations, we present below only proof sketches for these results. The full

version of each proof is presented in Section EC.3 of the online supplement.
a. The proof reduces the quadratic assignment problem (QSCP), a classical and well-studied
NP-hard problem, to the α-quadratic shortest cycle problem (α-QSCP), introduced in this paper.
In the QSCP, we are given a graph G = (V, E) and a quadratic cost function q : V × V → [0, 1], with
q(u, v) = 0 if (u, v) ∈ E. A feasible solution of QSCP is a simple chordless cycle C = (v1 , v2 , . . . , v|C| )
whose cost is p(C) =

P

{u,v}∈E(G[C])C

q(u, v) − |C |. The α-QSCP is the decision version of QSCP

in which the goal is to decide whether G has a simple chordless cycle C such that p(C) < α. We
employ a reduction of the quadratic assignment problem to (−3)-QSCP that resembles the ones
used by Rostami et al. (2015) for the quadratic shortest path problem. Finally, the −3-QSCP is
reduced to the problem of separating the inequality (I1), completing the proof.
b. An auxiliary graph G0 , a complete digraph on |V (G)| nodes, is constructed for which the
separation problem is reduced to finding, for every triple of vertices (v1 , v2 , v3 ), the shortest path
from v1 to v3 that does not include v2 . The number of sequences for which this verification needs to
be performed is O(|V (G)|3 ), and the identification of such a path can be made in time O(|V (G)|)2 .
c. As in b, An auxiliary graph G0 , specifically a complete digraph on |V (G)|2 nodes, is
constructed for which the separation problem is reduced to finding at most O(|V (G)|4 ) shortest
paths, each of which can be performed in polynomial time.
d. The proof is similar to that of a, except that we use a reduction from −4-QSCP*, a slight
variant of −3-QSCP.



Bergman et al.: On the Minimum Chordal Completion Polytope
Article submitted to ; manuscript no. (Please, provide the manuscript number!)

7.2.

17

Heuristic separation algorithms

In view of Proposition 6 and Theorem 5, we tackle model (IPC) by applying a typical branch-andbound procedure that alternates between heuristic separation and lazy-constraint generation.
For the lazy generation part, at every integer node of the branching tree we apply the procedure
presented in the proof of Proposition 6 to separate at least one violated inequality (I1)-(I4), similar
to a combinatorial Benders methodology (Codato and Fischetti 2006). Propositions 1 and 6 ensures
that this approach yields an (feasible and) optimal solution to (IPC), since a violated inequality is
not found if and only if the resulting graph is chordal.
Nonetheless, adding violated inequalities only at integer points typically yield weak bounds
at intermediate nodes of the branching tree. Since a complete separation of fractional points is
not viable due to Theorem 5, we consider a heuristic threshold procedure. Namely, given a point
c

x∗ ∈ [0, 1]m and a threshold δ ∈ (0, 1), let
E δ (x) := {f ∈ E c : xf ≥ δ } .
We can use the procedure from Proposition 6 to find violating inequalities for the graph G + E δ (x∗ ).
Such inequalities may not be necessarily violated by x∗ , and require thus a (simple) extra verification testing step. Even though the threshold policy does not guarantee that at least one violated
inequality is found, it can be performed efficiently and, as our numerical experiments indicate, it
is a fundamental component for the good performance of the proposed solution technique.
7.3.

Primal Heuristic

We have also incorporated a primal heuristic to be applied at infeasible integer nodes of the
branching tree. The method is based on the state-of-the-art heuristic for the problem, designed
by George and Liu (1989). Specifically, the vertices of the graph are sorted in ascending order
according to their degree, thereby defining a sequence S = (v1 , v2 , . . . , v|V | ). The vertices are then
picked one at a time, in the order indicated by S. For each vertex vi , edges are added to G so
that S defines a perfect elimination ordering, i.e., vi and its neighbours on set {vi+1 , vi+2 , . . . , v|V | }
induce a clique, which makes G chordal. This procedure has complexity O(|V |2 |E |).

Bergman et al.: On the Minimum Chordal Completion Polytope
Article submitted to ; manuscript no. (Please, provide the manuscript number!)

18
c

For any integer point x ∈ {0, 1}m found during the branch-and-bound procedure, if G0 := G +
E(x) is not chordal, we can apply George and Liu (1989)’s heuristic in order to chordalize G0
and obtain a feasible solution to the problem. The application of this procedure at the root node
ensures we can identify solutions which are at least as good as those provided by the heuristic.

8.

Numerical Experiments

In this section we present an experimental evaluation of the solution methods introduced in this
paper. The experiments ran on an Intel(R) Xeon(R) CPU E5-2640 v3 at 2.60GHz with 128 GB
RAM. We used the integer programming solver IBM ILOG CPLEX 12.6.3 (IBM ILOG 2016) in
all experiments, with a time-limit of 3,600 seconds and one thread.
8.1.

Instances

Four family of instances were used for the experimental evaluation: relaxed caveman graphs, grid
graphs, queen graphs, and DIMACS graphs. They are described as follows.
Relaxed caveman graphs (Judd et al. 2011) represent typical social networks, where small pockets of individuals are tightly connected and have sporadic connections to other groups. This family
of instances has been employed previously in the evaluation of algorithms for combinatorial optimization problems (Bergman and Cire 2016). Each instance is generated randomly based on three
parameters, α, β ∈ Z+ and γ ∈ (0, 1). Starting from a set of β disjoint cliques of size α, each edge is
examined and, with probability γ, one of its endpoints is switched to a vertex belonging to another
clique; all operations are made uniformly at random. An example of a relaxed caveman graph is
depicted in Figure 4, where α = β = 6 and γ = 0.2.
The structure of relaxed caveman graphs is particularly useful for evaluating algorithms for
chordal completions. Namely, the modifications in the edges lead to large chordless cycles, enforcing
thus the inclusion of several edges in chordal completions. For our experiments, ten instances of
each possible configuration involving α, β ∈ {4, 5, 6, 7, 8} and γ = 0.30 were generated. This set of
graphs will be henceforth denoted simply by caveman instances.
The next set of instances, grid graphs, correspond to graphs whose node set can be partitioned
into a set of r rows R1 , . . . , Rr and c columns C1 , . . . , Cc . Each vertex is denoted by vr,c if vr,c ∈

Bergman et al.: On the Minimum Chordal Completion Polytope
Article submitted to ; manuscript no. (Please, provide the manuscript number!)

Figure 4

19

Relaxed caveman graph. Picture from Judd et al Judd et al. (2011).

Rr ∩ Cc . Vertices vi,j and vk,l are adjacent if and only if either i = k and |j − l| = 1, or j = l and
|i − k | = 1. Note that grid graphs also contain large chordless cycles.

We also used queen graphs for our experiments. The queen graphs are extensions of grid graphs
with additional edges representing longer hops as well as diagonal movements. More precisely, there
exists an edge connecting vi,j to vi0 ,j 0 if and only if one of the three following conditions is satisfied
for some k: (1) i = i0 ± k and j = j 0 ± k, (2) i = i0 and j = j 0 ± k, or (3) i = i0 ± k and j = j 0 . The
configurations of grid graphs and of queen graphs used in our experiments are equivalent to those
used by Yüceoğlu (2015).
The final set of instances consists of the classical DIMACS graph coloring instances, which can
be downloaded from http://dimacs.rutgers.edu/Challenges/. These instances are frequently used
in computational evaluations of graph algorithms.
8.2.

Other Approaches

The state-of-the-art approaches to the MCCP reported in the literature are a branch-and-cut
approach by Yüceoğlu (2015) and a Benders decomposition approach by Bergman and Raghunathan (2015), henceforth denoted by YUC and BEN, respectively.
YUC is based on a perfect elimination ordering (PEO) model of the MCCP. The model finds a
PEO that minimizes the number of fill-in edges, and can be written as follows.
min

X

yij + yji

(i,j)∈E c

s.t.

xij + xji = 1,

for all {i, j } ∈ E

(2)

Bergman et al.: On the Minimum Chordal Completion Polytope
Article submitted to ; manuscript no. (Please, provide the manuscript number!)

20

for all {i, j } ∈ E c

(3)

xij + xjk − xik ≤ 1,

for all i, j, k ∈ V, i 6= j, j 6= k, i 6= k

(4)

yij ≤ xij , yji ≤ xji ,

for all i, j ∈ V, i 6= j

(5)

yij = xij , yji = xji ,

for all {i, j } ∈ E

(6)

for all i, j, k ∈ V, i 6= j, j 6= k, i 6= k

(7)

for all i, j ∈ V, i 6= j

(8)

xij + xji ≤ 1,

xjk + yij + yik − yjk ≤ 2,
yij , xij ∈ {0, 1},

In the model above, denoted by PEO, a binary variable yij indicates whether edge {i, j } is added to G
and binary variable xij indicates whether vertex i precedes j in the resulting ordering. Constraints
(2) enforce the existence of a precedence relation between vertices i and j if {i, j } ∈ E, whereas
constraints (3) prevent i and j from preceding each other simultaneously in an elimination ordering.
Constraints (4) ensure the transitive closure of precedence relations is satisfied. Constraints (5)
and (6) indicate that a precedence relation between edges i and j can exist if and only if {i, j } ∈ E.
Finally, constraints (7) impose that the final ordering must be a perfect elimination ordering.
YUC employs a branch-and-cut approach that is based on a polyhedral analysis of the convex
hull of solutions to PEO. Additionally, the algorithm also considers valid inequalities for special
structured graphs, such as grid and queen graphs.
The other approach tested against is BEN, the precursor of the approach described in the present
work. In Bergman and Raghunathan (2015), a formulation consisting only of inequalities (I1) is
used in a pure Benders decomposition approach. That is, BEN solves to optimality an IP using the
current set of inequalities (I1) (i.e., the Benders cuts) found up to the current iteration. If the
solution contains no chordless cycles, its optimality is proven and the procedure stops. Otherwise,
a collection of chordless cycles is found and new Benders cuts (i.e., inequalities (I1) violated by the
current solution) are added to the model, and the procedure repeats.
Also of interest is to compare our approach with state-of-the-art heuristics in terms of solution
quality, assessing thus how significant the differences between exact and heuristic solutions are. We

Bergman et al.: On the Minimum Chordal Completion Polytope
Article submitted to ; manuscript no. (Please, provide the manuscript number!)

21

consider the state-of-the-art heuristic developed by George and Liu (1989) (described in Section
7.3), which will be henceforth denoted by MDO.
The methodology proposed in this paper will be henceforth denoted by BC, as it can also be
classified as a branch-and-cut algorithm.
8.3.

Algorithmic Enhancements

In the first set of experiments, we test the following algorithmic enhancements to BC: (1) using
only inequalities (I1) versus using all inequalities (I1)-(I4); (2) separating the inequalities only at
integer solutions or at each search-tree node; and (3) invoking MDO as a primal heuristic. In particular, BC-Base is an implementation of BC where only inequality (I1) is considered, the separation
algorithm is invoked only at integer search-tree nodes, and no primal heuristic is applied. BC-Enh
is an implementation of BC where all enhancements are applied. The caveman graphs are used for
this evaluation.
In order to verify whether an individual enhancement leads to a statistically significant reduction
in the solution times, a two-sample paired t-test was employed. Specifically, the null hypothesis
indicates whether the solutions times are equivalent with or without the enhancements. Solution
times can differ by orders of magnitude across the 250 instances of caveman graphs (e.g., 0.001
seconds versus nearly 3,600 seconds), so all comparisons were made in logarithmic scale, i.e., we
applied log(1 + t) transformations to run times t (given in seconds).
For enhancement (1), (2), and (3) taken individually, the tests resulted in a p-value of 0.070,
0.00057, and 0.0013, respectively. This shows that each enhancement provides considerable reductions in run time, with the heuristic being perhaps the most effective among them. When comparing
BC-Base versus BC-Enh, the test yields a p-value 0.0000067, showing strong statistical significance
of the results indicating reductions on run times caused by the enhancements.
A plot comparing the solution times of BC-Base and BC-Enh is provided in Figure 5. Each point in
the scatter plot of Figure 5(a) corresponds to one instance, with the radii indicating the sizes of the
cliques and the color representing the number of cliques (dark red/blue corresponding to instances

Bergman et al.: On the Minimum Chordal Completion Polytope
Article submitted to ; manuscript no. (Please, provide the manuscript number!)

22

with smallest/largest number of cliques, respectively). The x-axis is the run time in seconds in
log-scale for BC-Base and the y-axis contains the respective values for BC-Enh. Figure 5(b) presents
the cumulative distribution plot of performance of both algorithms, indicating in the y-axis how
many instances were solved within the amount of time indicated in the x-axis. Both figures shows
that BC-Enh typically outperforms BC-Base, which becomes more prominent with harder instances.

(a) Scatter plot
Figure 5

(b) Cumulative distribution plots of performance

Comparing BC with and without algorithmic enhancements on caveman graphs. (a) Scatter plot comparing solution times, with the size of the dot corresponding to the number of vertices in each clique and
the color (red to blue) the relative number of cliques. (b) Cumulative distribution plot of performance
showing number of instances solved by a certain time limit.

The algorithmic enhancements provide clear computational advantages, and so we use them for
the remaining experiments, referring to BC-Enh simply as BC.
8.4.

Comparison with Heuristics

In the second set of experiments, we investigate the improvements brought by BC upon the solutions
obtained alone by MDO. Note that, since BC uses MDO at the root and throughout search, the solutions
will always be at least as good as those achieved by MDO.
Our first comparison, involving the relaxed caveman graphs, is presented in Table 1. For each
configuration, the averages of the upper bounds provided by both BC and MDO are presented, as
well as the average percentage decreases in the upper bound from MDO to BC and the average times
to compute the chordal completion. As MDO achieves solutions in under a hundredth of a second in
all cases, its running times are not reported. These results readily show the advantage of seeking

Bergman et al.: On the Minimum Chordal Completion Polytope
Article submitted to ; manuscript no. (Please, provide the manuscript number!)

23

optimal solutions. The heuristic can be far from the optimal solution (eventually by up to 70%)
and, on the relaxed caveman graphs, the running time of BC is almost always small (only one
instance is not proven optimal within 3,600 seconds).
Table 1

Comparison between MDO and BC on caveman graphs.

α

β

BC UB

MDO UB

% Dec

BC Time

4

4

0.9

1.4

15

0

4

5

1.7

2.8

35.1

0

4

6

5.3

7.4

42.8

0

4

7

13.2

17.3

25.1

0

4

8

19

26.3

29.3

0

5

4

1.6

1.8

6.3

0

5

5

1.7

4.4

51.8

0

5

6

7.7

10.3

40.3

0

5

7

15.5

21.7

35.7

1.3

5

8

25.1

37.1

34.8

0.5

6

4

0.6

1.7

32.1

0

6

5

4.1

8.4

54.9

0

6

6

12.2

16.9

35.4

0.1

6

7

18.1

24.2

25.3

0.1

6

8

28.9

43

35.8

2.0

7

4

1.1

2.5

50.8

0

7

5

3.6

6.5

42.9

0

7

6

17.1

23.6

35.8

0.5

7

7

24.8

35.4

37.6

3.5

7

8

55.9

74.1

27.6

198.9

8

4

0.3

3.3

70.8

0

8

5

5.5

9.9

58.7

0

8

6

14.6

23.3

39.9

1.5

8

7

29.7

45

37.6

5.2

8

8

52.4

69.8

26.2

382.2

The same data for grid graphs, queen graphs, and DIMACS graphs are presented in Tables 2, 3,
and 4, respectively. These tables first report the graph characteristics, including number of vertices
and number of edges, and for all algorithms the resulting lower bounds, upper bounds, and solution
times (in seconds if solved to optimality in 3,600s, or a mark ”-” otherwise), respectively. Bold face
for the upper bound indicates that the algorithm found the best-known solution for the instance. In
general, BC can deliver better solutions than MDO but requires much more time in harder instances,
showing therefore the trade-off in computational time and solution quality.

Bergman et al.: On the Minimum Chordal Completion Polytope
Article submitted to ; manuscript no. (Please, provide the manuscript number!)

24

8.5.

Comparison with Other Techniques

This section provides a comparison of BC with YUC and BEN. For these evaluations, we employed all
instances reported upon in Yüceoğlu (2015) and Bergman and Raghunathan (2015) and compared
the solution times and objective function bounds obtained by all solution methods. The reported
numbers for YUC were obtained directly from Yüceoğlu (2015), who uses IBM ILOG CPLEX 12.2
and a processor with similar clock (2.53 GHz), but runs the parallel version of the solver with 4
cores, and not with 1 core, as we do in this work.
First, we report on grid graphs, which were used in the computational results of Yüceoğlu (2015)
for YUC. This approach enhances the PEO formulation with cuts tailored for graphs containing grid
structures, so these instances are particularly well-suited for YUC. The results are presented in
Table 2. BC typically finds the best-known solutions, and only in 4 cases out of 22 the relaxation
bound for YUC outperforms that of BC.
Next, Table 3 reports on queen graphs. As previously mentioned, these instances are also wellsuited to YUC because of their grid-like structures. Nonetheless, the results show that BC typically
outperforms YUC both in terms of optimality gap and solution time. In particular, for almost all
instances, the obtained solution is at least as good as the one found by YUC. In the only exception,
the solution obtained by BC contains only one fill edge more than YUC.
Finally, Table 4 reports on DIMACS graphs. The 12 instances above the double horizontal line
are those reported on in Yüceoğlu (2015), whereas the others are the remaining graphs in the
benchmark set with fewer than 150 vertices. Our results show that instances of the first group are
solved orders of magnitude faster by BC and, for those in which YUC was not able to prove optimality,
better objective function bounds are obtained. In particular, BC was able to close entirely the
optimality gap of four instances of this dataset that were still open: david, miles250, miles750,
and myciel5. These results can be explained by the fact that DIMACS graphs do not necessarily
have grid-like structures, which makes them more challenging for YUC. For the remaining instances,
9 are solved to optimality and for many of the other instances, the best solutions obtained by BC
employed substantially fewer fill edges than those obtained by the traditional heuristic MDO.

Bergman et al.: On the Minimum Chordal Completion Polytope
Article submitted to ; manuscript no. (Please, provide the manuscript number!)

Table 2

25

Results for grid graphs. Note: Graph grid5 5 was not included in the results reported on in Yüceoğlu
(2015).
Instance

YUC

BC

MDO

name

|V |

|E|

LB

UB

t

LB

UB

t

UB

grid3 3

9

12

5

5

0.01

5

5

0

5

grid3 4

12

17

9

9

0

9

9

0.01

9

grid3 5

15

22

13

13

0.02

13

13

0.07

13

grid3 6

18

27

17

17

0.02

17

17

0.17

17

grid3 7

21

32

21

21

0.01

21

21

0.22

21

grid3 8

24

37

25

25

0.02

25

25

1.39

25

grid3 9

27

42

29

29

0.02

29

29

9.13

33

grid3 10

30

47

33

33

0.03

33

33

20.39

37

grid4 4

16

24

18

18

1.23

18

18

2.33

18

grid4 5

20

31

25

25

18.11

25

25

8.35

25

grid4 6

24

38

32.2

34

-

34

34

216.71

34

grid4 7

28

45

39

41

-

41

41

304.85

41

grid4 8

32

52

45.5

52

-

48.2

50

-

50

grid4 9

36

59

52.5

58

-

54.2

57

-

57

grid4 10

40

66

59.3

66

-

59.1

66

-

66

grid5 5

25

40

*

*

*

37

37

115.98

37

grid5 6

30

49

46.2

53

-

48.7

50

-

52

grid5 7

35

58

56.9

65

-

56.5

62

-

68

grid5 8

40

67

67.5

77

-

65.2

75

-

80

grid5 9

45

76

33.3

90

-

73.2

89

-

93

grid6 6

36

60

60.9

77

-

59.2

69

-

71

grid6 7

42

71

31

94

-

69.1

88

-

92

grid7 7

49

84

37

125

-

80.3

112

-

119

We conclude this section by comparing our results with those presented in Bergman and Raghunathan (2015). With the exception of some queen instances, BC always provides better solutions
and objective bounds than BEN. In the exceptional cases, the bounds provided by BEN were slightly
better. Note also that BEN does not provide any feasible solution until the algorithm terminates.
8.6.

Cuts Found

This section provides an analysis of the types of cuts found by BC during the solution process
across all experiments. Figure 6 (a) shows an area plot depicting the distribution of the number of
inequalities of each type that was identified and added to the model in BC. We present only the 88
instances for which at least 10,000 cuts were added, where all graph classes were considered, and

Bergman et al.: On the Minimum Chordal Completion Polytope
Article submitted to ; manuscript no. (Please, provide the manuscript number!)

26
Table 3
Instance

Results for queen graphs.
YUC

BC

MDO

name

|V |

|E|

LB

UB

t

LB

UB

t

UB

queen3 3

9

28

5

5

0

5

5

0

5

queen3 4

12

46

12

12

0.01

12

12

0.01

12

queen3 5

15

67

22

22

0.31

22

22

0.03

22

queen3 6

18

91

36

36

1.03

36

36

0.25

36

queen3 7

21

118

53

53

2.17

53

53

0.91

53

queen3 8

24

148

74

74

8.49

74

74

2.27

74

queen3 9

27

181

98

98

15.77

98

98

4.97

98

queen3 10

30

217

126

126

65.91

126

126

22.29

126

queen4 4

16

76

26

26

0.19

26

26

0.03

28

queen4 5

20

110

51

51

4.54

51

51

0.75

53

queen4 6

24

148

83

83

16.54

83

83

6.68

83

queen4 7

28

190

119

119

68.22

119

119

34.5

121

queen4 8

32

236

164

164

636.28

164

164

445.78

167

queen4 9

36

286

209.8

217

-

211.4

217

-

222

queen4 10

40

340

255.5

278

-

259.7

278

-

286

queen5 5

25

160

93

93

41.03

93

93

14.02

94

queen5 6

30

215

144

144

185.81

144

144

186.93

154

queen5 7

35

275

203.1

214

-

204.2

214

-

223

queen5 8

40

340

265.8

293

-

265.5

293

-

306

queen5 9

45

410

339.8

393

-

338.8

386

-

398

queen5 10

50

485

424.9

501

-

424

492

-

503

queen6 6

36

290

214.9

232

-

218.1

231

-

244

queen6 7

42

371

299.2

351

-

296.4

338

-

352

queen6 8

48

458

400.7

481

-

396.5

461

-

482

queen6 9

54

551

521.4

622

-

514.3

619

-

633

queen6 10

60

650

656.7

786

-

646.6

787

-

826

queen7 7

49

476

423.7

520

-

422.3

495

-

515

queen7 8

56

588

577.6

710

-

567.2

680

-

687

queen7 9

63

707

751.8

935

-

736.8

897

-

919

queen7 10

70

833

948.5

1177

-

926.6

1141

-

1149

queen8 8

64

728

782.1

965

-

766.9

939

-

970

the instances are ordered by total number of cuts found. This plot readily shows that most of the
cuts added were of type (I2) and (I4).
Figure 6 (b) shows an area plot depicting a similar comparison, but between those cuts added
at integer nodes and those added by the threshold separation procedure from §7. For the majority
of instances, the cuts are predominantely found through threshold cuts. The far right portion of
the plot corresponds to relatively large instances, hence only a few branching nodes were explored.

Bergman et al.: On the Minimum Chordal Completion Polytope
Article submitted to ; manuscript no. (Please, provide the manuscript number!)

Table 4

27

Results for dimacs graphs.
YUC

BC

MDO

Instance
name

|V |

|E|

LB

UB

t

LB

UB

t

UB

anna

138

493

47

47

1386.04

47

47

1.02

47

david

87

406

59.5

65

-

64

64

0.4

66

games120

120

638

496.4

1626

-

886.7

1503

-

1513

huck

74

301

5

5

2.92

5

5

0.04

9

jean

80

254

16

16

6.13

16

16

0.09

19

miles250

128

387

45.7

61

-

53

53

0.4

61

miles500

128

1170

196.4

447

-

327.487

376

-

446

miles750

128

2113

352.1

954

-

471

471

537.65

723

myciel3

11

20

10

10

0

10

10

0

10

myciel4

23

71

46

46

0.06

46

46

0.03

46

myciel5

47

236

189.7

197

-

196

196

28.93

197

1-FullIns 3

30

100

80

80

2.42

80

1-FullIns 4

93

593

657.9

785

-

839

1-Insertions 4

67

232

303.6

365

-

394

2-FullIns 3

52

201

230.4

248

-

273

2-Insertions 3

37

72

85.1

99

-

103

2-Insertions 4

149

541

659.3

1585

-

1588

3-FullIns 3

80

346

407.1

577

-

661

3-Insertions 3

56

110

118.4

192

-

198

4-FullIns 3

114

541

691.8

1094

-

1274

4-Insertions 3

79

156

155.8

330

-

331

DSJC125.1

125

736

1752.3

2618

-

2618

DSJC125.5

125

3891

2381.7

3240

-

3240

DSJC125.9

125

6961

600.6

734

-

734

miles1000

128

3216

535

535

331.2

700

miles1500

128

5198

218

218

1.65

308

mug100 1

100

166

64

64

0.3

91

mug100 25

100

166

64

64

0.51

93

mug88 1

88

146

56

56

0.22

82

mug88 25

88

146

56

56

0.49

84

myciel6

95

755

741.3

753

-

753

r125.1

125

209

11

11

0.17

15

r125.1c

125

7501

207

207

26.83

207

r125.5

125

3838

895.4

1231

-

1231

Bergman et al.: On the Minimum Chordal Completion Polytope
Article submitted to ; manuscript no. (Please, provide the manuscript number!)

28

(a) Comparing counts of inequalities
Figure 6

9.

(b) Comparing mode of cut identification

Area plots displaying types of cuts found and added by BC across all instances.

Conclusion

In this paper we described a new mathematical programming formulation for the MCCP and
investigated some key properties of its polytope. The constraints employed in our model correspond
to lifted inequalities of induced cycle graphs, and our theoretical results show that this lifting
procedure can be generalized to derive other facets of the MCCP polytope of cycle graphs. Finally,
we proposed a hybrid solution technique that considers both a lazy-constraint generation and a
heuristic separation method based on a threshold rounding, and also presented a simple primal
heuristic for the problem. A numerical study indicates that our approach substantially outperforms
existing methods, often by orders of magnitude, and, in particular, solves many benchmark graphs
to optimality for the first time.

References
Beeri C, Fagin R, Maier D, Yannakakis M (1983) On the desirability of acyclic database schemes. J. ACM
30(3):479–513, ISSN 0004-5411, URL http://dx.doi.org/10.1145/2402.322389.
Bergman D, Cire A (2016) Decompositions based on decision diagrams. CPAIOR 2016, to appear .
Bergman D, Raghunathan AU (2015) A benders approach to the minimum chordal completion problem.
Principles and Practice of Constraint Programming CP 2015, volume 6308 of Lecture Notes in Computer Science, 47–64 (Springer Berlin Heidelberg).

Bergman et al.: On the Minimum Chordal Completion Polytope
Article submitted to ; manuscript no. (Please, provide the manuscript number!)

29

Berry A, Bordat JP, Heggernes P, Simonet G, Villanger Y (2006) A wide-range algorithm for minimal
triangulation from an arbitrary ordering. Journal of Algorithms 58(1):33 – 66, ISSN 0196-6774, URL
http://dx.doi.org/http://dx.doi.org/10.1016/j.jalgor.2004.07.001.
Berry A, Heggernes P, Simonet G (2003) The minimum degree heuristic and the minimal triangulation
process. Bodlaender H, ed., Graph-Theoretic Concepts in Computer Science, volume 2880 of Lecture
Notes in Computer Science, 58–70 (Springer Berlin Heidelberg), ISBN 978-3-540-20452-7, URL http:
//dx.doi.org/10.1007/978-3-540-39890-5_6.
Bodlaender HL, Kloks T, Kratsch D, Mueller H (1998) Treewidth and minimum fill-in on d-trapezoid graphs.
Broersma H, Dahlhaus E, Kloks T (1997) Algorithms for the treewidth and minimum fill-in of HHD-free
graphs. Mhring R, ed., Graph-Theoretic Concepts in Computer Science, volume 1335 of Lecture Notes
in Computer Science, 109–117 (Springer Berlin Heidelberg), ISBN 978-3-540-63757-8, URL http://
dx.doi.org/10.1007/BFb0024492.
Chang MS (1996) Algorithms for maximum matching and minimum fill-in on chordal bipartite graphs. Asano
T, Igarashi Y, Nagamochi H, Miyano S, Suri S, eds., Algorithms and Computation, volume 1178 of
Lecture Notes in Computer Science, 146–155 (Springer Berlin Heidelberg), ISBN 978-3-540-62048-8,
URL http://dx.doi.org/10.1007/BFb0009490.
Chung F, Mumford D (1994) Chordal completions of planar graphs. Journal of Combinatorial Theory, Series
B 62(1):96 – 106, ISSN 0095-8956, URL http://dx.doi.org/http://dx.doi.org/10.1006/jctb.
1994.1056.
Codato G, Fischetti M (2006) Combinatorial benders’ cuts for mixed-integer linear programming. Operations
Research 54(4):756–766, URL http://dx.doi.org/10.1287/opre.1060.0286.
Cormen TH, Leiserson CE, Rivest RL, Stein C (2009) Introduction to Algorithms, Third Edition (The MIT
Press), 3rd edition, ISBN 0262033844, 9780262033848.
Feremans C, Oswald M, Reinelt G (2002) A y-formulation for the treewidth. Technical report, Heidelberg
University.
Fomin FV, Philip G, Villanger Y (2013) Minimum fill-in of sparse graphs: Kernelization and approximation.
Algorithmica 71(1):1–20, ISSN 1432-0541, URL http://dx.doi.org/10.1007/s00453-013-9776-1.

Bergman et al.: On the Minimum Chordal Completion Polytope
Article submitted to ; manuscript no. (Please, provide the manuscript number!)

30

Fomin FV, Villanger Y (2012) Subexponential parameterized algorithm for minimum fill-in. Proceedings
of the Twenty-third Annual ACM-SIAM Symposium on Discrete Algorithms, 1737–1746, SODA ’12
(SIAM), URL http://dl.acm.org/citation.cfm?id=2095116.2095254.
Fulkerson DR, Gross OA (1965) Incidence matrices and interval graphs. Pacific J. Math. 15(3):835–855,
URL http://projecteuclid.org/euclid.pjm/1102995572.
Garey MR, Johnson DS (1979) Computers and Intractability: A Guide to the Theory of NP-Completeness
(New York, NY, USA: W. H. Freeman & Co.), ISBN 0716710447.
George A, Liu WH (1989) The evolution of the minimum degree ordering algorithm. SIAM Rev. 31(1):1–19,
ISSN 0036-1445, URL http://dx.doi.org/10.1137/1031001.
Grone R, Johnson CR, S EM, Wolkowicz H (1984) Positive definite completions of partial hermitian matrices.
Linear Algebra and its Applications 58(0):109 – 124, ISSN 0024-3795, URL http://dx.doi.org/http:
//dx.doi.org/10.1016/0024-3795(84)90207-6.
Heggernes P (2006) Minimal triangulations of graphs: A survey. Discrete Mathematics 306(3):297 – 317, ISSN
0012-365X, URL http://dx.doi.org/http://dx.doi.org/10.1016/j.disc.2005.12.003, minimal
Separation and Minimal Triangulation.
IBM ILOG (2016) Cplex optimization studio 12.6.3 user manual.
Judd S, Kearns M, Vorobeychik Y (2011) Behavioral conflict and fairness in social networks. Chen N, Elkind
E, Koutsoupias E, eds., Internet and Network Economics, volume 7090 of Lecture Notes in Computer
Science, 242–253 (Springer Berlin Heidelberg), ISBN 978-3-642-25509-0, URL http://dx.doi.org/
10.1007/978-3-642-25510-6_21.
Kaplan H, Shamir R, Tarjan RE (1999) Tractability of parameterized completion problems on chordal,
strongly chordal, and proper interval graphs. SIAM Journal on Computing 28(5):1906–1922, URL
http://dx.doi.org/10.1137/S0097539796303044.
Kim S, Kojima M, Mevissen M, Yamashita M (2011) Exploiting sparsity in linear and nonlinear matrix
inequalities via positive semidefinite matrix completion. Mathematical Programming 129(1):33–68,
ISSN 0025-5610, URL http://dx.doi.org/10.1007/s10107-010-0402-6.

Bergman et al.: On the Minimum Chordal Completion Polytope
Article submitted to ; manuscript no. (Please, provide the manuscript number!)

31

Kloks T, Kratsch D, Wong C (1998) Minimum fill-in on circle and circular-arc graphs. Journal of Algorithms 28(2):272 – 289, ISSN 0196-6774, URL http://dx.doi.org/http://dx.doi.org/10.1006/
jagm.1998.0936.
Lauritzen SL, Spiegelhalter DJ (1990) Local computations with probabilities on graphical structures and
their application to expert systems. Shafer G, Pearl J, eds., Readings in Uncertain Reasoning, 415–
448 (San Francisco, CA, USA: Morgan Kaufmann Publishers Inc.), ISBN 1-55860-125-2, URL http:
//dl.acm.org/citation.cfm?id=84628.85343.
Mezzini M, Moscarini M (2010) Simple algorithms for minimal triangulation of a graph and backward
selection of a decomposable Markov network. Theoretical Computer Science 411(79):958 – 966, ISSN
0304-3975, URL http://dx.doi.org/http://dx.doi.org/10.1016/j.tcs.2009.10.004.
Nakata K, Fujisawa K, Fukuda M, Kojima M, Murota K (2003) Exploiting sparsity in semidefinite programming via matrix completion II: implementation and numerical results. Mathematical Programming
95(2):303–327, ISSN 0025-5610, URL http://dx.doi.org/10.1007/s10107-002-0351-9.
Rollon E, Larrosa J (2011) Principles and Practice of Constraint Programming – CP 2011: 17th International
Conference, CP 2011, Perugia, Italy, September 12-16, 2011. Proceedings, chapter On Mini-Buckets
and the Min-fill Elimination Ordering, 759–773 (Berlin, Heidelberg: Springer Berlin Heidelberg), ISBN
978-3-642-23786-7, URL http://dx.doi.org/10.1007/978-3-642-23786-7_57.
Rose DJ, Tarjan RE (1978) Algorithmic aspects of vertex elimination on directed graphs. SIAM Journal on
Applied Mathematics 34(1):176–197, URL http://dx.doi.org/10.1137/0134014.
Rose DJ, Tarjan RE, Lueker GS (1976) Algorithmic aspects of vertex elimination on graphs. SIAM Journal
on Computing 5(2):266–283, URL http://dx.doi.org/10.1137/0205021.
Rostami B, Malucelli F, Frey D, Buchheim C (2015) On the quadratic shortest path problem. International
Symposium on Experimental Algorithms, 379–390 (Springer).
Tarjan RE, Yannakakis M (1984) Simple linear-time algorithms to test chordality of graphs, test acyclicity
of hypergraphs, and selectively reduce acyclic hypergraphs. SIAM J. Comput. 13(3):566–579, ISSN
0097-5397, URL http://dx.doi.org/10.1137/0213035.
Vandenberghe L, Andersen MS (2015) Chordal graphs and semidefinite optimization. Foundations and Trends
in Optimization 1(4):241–433, ISSN 2167-3888, URL http://dx.doi.org/10.1561/2400000006.

Bergman et al.: On the Minimum Chordal Completion Polytope
Article submitted to ; manuscript no. (Please, provide the manuscript number!)

32

Yannakakis M (1981) Computing the minimum fill-in is NP-Complete. SIAM Journal on Algebraic Discrete
Methods 2(1):77–79, URL http://dx.doi.org/10.1137/0602010.
Yüceoğlu

B

(2015)

University,

Branch-and-cut
URL

algorithms

for

graph

problems.

Ph.D.

thesis,

Maastricht

http://digitalarchive.maastrichtuniversity.nl/fedora/get/guid:

bde57abf-9652-45bc-8590-667e7e085074/ASSET1.

e-companion to Bergman et al.: On the Minimum Chordal Completion Polytope

ec1

Online Supplement - Proofs of Statements
EC.1.

Additional Proofs for Section 5

Facet-defining proof of Proposition 2.

n
o
P
Let F I = x ∈ X(G) : f ∈ int(C) xf = |C | − 3 and µx ≥

µ0 be a valid inequality for conv(X(G)) which is satisfied at equality by each x ∈ F I . It suffices to
show that there exists some λ for which µf = λ and µ0 = (|C | − 3)λ.
c

Let x0 ∈ {0, 1}m be defined by
x0f =



 1,

f = {v0 , vj }, j = 2, . . . , k − 2;


 0,

otherwise.

Claim EC.1. x0 ∈ X(G), i.e., G(x0 ) is chordal, and x0 ∈ F I .
Proof.

For every j ∈ [2, k − 1], let V̄j = {v0 , v1 , . . . , vj }. By construction, set NG[V̄j ] (vj ) =

{v0 , vj−1 } induces a clique in G[V̄j ]. Therefore, v0 , v1 , . . . , vk−1 is a perfect elimination ordering

of V (G(x0 )), thereby proving that G(x0 ) is chordal. Additionally, since exactly |C | − 3 edges in
int(C) are in G(x0 ), x0 ∈ F I . 
c

Consider now the solutions x̃i ∈ {0, 1}m for i = 3, . . . , k − 1, defined by



 1, f = {v1 , vj }, j = 3, . . . , i;



i
x̃f = 1, f = {v0 , vj }, j = i, i + 1, . . . , k − 2;





 0, otherwise.
Figure EC.1 (a) provides a depiction of G(x̃i ).
Claim EC.2. Each x̃i ∈ X(G), i.e., each G(x̃i ) is chordal, and x̃i ∈ F I .
Proof.

For every j ∈ [2, k − 1], let V̄j be the set of vertices belonging to the subsequence of

(v1 , . . . , vi , v0 , vi+1 , . . . , vk−1 ) finishing at element vj . By construction, we have




{ v1 , v i } ,
j = 0;






 { v1 } ,
j = 2;
NG[V̄j ] (vj ) =




 {v1 , vj−1 } , 3 ≤ j ≤ i;




 {v0 , vj−1 } , i + 1 ≤ j ≤ k − 1,

ec2

e-companion to Bergman et al.: On the Minimum Chordal Completion Polytope

v0

v0
vk−1

vk−1

v1

vk−2

vk−2

v2

vk−3

Figure EC.1

v2

vk−3

v3

vi+1

v1

v3

vi+1

vi−1

vi−1

vi

vi

a

b

The graph (a) G(x̃i ) and the graph (b) G(x̂i ) defined in the proof of Proposition 2.

which in each case is a clique. Therefore, v1 , . . . , vi , v0 , vi+1 , . . . , vk−1 is a perfect elimination ordering
of V (G(x̃i )), showing thus that G(x̃i ) is chordal. Moreover, exactly |C | − 3 edges of int(C) are in
G(x̃i ), so x̃i ∈ F I . 
Let λ2 = µ{v0 ,v2 } . Solutions x̃i and x0 belong to FI , so µx̃i = µx0 = µ0 . By subtracting equation µx̃3 = µ0 from µx0 = µ0 , we obtain µ{v0 ,v2 } = µ{v1 ,v3 } . Additionally, shift operations on the
order of the vertices (to the left or to the right) lead to the same cycle C. Therefore, µ{v0 ,v2 } =
µ{vj ,v

(j+2) mod k

} for any j ∈ [k − 1], implying thus that µ{v0 ,v2 } = λ2 for every f ∈ int(C) containing

vertices whose indices in C differ by 2.
The same operation involving x̃i−1 and x̃i for i = 4, . . . , k − 1 yields µ{v0 ,vi−1 } = µ{v1 ,vi } . Again,
as the ordering around C can be arbitrarily shifted to the left and to the right, all edges f ∈ int(C)
containing vertices whose indices in C differ by i − 1 have the same coefficient in µ; let λi−1 be this
common value. We conclude thus that µ{vj ,v 0 } = λj 0 −j for any f = {vj , vj 0 } (assuming j < j 0 ).
j
c

Consider now the solutions x̂i ∈ {0, 1}m for i = 2, . . . , k − 2, defined by



1,




x̂if = 1,





 0,

f = {v0 , vj }, j = 2, . . . , i − 1, i + 1, . . . , k − 2
f = {vi−1 , vi+1 }
otherwise

Figure EC.1 (b) provides a depiction of G(x̂i ).
Claim EC.3. Each x̂i ∈ X(G), i.e., each G(x̂i ) is chordal, and x̂i ∈ F I .

ec3

e-companion to Bergman et al.: On the Minimum Chordal Completion Polytope

Proof.

For every j ∈ [2, k − 1], let V̄j be the set of vertices belonging to the subsequence of

(v0 , v1 , . . . , vi−1 , vi+1 , . . . , vk−1 , vi ) finishing at element vj .



{ v0 } ,




NG[V̄j ] (vj ) = {v0 , vj−1 } ,





 {v , v } ,
i−1 i+1

By construction, we have
j = 2;
1 ≤ j ≤ i − 1;
j = i,

which in each case is a clique. Consequently, (v0 , v1 , . . . , vi−1 , vi+1 , . . . , vk−1 , vi ) is a perfect elimination ordering, so x̂i ∈ X(G). Finally, as |C | − 3 edges from int(C) are included in G(x̂i ), x̂i ∈ F I .

By subtracting µx0 = µ0 from µx̂i = µ0 for any i = 2, . . . , k − 2, we obtain µ{v0 ,vi } = µ{vi−1 ,vi+1 } .
Therefore, we have that λi = λ2 for any i = 2, . . . , k − 2. If λ = λ2 , µx = µ0 can be rewritten
P

f ∈int(C) λxf

= µ0 . Finally, substituting x0 in this equation yields µ0 = (|C | − 3) λ, as desired.

Facet-defining proof of Proposition 3.



Let I := ax ≥ b be the inequality of type (I2) associated

with i = 1, F I be the set of points in conv(X(G)) that satisfy I at equality, and µx ≥ µ0 be a valid
inequality for conv(X(G)) satisfied at equality for each x ∈ F I . Let µv0 ,v2 = λ.
Claim EC.4. ∀i ∈ {3, 4, . . . , k − 1}, µ{v1 ,vi } = λ.
Proof.

For i ∈ {3, 4, . . . , k − 1} let x̌i be the solution


 1, {vi , vj }, j ∈ [k − 1]\{i − 1, i, i + 1},
i
x̌f =

 0, otherwise,

i
i
and y̌ i be the solution such that y̌{v
= 0, y̌{v
= 1, and y̌fi = x̌if for the remaining edges
1 ,vi }
0 ,v2 }

in E(G)c ; both families of solutions are depicted in Figure EC.2. We have that both x̌i and y̌ i belong
to X(G), i ∈ {3, 4, . . . , k − 1}, as G(x̌i ) is isomorphic to G(x0 ) and y̌ i is isomorphic to G(x̂i−1 ); note
that G(x̌i ) and G(x̂i−1 ) were defined and shown to be associated with chordal completions in the
proof of Proposition 2. Additionally, note that af x̌if = 1 only for f = {v1 , vi } and af y̌fi = 1 only for
f = {v0 , v2 }, so both solutions satisfy I at equality and, by definition, µx̌i = µ0 = µy̌ i . Therefore,
we must have µ{v1 ,vi } = µ{v0 ,v2 } = λ for i ∈ {3, 4, . . . , k − 1}, as desired.



ec4

e-companion to Bergman et al.: On the Minimum Chordal Completion Polytope

v1

v1
v0

v0

v2

v2

vk−1

v3

vk−1

v3

vi+2

vi−2

vi+2

vi−2

vi+1

Figure EC.2

vi+1

vi−1

vi−1

vi

vi

a

b

The graph (a) G(x̌i ) and the graph (b) G(y̌ i ) defined in the proof of Proposition 3.



0

S

Claim EC.5. For each f ∈ int(C)\ {v0 , v2 } ∪


{v1 , vi } , µf 0 = 0.

i=3,...,k−1


Proof.



{v1 , vi } 6= ∅ only if k ≥ 5. Let f 0 = {vj , vj 0 }

S

First, note that int(C)\ {v0 , v2 } ∪

i=3,...,k−1

be such an edge, and assume without loss of generality that vj 6= v0 (i.e., vj 0 can be equal to v2 ).
Let z(f 0 ) be the solution in



 1,






 1,
0
z(f )f =



1,






 0,

c

{0, 1}m presented in Figure EC.3 (part a) defined by

f = {vi , vj 0 }, k = 0, 2 ≤ i ≤ j 0 − 2, and j + 1 ≤ i ≤ k − 1,
f = {vj+1 , vj 0 +1 },
f = {vj , vi }, j 0 + 1 ≤ i ≤ j − 2,
otherwise.

Solution z(f 0 ) satisfies I at equality, as af z(f 0 )f = 1 for f = {v1 , vj 0 } and af z(f 0 )f = 0 for all the
other edges in G(z(f 0 )). Moreover, G(z(f 0 )) is isomorphic to the graph presented in Figure EC.1
(part a), so z(f 0 ) ∈ X(G).
c

Let now z 0 (f 0 ) be the solution in {0, 1}m

such that z 0 (f 0 )f 0 = 1 and z 0 (f 0 )f =

z(f 0 )f for the remaining edges; this solution is presented in Figure EC.3 (part b). The
same argument used for z(f 0 ) shows that z 0 (f 0 ) satisfies I at equality, and sequence
(vj , vj 0 , vj+1 , vj+2 , . . . , vk−1 , v0 , v1 , . . . , vj 0 −1 , vj 0 +1 , . . . , vj−1 ) is a perfect elimination ordering of V (G)
for G(z 0 (f 0 )), which shows that z 0 (f 0 ) ∈ X(G).
Finally, because µz 0 (f 0 ) = µ0 = µz(f 0 ), it follows that µf 0 = 0, as desired.



Direct inspection on any solution x̌ (e.g., x̌3 ) allows us to see that µ0 = λ. Therefore, there exists
a λ such that ∀f ∈ E c , µf = λaf and µ0 = bλ, completing the proof that I is facet-defining.



ec5

e-companion to Bergman et al.: On the Minimum Chordal Completion Polytope

v1

v1
v0

v0

v2

v2

vk−1

v3

vk−1

v3

vj+1

vj 0

vj+1

vj 0

a

Figure EC.3

vj 0 +2

vj−1

vj 0 +2

vj−1

vj 0 +1

vj

vj 0 +1

vj

b

The graph (a) G(z(f 0 )) and the graph (b) G(z 0 (f 0 )) defined in the proof of Proposition 3.

Facet-defining proof of Proposition 4.

Let I := ax ≥ b be any inequality (I3). Moreover, let F I

be the set of points in conv(X(G)) that satisfy I at equality and µx ≥ µ0 be a valid inequality for
conv(X(G)) satisfied at equality for each x ∈ F I . Let λ = µ{v0 ,v2 } .
Claim EC.6. ∃λ 6= 0 such that ∀f ∈ int(C) with dC (f ) = 2, µf = λ.
Proof.

Consider solutions x0 and x̃3 presented in the proof of Proposition 2; graph G(x0 ) is

isormorphic to the one shown in Figure EC.2 (part a) and has v0 as the neighbour of all vertices
in V (G), whereas graph G(x̃3 ) is shown in Figure EC.1 (part a). By construction, both solutions
are in F I . Subtracting µx0 = µ0 from µx̃3 = µ0 and cancelling like terms yields µ{v0 ,v2 } = µ{v1 ,v3 } .
By applying sequentially this procedure starting from any fill edge of C with dC (vi , vj ) = 2, we
obtain the desired result.



Claim EC.7. ∀f ∈ int(C) s.t. dC (f ) ≥ 3, µf = 0.
Proof.

Let ỹ i be the set of solutions given by ỹ i = x̃i + e{v1 ,vi+1 } , 3 ≤ i ≤ k − 3, with x̃ being again

the solutions defined in the proof of Proposition 2. Each solution ỹ i satisfies I at equality. Moreover,
(v1 , v2 , . . . , vi , v0 , vi+1 , vi+2 , . . . , vk−1 ) is a perfect elimination ordering for each G(ỹ i ), showing thus
that each ỹ i is a valid solution. Therefore, µỹ i = µ0 = µx̃i = µ0 , and as ỹ i and x̃i only differ on
the coordinate corresponding to fill edge {v1 , vi+1 }, we must have µ{v1 ,vi+1 } = 0 for any edge index
i, 3 ≤ i ≤ k − 2. This implies, due to cyclic symmetry, that µf = 0 for any edge f ∈ int(C) such that
dC (f ) ≥ 3.



ec6

e-companion to Bergman et al.: On the Minimum Chordal Completion Polytope

Finally, we have µ0 = µx0 = µ{v0 ,v2 } + µ{v0 ,v2 } = 2λ. Therefore, there exists a λ such that µ0 = bλ
and µf = λaf for every f in E c , which shows that I is facet-defining.

Facet-defining proof of Proposition 5.



Let I := ax ≥ b be any inequality (I4). Without loss of

generality, let j = 0 and i be any value in [2, k − 3]. Let F I be the set of points in conv(X(G)) that
satisfy I at equality, and let µx ≥ µ0 be a valid inequality for conv(X(G)) satisfied at equality for
each x ∈ F I .
Claim EC.8. µ{v0 ,vi } = µ{vi−1 ,vi+1 } = 0.
Proof.

Consider solutions x0 and x̂i presented in the proof of Proposition 2. Direct inspection

allows us to see that both belong to F I and differ only on coordinates σ({v0 , vi }) and σ({vi−1 , vi+1 }),
so that µx0 = µ0 = µx̂i implies that µ{v0 ,vi } = µ{vi−1 ,vi+1 } .
Additionally, the solution x0 + e{vi−1 ,vi+1 } also belongs to F I : it satisfies I at equality and the sequence (v0 , v1 , . . . , vk−1 ) is a perfect elimination order of V (G). Therefore, as


µ x0 + e{vi−1 ,vi+1 } = µx0 + µ{vi−1 ,vi+1 } = µ0 , it follows that µ{vi−1 ,vi+1 } = 0. 
Let C 0 = (v0 , v1 , . . . , vi−1 , vi+1 , vi+2 , . . . , vk−1 ) and let λ = µv1 ,vk−1 .
Claim EC.9. ∃ λ such that ∀f ∈ int(C 0 ), µf = λ.
Proof.

Let x be any feasible solution of X(C 0 + {{vi−1 , vi+1 }}) satisfying inequality (I1) at

equality. Let y be a solution of X(G) defined as follows:



xf , f ∈ int(C 0 )




yf = 1,
f = {vi−1 , vi+1 }





 0,
otherwise.
Solution y belongs to X(G) because any perfect elimination order of V (C 0 ) can be extended into
a perfect elimination order for V (C) by putting vi in the end of the sequence (note that the only
neighbors of vi are vi−1 and vi+1 , which are necessarily connected). Moreover, by construction,
P
P
P
0
I
f ∈int(C 0 ) yf = |C | − 3 = |C | − 4, so y ∈ F . Finally, as
f ∈int(C)\{{vi−1 ,vi+1 ,{vj ,vi }}} yf =
f ∈int(C 0 ) yf
for all j ∈ [k − 1] \ {i}, it follows from the arguments used in the proof of Proposition 2 that µf = λ
for each f ∈ int(C 0 ).



ec7

e-companion to Bergman et al.: On the Minimum Chordal Completion Polytope

Claim EC.10. ∀f = {vi , v` }, ` = 1, 2, . . . , i − 2, i + 2, i + 3, . . . , k − 2, µf = λ.
Fix `0 ∈ {1, 2, . . . , i − 2, i + 2, i + 3, . . . , k − 2}. Let x̄ be defined by


 1, vi ∈ f
x̄f =

 0, otherwise.

Proof.

G(x̄) is isomorphic to the solution x0 defined in the proof of Proposition 2, so it follows that x̄
is feasible. Moreover, x̄f = 1 for |C | − 4 edges in int(C) \ {{vi−1 , vi+1 } , {v0 , vi }}, so we have that
x̄ ∈ F I .
0

0

0

Let x̄` be the solution of X(G) such that x̄`{v 0

` −1 ,v`0 +1 }

0

= 1, x̄`{vi ,v 0 } = 0, and x̄`f = x̄f for
`

`0

0

the remaining edges. The graph G(x̄ ) is isomorphic to one of the graphs G(x̂i ) defined in
0

0

the proof of Proposition 2, and therefore x̄` ∈ X(G). Moreover, x̄`f = 1 for |C | − 4 edges in
0

int(C) \ {{vi−1 , vi+1 } , {vi , vl0 }}, so we have that x̄` ∈ F I .
0

Finally, we have µx̄ = µ0 and µx̄` = µ0 , and the subtraction of these two equalities yields
µ{v`0 −1 ,v`0 +1 } = µ{vi ,v`0 } . Since {v`0 −1 , v`0 +1 } ∈ int(C 0 ), λ = µ{v`0 −1 ,v`0 +1 } and µ{vi ,v`0 } = λ.



From the previous claims, we have that any solution in F I yields µ0 = λ (|C | − 4), as desired.


EC.2.

Additional Proofs for Section 6

Lemma EC.1. If G = (V, E) is a chordal graph, then the graph G0 = (V ∪ w, E ∪ {(w, v) : ∀ v ∈ V }
is also chordal.
Proof.

Suppose by contradiction that C = (v0 , v1 , . . . , vk−1 ), k ≥ 4, is a chordless cycle in G0 .

As G does not contain chordless cycles, V (C) cannot be contained in V (G), so w ∈ V (C). By
construction, w is adjacent to all vertices in V (G) and, in particular, to all vertices in V (C),
contradicting thus the hypothesis that C is chordless.



Lemma EC.1 can be extended to cliques as opposed to single vertices, since this addition can
be seen as a inductively adding a single vertex one-by-one. This is formalized in the following
immediate corollary.

ec8

e-companion to Bergman et al.: On the Minimum Chordal Completion Polytope

Corollary EC.1. If G = (V, E) is a chordal graph, then the graph G0 = (V ∪ W, E ∪
{(w, v) : ∀w ∈ W, v ∈ V ∪ W \{w}} is also chordal.

Definition EC.1. An edge e is said to be critical in a chordal graph G = (V, E) if G0 = (V, E \e)
is not chordal (i.e., the removal of e from G creates a chordless cycle).
Lemma EC.2. Let G = (V, E) be a chordal graph. If e = {v, w} is critical, then any chordless
cycle C emerging after the deletion of e is such that {v, w} ⊂ V (C) and |C | = 4.
Proof.

Let C be a chordless cycle emerging after the deletion of e. If either v or w does not

belong to V (C), then C is also a chordless cycle in G, so G is not chordal, a contradiction.
Suppose |C | > 4. In this case, C can be written as a sequence v ∼ P1 ∼ w ∼ P2 , where P1 and
P2 are paths in G such that V (P1 ) ∩ V (P2 ) = ∅ and v, w ∈
/ V (P1 ) ∪ V (P2 ). Moreover, as |C | > 4, at
least one of P1 , P2 contains 2 or more vertices. If |P1 | > 1 (|P2 | > 1), then the sequence described by
path v ∼ P1 ∼ w (w ∼ P2 ∼ v) induces a chordless cycle in G, thereby contradicting the assumption
that G is chordal.



Proof of Theorem 3.

This follows directly from Theorem EC.1 presented next.



Theorem EC.1. Let G = (V, E) and E 0 ⊆ E C be such that G + E 0 is not chordal and G + E 0 \{f }
is chordal for every f ∈ E 0 . If ax ≥ b is facet-defining for conv(X(G + E 0 )), a ≥ 0, and a0 ∈ R|E

C

(G)|

,

with a0f = af if f ∈ E C \E 0 and a0f = 0 otherwise, the inequality


X
a0 x ≥ b 
xf − |E 0 | + 1
f ∈FG (C)

is facet-defining for conv(X(G)).
Let ax ≥ b be a facet-defining inequality for conv(X(G + E 0 )) and I be
P

0
the corresponding lifted inequality a0 x ≥ b
x
−
|
E
|
+
1
for conv(X(G)).
f ∈E 0 f
Proof of Theorem EC.1

First, we show that I is valid for conv(X(G)). Since a ≥ 0, I can only be violated by a feasible
P
element x of conv(X(G)) if f ∈E 0 xf = |E 0 |; otherwise, I is trivially satisfied. Moreover, because
ax0 ≥ b is valid for every x0 ∈ conv(X(G + E 0 )), we have


X
X
a0 x =
af xf ≥ b = b 
xf − |E 0 | + 1 ,
f ∈E C \E 0

f ∈E 0

ec9

e-companion to Bergman et al.: On the Minimum Chordal Completion Polytope

as desired.
Now we present a set of |E c | affinely independent vectors of conv(X(G)) satisfying I at equality.
For any facet-defining inequality ax ≥ b of conv(X(G + E 0 )), there exists an affinely independent
set of vectors W = {wj }dj=1 ⊆ {0, 1}|E

C

\E 0 |

that satisfy ax = b. Let T = {tj }dj=1 ⊆ {0, 1}|E

C

|

be such

that
tjf

=



 wfj ,

f ∈ EC \ E0,


 1,

f ∈ E0.

That is, tj is an embedding of wj in {0, 1}|E

C

|

in which coordinates associated with edges in E 0 are

set to 1. Note that every tj belongs to conv(X(G)) because G(tj ) is isomorphic to (G + E 0 ) (wj ),
which is chordal. Moreover, by construction, a0 tj =

P

f ∈E C \E 0

a0f tjf = b and

j
f ∈E 0 tf

P

= |E 0 | for

each j = 1, . . . , d, so solutions of T satisfy I at equality. Finally, note that the embedding operation
in the elements of W is such that T is also affinely independent.
Let Z = {z f }f ∈E 0 ⊆ {0, 1}|E

C

|

be such that

zff0 =



1

f 0 ∈ E 0 \ f,


 0,

otherwise.

As G + E 0 \ {f } is chordal by hypothesis, it follows that each solution z f belongs to conv(X(G)).
Moreover, by construction, a0 z f =

P

f 0 ∈E C \E 0

a0f 0 tjf 0 = 0 and

P

f 0 ∈E 0

zff0 = |E 0 | − 1 for each f ∈ E 0 , so

each solution of Z satisfies I at equality. Let αf , f ∈ E C \ E 0 , and βf , f ∈ E 0 , be constants for which
X

αj tj +

X
f ∈E 0

f ∈E C \E 0

βf z f = 0,

X
f ∈E C \E 0

αj +

X

βf = 0.

f ∈E 0

For each f ∈ E 0 , we have zff = 0, whereas sf = 1 for s ∈ T ∪ Z \ {z f }. Therefore, we must have
P

f 0 ∈E C \E 0

αf 0 +

P

f 0 ∈E 0 \{f } βf

0

= 0 and, as a consequence, βf = 0 for each f ∈ E 0 . Finally, as T

is affinely independent, we have that αf = 0, f ∈ E C \ E 0 . It follows that I is a faced-defining
inequality for conv(X), as desired.
Proof of Theorem 4.



Without loss of generality, let f ∗ = {v0 , vt−1 }, t < k, be the chord consid-

ered and I be the associated lifted inequality a0 x − bxf ∗ ≥ 0 for X(G). For any vector x ∈ {0, 1}|E

c

|

ec10

e-companion to Bergman et al.: On the Minimum Chordal Completion Polytope

and set E 0 ⊆ E c , let x[E 0 ] be the projection of x onto the coordinates corresponding to fill edges
in E 0 .
First, we claim that I is valid for X(G). Take any solution x0 ∈ X(G). If x0f ∗ = 0, then I reduces
to a0 x0 ≥ 0, which must be satisfied because a0 ≥ 0 and x0 ≥ 0. If x0f ∗ = 1, then I reduces to
a0 x ≥ b. Since G(x0 ) is chordal, by Lemma 2 we have that G(x0 )[C 0 ] is also chordal, and therefore
x0 [int(C 0 )] ∈ X(G0 ). Since I is facet-defining for conv(X(G0 )), we have a0 x0 = ax0 [int(C 0 )] ≥ b. As
x0 was chosen arbitrarily among all feasible solutions in X(G), it follows that I is valid for X(G).
Let C 0 = (v0 , v1 , . . . , vt−1 ) , C 00 = (v0 , vt−1 , vt , . . . , vk−1 ), and
Cross(f ∗ ) = {f : f ∩ {v1 , v2 , . . . , vt−2 } 6= ∅, f ∩ {vt , vt+1 , . . . , vk−1 } 6= ∅};
that is, Cross(f ∗ ) contains all fill edges in int(C) containing exactly one vertex incident in C 0 \ C 00
and one vertex incident in C 00 \ C 0 . Set int(C) can therefore be partitioned as follows:
int(C) = int(C 0 ) ∪˙ int(C 00 ) ∪˙ f ∗ ∪˙ Cross(f ∗ )
Let F I be the set of points in conv(X(G)) that satisfy I at equality, and µx ≥ µ0 be a valid
inequality for conv(X(G)) satisfied at equality by each x ∈ F I . Inequality µx ≥ µ0 can be written
as
X

µf xf +

f ∈int(C 0 )

X

µf xf + µf ∗ xf ∗ +

f ∈int(C 00 )

X

µf xf ≥ µ0

f ∈Cross(f ∗ )

Claim EC.11. For every f in Cross(f ∗ ), µf = 0.
Proof.

Take any vector w̃b in X(G0 ) such that aw̃b = b. Moreover, let us assume that the fill in

set associated with w̃b is minimal; note that if w̃b does not satisfy this condition, then it can be
substituted for some other feasible solution w0 , aw0 = aw̃b = b, associated with a subset of the fill
in edges represented by w̃b .
From Proposition 4, it follows that G0 (w̃b ) must contain an edge {vb−1 , vb+1 }. Moreover, from
Lemma 2, we have that w0 = w̃b [E c (G0 ) \ {{va , vb } : va ∈ V (G0 )}] is associated with a chordal completion of G0 [V (G) \ vb ]. Because vb−1 and vb+1 are the only neighbours of vb in G0 , the edges of w0

e-companion to Bergman et al.: On the Minimum Chordal Completion Polytope

ec11

are sufficient to make G0 chordal; therefore, we have that the neighbours of vb in G0 [w̃b ] are exactly
its neighbours in C 0 .
Fix f 0 ∈ Cross(f ∗ ), f 0 = {va , vb }, 1 ≤ a ≤ t − 2, t ≤ b ≤ k − 1. Let w̃ in X(G) be defined by




w̃fb , f ∈ int(C 0 )







1,
f = f∗




w̃f = 1,
f ∈ int(C 00 )







0,
f = {va , vb }






 1,
f ∈ Cross(f ∗ )\{va , vb }

By Lemma EC.1, G w̃ + e{va ,vb } is a chordal graph. We claim that {va , vb } cannot be critical,
and therefore G (T 1 (w̃b )) is chordal. Suppose by contradiction that this is not true. Then, upon
the removal of {va , vb }, by Lemma EC.2 there must exists vertices v 0 , v 00 for which (va , v 0 , vb , v 00 ) is
a chordless cycle. This can only happen if there exists a pair of vertices in N (vb ) which are not
adjacent. However, N (vb ) = {vb−1 , vb+1 } ∪ {vt , vt+1 , . . . , vk−1 }, which, by construction, is a clique.
Therefore, we have that w̃ and w̃ + e{va ,vb } belong to conv(X(G)). Additionally, both solutions
satisfy I at equality and belong thus to F I . Finally, as
µ(w̃ + e{va ,vb } − w̃) = µ{va ,vb } = 0,
it follows that µf 0 = 0 for every f 0 ∈ Cross(f ∗ ).



Claim EC.12. For every f ∈ int(C 00 ), µf = 0.
Proof.

Fix f 0 = {z1 , z2 } ∈ int(C 00 ) and any solution w̃b in X(G0 ) such that aw̃b = b. Let w̃ be

defined by




w̃fb ,







1,




w̃f = 0,







0,






 1,

f ∈ int(C 0 )
f = f∗
f ∈ Cross(f ∗ )
f = f0
f ∈ int(C 00 )\f 0

ec12

e-companion to Bergman et al.: On the Minimum Chordal Completion Polytope
0

We claim that G(w̃ + ef ) is chordal. Consider the ordering π of the vertices in V (G) consisting
of a perfect elimination order of the vertices in V (C 0 ) (which must exists because G[V (C 0 )](w̃b ) is
chordal), followed by an arbitrary ordering of the remaining vertices. Because the neighbourhood
of each vertex in V (C 00 ) \ V (C 0 ) is a clique in V (C 00 ), it follows by construction that π is a perfect
0

elimination ordering for the vertices of G(w̃ + ef ).
We claim now that G(w̃) is also chordal. If not, by Lemma EC.2 there must exist a chordless
0

cycle (z1 , v 0 , z2 , v 00 ) created upon the removal of f 0 from G(w̃ + ef ). At least one among z1 and z2
is contained in {vt , vt+1 , . . . , vk−1 }; let z1 be one such vertex. The neighborhood of z1 in G(w̃) is
V (C 00 ), and as G(w̃)[V (C 00 )] is a clique, we must have {v 0 , v 00 } ∈ E(G(w̃)), a contradiction.
0

Therefore, we have that w̃ and w̃ + ef belong to conv(X(G)) and, by construction, to F I .
Similar arguments to those used in the previous claim allow us to conclude that µf 0 = 0 for every
f 0 ∈ int(C 00 ). 
Claim EC.13. µ0 = 0.
Proof.

Consider the solution ŵ defined by


 1,
ŵf =

 0,

vk−1 ∈ f
otherwise

This solution is isomorphic to the solution x0 constructed in the proof of Proposition 2, so G(ŵ)
is chordal. By construction, because f ∗ = {v0 , vt−1 } for t < k, ŵf ∗ = 0. Moreover, as af = 0 for
f∈
/ int(C 0 ), we have aŵ = 0, and therefore aŵ − bŵf ∗ = 0. Substituting ŵ into µx = µ0 yields
X

µ0 = µŵ =

µf ŵf + µf ∗ ŵf ∗ = 0,

f ∈int(C 0 )

as desired.



Claim EC.14. There is a λ ∈ R such that µf ∗ = −λb and µf = λaf for every f in int(C 0 ).
Proof.

Let F̃ I be the subset of F I containing only solutions x such that xf = 1 for every edge

f which does not belong to int(C 0 ). For every x ∈ F̃ I , we have
µx =

X

µf xf + µf ∗ 1 = 0 =⇒

f ∈int(C 0 )

X
f ∈int(C 0 )

µf xf = −µf ∗ .

e-companion to Bergman et al.: On the Minimum Chordal Completion Polytope

ec13

Consequently, we have that every solution y in X(G0 ) that satisfies ay = b must also satisfy
µ[int(C 0 )]y = −µf ∗ . As ay ≥ b is facet-defining for X(G0 ), there exists some λ such that −µf ∗ = λb
and µf = λ0 af for every f in E(G0 )c , as desired.



From the previous claims, we conclude that I is a facet-defining inequality for conv(X(G)).

EC.3.



Additional Proofs for Section 7.1

We first provide a lemma.
c

Lemma EC.3. For any fractional point x ∈ [0, 1]m , if x ∈
/ conv(X(G)), then there is a chordless
cycle C in G + E(x) whose associated inequality of type (I1) is violated by x.
Proof.

Suppose by contradiction that this claim does not hold, and let C be a cycle in G

associated with a violated inequality of type (I1) such that int(C) ∩ E(G) is minimum. Set int(C)
must contain at least one edge e in E(G), so let C 0 and C 00 be the sub-cycles of C such that
V (C 0 ) ∩ V (C 00 ) = e, V (C 0 ) ∪ V (C 00 ) = V (C), and E(C 0 ) ∩ E(C 00 ) = {e}; by construction, we have
|C 0 | + |C 00 | = |C | + 2.

If x satisfies the inequalities (I1) associated with C 0 and C 00 , we have
X
e∈int(C)

xe ≥

X
e∈int(C 0 )

xe +

X

xe + 1 ≥ |C 0 | − 3 + |C 00 | − 3 + 1 = |C | + 2 − 5 = |C | − 3,

e∈int(C 00 )

contradicting hence the fact that C does not satisfy inequality I1. Therefore, x must violate inequality (I1) for C 0 or C 00 ; let us assume that the violation holds for C 0 . If int(C 0 ) does not contain any
edge in E(G), we have a contradiction. Otherwise, we must have |int(C 0 ) ∩ E(G)| < |int(C) ∩ E(G)|,
which contradicts the selection of C.
Proof of Theorem 5(a).



We show this result by proving that the (−3)-Quadratic Shortest Cycle

Problem (or (−3)-QSCP), defined below, can be reduced to the the separation of the simplified
version of inequalities I1. Lemma EC.3 allows us to conclude that these two problems are equivalent,
so the main step of the proof consists of showing that (−3)-QSCP is N P -complete.

ec14

e-companion to Bergman et al.: On the Minimum Chordal Completion Polytope

We define the Quadratic Shortest Cycle Problem (QSCP) as follows: we are given an undirected
graph G = (V, E) and a quadratic cost function q : V × V → [0, 1] such that q(u, v) = 0 if (u, v) ∈ E;
that is, the quadratic cost associated with {u, v } can be different from zero only if {u, v } ∈
/ E.
For any cycle C in G, let int∗ (C) = E(G[C])C , that is, edge {u, v } belongs to int∗ (C) if u 6= v
and (u, v) ∈
/ E. A feasible solution for an instance of QSCP consists of a simple chordless cycle
C = (v1 , v2 , . . . , v|C| ) whose cost p(C) is given by
p(C) =

X

q(u, v) − |C |.

{u,v}∈int∗ (C)

Finally, α-QSCP is the decision version of QSCP in which the goal is to decide whether there is a
simple chordless cycle C such that p(C) < α.
Lemma EC.4. (−3)-QSCP is N P -complete.
Proof.

Our proof employs a reduction of the Quadratic Assignment Problem (QAP) to (−3)-

QSCP. This strategy is based on the reduction used by Rostami et al. (2015) to show that the
Quadratic Shortest Path Problem is strongly NP-hard.
QAP description: For an arbitrary instance I of QAP, let F and L be the set of facilities and
locations, respectively, with n = |F | = |L|, and let C, D, and A be the n × n matrices in R+ describing the flow between facilities, the distance between locations, and the cost of assigning facilities
to locations, respectively; recall that linear costs are given by entries of A, whereas quadratic costs
are associated with the multiplication of one entry in C (referring to the flow of products between
facilities) by some other entry in D (representing the distance between locations). Finally, we are
given a value β, and the goal is to decide whether the instance of QAP admits an assignment whose
cost is smaller than β. This problem is known to be NP-complete (see e.g., Garey and Johnson
(1979)).
Let





M = max  max
0

1≤f,f ≤|F |
1≤l,l0 ≤|L|


Cf,f 0 Dl,l0 , max Af,l  ,
1≤f ≤|F |
1≤l≤|L|

e-companion to Bergman et al.: On the Minimum Chordal Completion Polytope

ec15

that is, M is the largest individual penalty that may compose the cost of a feasible assignment. Any
feasible solution consists of n assignments, so it is subject to not more than n2 and n quadratic and
linear penalizations, respectively. Therefore, no feasible assignment has an objective value larger
than K = 2M n2 .
Vertices and edges: From I, we construct an instance I 0 of (−3)-QSCP associated with a graph
G = (V, E) and a quadratic cost q : V × V → [0, 1] as follows. Let us assume w.l.o.g. that there is
some (arbitrary) ordering between facilities, that is, F = {f1 , f2 , . . . , fn }.
Set V contains one assignment vertex af,l for each pair (f, l) ∈ F × L; these vertices can be
interpreted as the assignment of facilities to locations. We say that a pair of assignment vertices
belong to the same block if they are associated with the same facility.
For technical reasons, V contains three types of auxiliary variables. We have type-z vertices z1
and z2 and type-y variables y1 , y2 , . . . , yn whose usage will become clear next. Additionally, for
each pair of assignments (fi , l) and (fi+1 , l0 ), 1 ≤ i < n and l, l0 ∈ L, we have a connection vertex
cfi ,fi+1 ,l,l0 . V also contains connection vertices cz1 ,f1 ,∅,l and cfn ,yn−1 ,l,∅ for all l in L; by an abuse of
notation, we might use cf0 ,f1 ,l,l0 instead of cz1 ,f1 ,∅,l0 (i.e., substitute (z1 , ∅) for (f0 , l)) and cfn ,fn+1 ,l,l0
instead of cfn ,zn ,l,∅ ((zn , ∅) for (fn+1 , l0 ) ) in situations where the correct notation can be easily
inferred from the context. A pair of connection vertices is said to belong to the same block if they
have the same first facility index.
Each assignment vertex afi ,l composes edges with connection vertices cfi ,fi+1 ,l,l0 and cfi−1 ,fi ,l00 ,l for
all l0 , l00 in L. Moreover, z1 and assignment vertices af1 ,l are connected to cz1 ,f1 ,∅,l , whereas yn and
assignment vertices afn ,l are connected to cfn ,yn ,l,∅ , l ∈ L. Note that afi ,l and afi+1 ,l0 are the only
neighbours of cfi ,fi+1 ,l,l0 , that is, all connection vertices have degree 2. Finally, {z1 , z2 }, {z2 , y1 },
{y1 , y2 }, . . . , {yn−1 , yn } are also edges of E. An example of graph associated with an instance of

QAP with n = 3 is presented in Figure EC.4.
Penalties: The goal of the construction is to enforce every algorithm deciding (−3)-QSCP to
deliver a cycle C as solution for I 0 if and only if I admits an assignment whose cost is inferior to β.

ec16

e-companion to Bergman et al.: On the Minimum Chordal Completion Polytope

cf1 ,f2 ,l1 ,l2
af1 ,l1

cf2 ,f3 ,l1 ,l2
af2 ,l1

cf1 ,f2 ,l1 ,l3

af3 ,l1
cf2 ,f3 ,l1 ,l3

cz1 ,f1 ,∅,l1

cf3 ,y3 ,l1 ,∅
cf1 ,f2 ,l2 ,l1

z1

cz1 ,f1 ,∅,l2

af1 ,l2

cf2 ,f3 ,l2 ,l1
af2 ,l2

cf1 ,f2 ,l2 ,l3

af3 ,l2

y3

cf2 ,f3 ,l2 ,l3

cz1 ,f1 ,∅,l3

cf3 ,y3 ,l3 ,∅
cf1 ,f2 ,l3 ,l1
af1 ,l3

cf2 ,f3 ,l3 ,l1
af2 ,l3

cf1 ,f2 ,l3 ,l2

af3 ,l3
cf2 ,f3 ,l3 ,l2

y1

z2

Figure EC.4

cf3 ,y3 ,l2 ,∅

y2

Construction for QAP instance with n = 3.

We say that C is associated with the solution of I containing each assignment (fi , lj ) such that
afi ,lj belongs to V (C).
Let Alg be an algorithm deciding (−3)-QSCP. Alg can return C only if
p(C) = pL (C) + pQ (C) + q ∗ (C) < −3,
where q ∗ (C) is the sum of −|C | with all additional costs that will be incorporated in our construction
and pL (C) and pQ (C) denote the linear and the quadratic costs of I mapped into C, respectively.
For technical reasons described below, the original (linear and quadratic) costs of I will be divided
by K in I 0 . As a consequence, the assignment associated with C is a solution of I if it is feasible
and
pL (C) + pQ (C) <

β
,
K

so we just need to define q ∗ (C) in a way that
−3 − q ∗ (C) =

β
β
=⇒ q ∗ (C) = −3 − .
K
K

Note that β ≤ K; otherwise, any feasible assignment decides I.

e-companion to Bergman et al.: On the Minimum Chordal Completion Polytope

ec17

In summary, the costs composing q ∗ (C) should guarantee that Alg returns a cycle if and only if
the associated assignment in I is feasible with cost inferior to β. For this, our construction restricts
the set of cycles Alg may select to matching cycles, which are cycles in G of size 3n + 3 that
pass through all type-y and type-z vertices and are associated with a feasible assignment for the
QAP instance whose cost is below β. The rest of the proof shows how the function q enforces the
satisfaction of these conditions.
Original QAP penalties: For each pair of assignment vertices af,l and af 0 ,l0 , f 6= f 0 and l 6= l0 , we
have the assignment cost
q(af,l , af 0 ,l0 ) =

Cf,f 0 Dl,l0
,
K

which represents the quadratic cost of I associated with assignments (f, l) and (f 0 , l0 ).
Additionally, we have linear costs
q(z1 , af,l ) =

Af,l
,
K

that is, q(z1 , af,l ) contains the linear cost of I associated with assignment (f, l).
Note that the scaling factor

1
K

enforces all values to belong to [0, 2n1 2 ] and, consequently, the sum

of these penalties is bounded by 1 for any feasible assignment in I. In particular, any cycle C of G
associated with a feasible assignment is such that 0 ≤ pL (C) + pQ (C) ≤ 1.
Infeasibility penalties: Cycle C cannot be a matching cycle if V (C) contains one or more pairs
of assignment vertices sharing the same location or facility. In order to avoid these configurations,
we set assignment conflict costs
q(af,l , af 0 ,l0 ) = 1
for every pair of assignment vertices af,l and af 0 ,l0 such that either f = f 0 or l = l0 . Note that this
penalty is not smaller than the (scaled) cost of any feasible solution of I.
Similar penalizations will be applied to pair of connection vertices belonging to the same block.
That is, given connection vertices cfi ,fi+1 ,l,l0 and cfi ,fi+1 ,l00 ,l000 , 1 ≤ i ≤ n and l, l0 , l00 , l000 ∈ L, we have
transition conflict costs
q(cfi ,fi+1 ,l,l0 , cfi ,fi+1 ,l00 ,l000 ) = 1.

ec18

e-companion to Bergman et al.: On the Minimum Chordal Completion Polytope

Sub-cycle elimination: In order to avoid the selection of cycles which do not pass through type-y
and type-z vertices, we penalize pairs of connection vertices belonging to consecutive blocks. That
is, given connection vertices cfi ,fi+1 ,l,l0 and cfi+1 ,fi+2 ,l00 ,l000 , 0 ≤ i < n and l, l0 , l00 , l000 ∈ L, we have
transition penalties
q(cfi ,fi+1 ,l,l0 , cfi+1 ,fi+2 ,l00 ,l000 ) = 1.
Note that this penalty incurs n times in matching cycles.
Compensation penalties: Penalties described here are used to compensate for the inclusion of
vertices and to make the solution respect the upper bound β associated with I.
The inclusion of connection vertices is compensated by their quadratic costs with z2 . That is,
for every connection vertex cfi ,fi+1 ,l,l0 , 0 ≤ i < n − 1 and l, l0 ∈ L (note that connection vertices who
are neighbours of yn are excluded), we have connection-covering costs
q(z2 , cfi ,fi+1 ,l,l0 ) = 1.
In matching cycles, connection-covering costs incur n times.
The costs of type-y vertices are covered by quadratic assignments involving z1 and connection
vertices cfi ,fi+1 ,l,l0 , 1 ≤ i < n − 1 and l, l0 ∈ L (note that we are excluding the neighbours of z1
andyn ). These y-covering costs are given by
q(z1 , cfi ,fi+1 ,l,l0 ) = 1.
In matching cycles, these costs incur n − 1 times.
So far, the sum of the compensation penalties with the transition penalties for any matching
β
cycle C is equal to n + n + n − 1. Because |C | = 3n + 3, there is a deficit of 1 − K
< 1 in p(C). For

this, we employ the quadratic cost of yn and z1 , that is,
q(z1 , yn ) = 1 −

β
.
K

Finally, all the remaining costs that have not been explicitly presented are set to zero.

ec19

e-companion to Bergman et al.: On the Minimum Chordal Completion Polytope

af1 ,l1

cz1 ,∅,f1 ,l1

af2 ,l2

cf1 ,l1 ,f2 ,l2

cf2 ,l2 ,f3 ,l3

af3 ,l3

z1

cz1 ,∅,f1 ,l4

cf1 ,l4 ,f2 ,l5

af1 ,l4

Figure EC.5

cf2 ,l5 ,f3 ,l3

af2 ,l5

Sub-cycle of G with 12 vertices

Lemma EC.5. Every cycle delivered by Alg must contain all type-z and type-y vertices.
Proof.

Let us assume that C does not include some type-y or type-z vertex; by construction,

a cycle in G contains either all vertices in {z2 , y1 , y2 , . . . , yn−1 } or none of them, so C may only
contain z1 , yn , assignment vertices, and connection vertices. Consequently, C belongs to a bipartite
region of G (with one part being composed of connection vertices), so |C | must be even and larger
than 4. See Figure EC.5 for an example with |C | = 12. Set V (C) can be partitioned as follows:
1. |C |/2 connection vertices: Each vertex in this category belongs to the same block as at least
some other connection vertex.
2. 2 vertices, which may be assignment vertices, yn , or z1 : These are the vertices located in the
extremities of the cycle according to the topology presented in Figure EC.5; on the left, we
have either z1 or the assignment vertex with facility of lower index in C, whereas on the right
we have either yn or the assignment vertex with facility of highest index in C. These vertices
stay either alone in their blocks (this is necessarily the case of z1 and yn ) or together with
other assignment vertices in the same block.
3. |C |/2 − 2 assignment vertices: These vertices are located in the middle of the cycle and stay
in the same block with at least one other assignment vertex, so the assignment conflict costs
involving these vertices is at least |C |/4 − 1.

ec20

e-companion to Bergman et al.: On the Minimum Chordal Completion Polytope

Connection vertices are distributed among k ≥ 2 (consecutive) blocks with bi ≥ 2 elements each,
1 ≤ i ≤ k. These vertices are associated with transition conflict penalties and transition penalties,
and the sum pc (C) of all penalties associated with them is
pc (C) =
Because 2 ≤ bi ≤

|C|
2

X bi (bi − 1)
X
bi bi+1 .
+
2
1≤i≤k
1≤i<k

− 2, we have bi bi+1 ≥ bi + bi+1 and b2i ≥ 2bi . Therefore,

X b2
X bi (bi − 1)
X
X bi
X
i
+
bi bi+1 ≥
−
+
(bi + bi+1 )
2
2 1≤i≤k 2 1≤i<k
1≤i<k
1≤i≤k
1≤i≤k
X
X bi
X
b1 + bk
|C | 3|C |
≥
2bi −
+
bi ≥ |C | −
≥ |C | −
=
.
2 1<i<k
2
4
4
1≤i≤k
1≤i≤k

pc (C) ≥

By summing all penalties, we have
p(C) ≥ −|C | + |C |/4 − 1 + pc (C) > −

3|C |
3|C |
−1+
> −1,
4
4

which is clearly larger than −3. Therefore, Alg can only return cycles C containing all type-z and
type-y vertices.



Lemma EC.6. Every cycle delivered by Alg is associated with a feasible assignment.
Proof.

Let us suppose by contradiction that Alg delivers a cycle C which is not associated with

a feasible assignment. From Lemma EC.5, it follows that every cycle delivered by Alg necessarily
contains at least one assignment vertex containing each facility. Thus, if the assignment associated with C is infeasible, then some location is being assigned to at least two different facilities.
Compensation penalties are not affected by this, so
q ∗ (C) = −3 −

β
.
K

As each assignment conflict cost is equal to 1, we have
p(C) = pL (C) + pQ (C) + q ∗ (C)
p(C) ≥ 1 + q ∗ (C) ≥ 1 − 3 −
and as

β
K

β
,
K

≤ 1, p(C) ≥ −3, and therefore C cannot be delivered by Alg.



ec21

e-companion to Bergman et al.: On the Minimum Chordal Completion Polytope

The previous lemmas show that Alg decides (−3)-QSCP positively on G using C only if C is a
matching cycle. A similar process can be used in order to construct a solution for (−3)-QSCP on G
given a feasible solution for the QAP instance; namely, just take the cycle containing the associated
assignment vertices, the connection vertices uniquely determined by the assignment vertices, and
all type-y and type-z vertices. Finally, as QAP is NP-complete and (−3)-QSCP is clearly in NP,
it follows that (−3)-QSCP is NP-complete. 
We conclude by reducing the (−3)-QSCP to the separation of I1. Let I be an instance of (−3)QSCP associated with graph G = (V, E) and quadratic cost function q : V × V → [0, 1]. We reduce I
to an instance I 0 of the separation of I1 associated with the same graph G = (V, E). The (potentially
fractional) solution x ∈ X(G) is derived from the quadratic cost function q of I as follows: if
e = {u, v } ∈ E C , xe = q(u, v). Note that x is valid, since xe ∈ [0, 1] for all e ∈ E and xe is not defined
if e ∈ E.
By construction, any chordless cycle C in G has a cost c(C) in I deciding (−3)-QSCP positively
has a cost c(C) such that
c(C) =

X

q(u, v) =

{u,v}∈E C (C)

X

xf < |C | − 3,

f ∈int(C)

that is, if C decides I positively, then C also decides I 0 positively. The same argument shows that
if C decides I 0 positively, then C is also a valid certificate for I. Finally, from Lemma EC.3, we
know that the separation of (I1) can be restricted to cycles which are chordless in G, so we conclude
that deciding whether I has a solution is equivalent to deciding whether I 0 has a solution. Thus,
we conclude that the separation of (I1) is NP-complete.

Proof of Theorem 5(b).



All coefficients of inequalities (I2) are non-negative, so we are able to

apply Theorem 3 in order to obtain the following inequalities:
x{vi−1 ,vi+1 } +

X
f :vi ∈f,{vi−1 ,vi+1 }∩f =∅

xf ≥

X

xf − |F (C)| + 1

f ∈F (C)

≥ 1−

X
f ∈F (C)

(1 − xf ).

(EC.1)

ec22

e-companion to Bergman et al.: On the Minimum Chordal Completion Polytope

P

Note that inequality (EC.1) is trivially satisfied if

f ∈F (C) xf

< |F (C)|, as the right-hand side

expression becomes zero and all coefficients on the left are non-negative.
Let x ∈ X(G) be a fractional solution; in abuse of notation, if {u, v } ∈ E(G), we assume
that x{u,v} = 1. By construction, solution x violates the inequality (EC.1) associated with cycle
C = (vi−1 , vi , vi+1 , v1 , v2 , . . . , vn ) if and only if
X

x{vi−1 ,vi+1 } +
0

X

x{vi ,t} +

t∈C 0 \{vi−1 ,vi ,vi+1 }

x{vi−1 ,vi+1 }

(1 − xf ) =⇒

f ∈F (C 0 )

t∈C \{vi−1 ,vi ,vi+1 }

x{vi−1 ,vi+1 } +

X

x{vi ,t} < 1 −
X

(1 − xf ) < 1 =⇒

f ∈F (C 0 )


X
x{vi ,vj } + x{vi ,vk }
+
+
(1 − x{vj ,vk } ) +
2
vi ∈{v
/ j ,vk }∈F (C 0 )
vi ∈{v
/ j ,vk }∈F (C 0 )
 


3x{vi ,vi+1 }
3x{vi−1 ,vi }
+ 1−
1−
2
2
X



Let Gi = (V (G), E(G)) be a complete weighted direct graph such that, for each edge e = {vj , vk }
in E(G),
w(e) =



x{v ,v } +x{v ,v }


1 − x{vj ,vk } + i j 2 i k , if vi ∈
/ { vj , v k }



+∞,

otherwise.

In order to separate inequalities (EC.1), it suffices to find a path in Gi connecting vi+1 to vi−1

 

3xv
3xvi ,vi+1
,vi
not passing through vi whose length is inferior to 1 − x{vi−1 ,vi+1 } − 1 − i−1
−
1
−
.
2
2
If such a path exists, then, in particular, any shortest path in Gi connecting vi+1 to vi−1 while
avoiding vi also satisfies this property, so the verification can be done in polynomial time for
each sequence (vi−1 , vi , vi+1 ) (e.g., the running time for simple implementations of Dijsktra’s algorithm is O(|V (G)|2 ). The number of sequences for which this verification needs to be performed is
O(|V (G)|3 ), so we conclude that inequality (EC.1) can be separated in polynomial time.
Proof of Theorem 5(c).



All coefficients of inequalities (I3) are non-negative, so we are able to

apply Theorem 3 in order to obtain the following inequalities:


X
X
xf ≥ 2 
xf − |F (C)| + 1 =⇒
f :{{vi ,vj }:dC (vi ,vj )=2}

X
f :{{vi ,vj }:dC (vi ,vj )=2}

f ∈F (C)

xf + 2

X

(1 − xf ) ≥ 2.

f ∈F (C)

(EC.2)

ec23

e-companion to Bergman et al.: On the Minimum Chordal Completion Polytope

Note that inequality (EC.2) is trivially satisfied if

P

f ∈F (C) xf

< |F (C)|, as the right-hand side

expression becomes zero and all coefficients on the left are non-negative.
Let x ∈ X(G) be a fractional solution; in abuse of notation, if {u, v } ∈ E(G), we assume
that x{u,v} = 1. Let D be a weighted directed graph such that, for each two-set {vi , vj } in V (G),
there is one vertex in V (D) labelled by pair (vi , vj ) and other labelled by pair (vj , vi ). Moreover,
for each pair of vertices (vi , vj ) and (vj , vk ) in V (D), vi 6= vk , we define an arc a = ((vi , vj ), (vj , vk ))
in A(D) whose weight is given by
wD (a) = wD ((vi , vj ), (vj , vk )) = (1 − x{vi ,vj } ) + x{vi ,vk } + (1 − x{vj ,vk } );
the first and the third terms of wD (a) can be interpreted as penalties associated with the absence
of edges {vi , vj } and {vj , vk } in G, whereas the second penalizes the existence of edge {vi , vk }.
Finally, note that path (v1 , v2 , . . . , vk ) in G is associated with path ((v1 , v2 ), (v2 , v3 ), . . . , (vk−1 , vk ))
in D (and vice-versa).
Let u, v, w, and x be vertices in V (G) such that PG = (u, v, w, x) is a path in G, and let
PD = (a1 , a2 , a3 ) be the associated path in D, with a1 = (u, v), a2 = (v, w), and a3 = (w, x). Let
PD0 = (v1 , v2 , . . . , vn ) be other path in D such that v1 = (x, z1 ), vi = (zi , zi+1 ), 1 ≤ i < n, and
vn = (zn , u); note that, by construction, arc ((a3 , v1 ), (vn , a1 )) belongs to A(D). If all elements in
{u, v, w, x, z1 , . . . , zn } are pairwise different, then CD = (a1 , a2 , a3 , v1 , . . . , vn ) is a directed cycle in D

associated with cycle CG = (u, v, w, x, z1 , . . . , zn ) in G.
We claim that CD is a directed cycle in D if PD0 is a shortest path in D connecting (x, z 0 )
to (z 00 , u), with z 0 , z 00 in V (G), whose internal vertices are not associated with edges in G containing
vertices in {u, v, w, x} and such that |PD0 | is minimal. As wD (a) ≥ 0 for all a ∈ A(D), it follows from
the last condition and from the fact that PD0 is a shortest path that all elements in {z1 , . . . , zn } are
necessarily pairwise different.
The sum of the costs of all edges cycle CD is given by
X

X

w((ai , ai+1 )) + w((a3 , v1 )) +

i∈[1,2]

w((vi , vi+1 )) + w((vn , a1 )) =

i∈[1,n−1]

X
f ∈{{a,b}:dC (a,b)=2}
G

xf + 2

X

(1 − xf ).

f ∈F (CG )

ec24

e-companion to Bergman et al.: On the Minimum Chordal Completion Polytope

Therefore, solution x does not respect the inequality (EC.2) associated with cycle CG in G containing path P = (u, v, w, x) if and only if the weight of PD0 is smaller than 2.
The number of tuples for which this verification needs to be performed is O(|V (G)|4 ), and
the identification (and construction) of a path PD0 with the desired features can be performed in
polynomial time (e.g., O(|V (D)|2 ) = O(|V (G)|4 ) using Dijkstra’s algorithm); therefore, we conclude
that Inequalities EC.2 can be separated in polynomial time.

Proof of Theorem 5(d).



We show this result by employing a construction that is very similar

to the one used in the proof of Theorem 5(a). More precisely, we introduce QSCP∗ , a variation
of QSCP that is more convenient for proving the hardness of (the simplified version of) (I4), and
show that the addition of a single compensation penalty to the construction used in the proof of
Theorem 5(a) yields the desired result.
Similarly to the QSCP, in the Adapted Quadratic Shortest Cycle Problem (QSCP∗ ) we are
given an undirected graph G = (V, E) and a quadratic cost function q : V × V → [0, 1] such that
q(u, v) = 0 if (u, v) ∈ E. A feasible solution for an instance of QSCP∗ consists of a simple chordless
cycle C = (v1 , v2 , . . . , v|C| ) whose cost p∗ (C) is given by
p∗ (C) =

X

q(u, v) − |C | −

{u,v}∈int∗ (C)

max

(q(vj−1 , vj+1 ) + q(vj , vi )).

i,j
i6=j
dC ({vj ,vi })≥2

Finally, α-QSCP∗ is the decision version of QSCP∗ in which the goal is to decide whether G admits
a simple chordless cycle C such that p∗ (C) < α.
The present proof also relies on a reduction of QAP to (−4)-QSCP∗ . Let I be an arbitrary
instance of QAP of size n and M be the largest individual (i.e., linear or quadratic) penalty that
may compose the cost of a feasible assignment. Note that K = 2M n2 is an upper bound on the
objective value of any feasible solution of I.
We show how to adapt the construction presented in the proof of Theorem 5(a) in order to
construct an instance I 0 of (−4)-QSCP∗ that admits solution if and only if the associated instance I

ec25

e-companion to Bergman et al.: On the Minimum Chordal Completion Polytope

of QAP admits an assignment whose cost is inferior to β. If Alg is an algorithm that decides
(−4)-QSCP∗ , then it will only return a cycle C containing the linear costs pL (C) and the quadratic
costs pQ (C) of I if
p∗ (C) = pL (C) + pQ (C) + q ∗ (C) −

max

(q(vj−1 , vj+1 ) + q(vj , vi )) < −4,

vi ,vj ∈V (C)
vi 6=vj
dC ({vj ,vi })≥2

where q ∗ (C) is the sum of −|C | with additional costs incorporated by our construction. The costs
of I are divided by K in I 0 , so the assignment associated with C is a solution if

pL (C) + pQ (C) <

β
.
K

Therefore, we define q ∗ (C) in the following way:
q ∗ (C) = −4 −

β
+
K

max

vi ,vj ∈V (C)
vi 6=vj
dC ({vj ,vi })≥2

(q(vj−1 , vj+1 ) + q(vj , vi )) .

Note that the difference between q ∗ (C) in this proof and q ∗ (C) in the proof of Theorem 5(a)
is −1 + maxi,j (q(vj−1 , vj+1 ) + q(vj , vi )). Moreover, in the original construction, one can see by
inspection that if C is a matching cycle, then

max

vi ,vj ∈V (C)
vi 6=vj
dC ({vj ,vi })≥2

(q(vj−1 , vj+1 ) + q(vj , vi )) ≤ 1 +

M
.
K

In order to guarantee equality in the inequality above for every matching cycle, we set

q(af1 ,lk , y1 ) =

M
K

for all lk ∈ L. By definition, M ≤ K, so q(af1 ,lk , y1 ) ≤ 1. With this modification, we have
q(vj−1 , vj+1 ) = 1 and q(vj , vi ) =

M
K

for vj−1 = cz1 ,f1 ,∅,lk , vj = af1 ,lk , vj+1 = cf1 ,f2 ,lk ,lz , and vi = y1 ,

lz , lk ∈ L. Moreover, for every matching cycle C, by direct substitution we have
q ∗ (C) = −3 −

β
M
+ .
K K

ec26

e-companion to Bergman et al.: On the Minimum Chordal Completion Polytope

The arguments used in the proof of Lemma EC.5 also apply to the present construction, so Alg
can only select cycles that include all type-y and type-z vertices. For Lemma EC.6, note that if C
contains assignments involving the same location or facility, then
p∗ (C) = pL (C) + pQ (C) + q ∗ (C) −

≥ 1−3−

max

(q(vj−1 , vj+1 ) + q(vj , vi ))

vi ,vj ∈V (C)
vi 6=vj
dC ({vj ,vi })≥2

M
β
+
> −3
K K

so Alg cannot decide (−4)-QSCP positively on G using C if C is associated with an infeasible
assignment.
Finally, the arguments used in the proof of Theorem 5(a) to show that (−3)-QSCP is NPcomplete can be used in an identical way in order to show that (−4)-QSCP is NP-complete, and
the problem of deciding the separation of (I4) can be reduced to (−4)-QSCP in the same way the
separation of (I1) was reduced to (−3)-QSCP, so we conclude that the separation of (I4) is also
NP-complete.



