# Construction of diagonal quintic threefolds with infinitely many rational
points

Maciej Ulas

###### Abstract.

In this note we present a construction of an infinite family of diagonal
quintic threefolds defined over $\mathbb{Q}$ each containing infinitely many
rational points. As an application, we prove that there are infinitely many
quadruples $B=(B_{0},B_{1},B_{2},B_{3})$ of co-prime integers such that for a
suitable chosen integer $b$ (depending on $B$), the equation
$B_{0}X_{0}^{5}+B_{1}X_{1}^{5}+B_{2}X_{2}^{5}+B_{3}X_{3}^{5}=b$ has infinitely
many positive integer solutions.

###### Key words and phrases:

diagonal quintic threefolds, polynomial solutions, quadratic forms, Gröbner
basis

###### 2020 Mathematics Subject Classification:

11D41, 13P15

##  1\. Introduction

Let $A=(A_{0},A_{1},A_{2},A_{3},A_{4})\in\mathbb{Z}^{5}$ be given and assume
that $\gcd(A)=1$. We consider the diagonal quintic form in five variables
given by

$F_{A}(X_{0},X_{1},X_{2},X_{3},X_{4})=\sum_{i=0}^{4}A_{i}X_{i}^{5},$

and a related diagonal quintic threefold defined as

$\mathcal{V}_{A}:\;F_{A}(X_{0},X_{1},X_{2},X_{3},X_{4})=0.$

The set of integer points on the variety $\mathcal{V}_{A}$ is denoted by
$\mathcal{V}_{A}(\mathbb{Z})$. We say that a point
$(X_{0},X_{1},X_{2},X_{3},X_{4})\in\mathcal{V}_{A}(\mathbb{Z})$ is non-trivial
if the greatest common divisor of the entries $X_{0},X_{1},X_{2},X_{3},X_{4}$
is equal to 1, and no proper sub-sum in the expression
$\sum_{i=0}^{4}A_{i}X_{i}^{5}$ vanish. In the sequel, by an integer point on
$\mathcal{V}_{A}$ we will mean a non-trivial one.

The question concerning the existence of integer points, or equivalently
rational points, on $\mathcal{V}_{A}$ is very difficult. In particular, if
$I=(1,1,1,1,1)$, the variety $\mathcal{V}_{I}$ is called the Fermat quintic
and it is an open question whether $\mathcal{V}_{A}(\mathbb{Z})$ is infinite.
Euler conjectured that there are no non-trivial points in
$\mathcal{V}_{I}(\mathbb{Z})$. However, in 1966, Lander and Parkin in [4]
found that $(27,84,110,133,-144)\in\mathcal{V}_{A}$, that is the following
equality holds

$27^{5}+84^{5}+110^{5}+133^{5}=144^{5}.$

The computer search was extended by others and two additional points were find
on $\mathcal{V}_{I}$. In 1997 Scher and Seidl found the point
$(5027,6237,14068,-220,-14132)$. The other one $(55,3183,28969,85282,-85359)$
was found by Frey. In fact, according to our best knowledge, there is no known
example of a vector $A\in\mathbb{Z}^{5}$ such that $\mathcal{V}_{A}$ contains
infinitely many non-trivial integer points and this motivated us to work on
this problem. Note that $\mathcal{V}_{A}\simeq\mathcal{V}_{I}$ over
$\mathbb{C}$. The geometry of $\mathcal{V}_{I}$ was investigated in many
papers. In particular, the geometry of lines on $\mathcal{V}_{I}$ was
investigated by Albano and Katz [1]. The question concerning the existence of
(complex) conics on $\mathcal{V}_{I}$ was the subject of PhD dissertation of
Xu [9], some experimental work of Testa [7] and recent work of A. M. Mustaţǎ
[5]. In this context let us recall that a generic quintic threefold contains
2875 lines and 609,250 conics. However, the findings of the mentioned authors
do not shed light on the question concerning non-emptiness of
$\mathcal{V}_{A}(\mathbb{Z})$.

Let us describe the content of the paper in some details. In Section 2 we
quickly eliminate the possibility of the existence of $A\in\mathbb{Z}^{5}$
with nonzero entries, such that the variety $\mathcal{V}_{A}$ contains a line
defined over $\mathbb{Q}$ giving infinitely many nontrivial rational points.
In Section 3 we present construction of a quadratic parametric solution of the
equation defining the variety $\mathcal{V}_{A}$ for suitable chosen values of
$A$. As an immediate application we get lower bound for the number of those
$A\in\mathbb{Z}^{5}$ satisfying $\gcd(A)=1$ and such that $\mathcal{V}_{A}$
has infinitely many integer points. More precisely, the number
$\mathcal{P}(N)$, of such $A\in\mathbb{Z}^{5}$ with
$\operatorname{max}(|A|)\leq N$ and $\gcd(A)=1$, satisfies $\mathcal{P}(N)\gg
N^{1/10}$. Finally, in the last section we prove that there are infinitely
many quadruples $B=(B_{0},B_{1},B_{2},B_{3})$ of co-prime integers such that
for a suitable chosen integer $b$ (depending on $B$), the equation
$B_{0}X_{0}^{5}+B_{1}X_{1}^{5}+B_{2}X_{2}^{5}+B_{3}X_{3}^{5}=b$ has infinitely
many positive integer solutions.

In our work we extensively used symbolic calculations, especially Gröbner
bases computations. All Gröbner bases were computed with the help of
Mathematica 13.2 computational package [8] running on a standard machine with
i7 type processor and 32 GB of RAM.

##  2\. Warm up

The first thing which comes to mind is to find linear polynomials and an
appropriate $A\in\mathbb{Z}^{5}$ such that on $\mathcal{V}_{A}$ there is a
line defined over $\mathbb{Q}$. In other words, for variables $u,v$, we take
$X_{i}=a_{i}u+b_{i}v$ for $i=0,\ldots,4$ and look for rational numbers
$a_{i},b_{i}$ such that

$\sum_{i=0}^{4}A_{i}(a_{i}u+b_{i}v)^{5}=0$

in the ring $\mathbb{Q}[u,v]$. In other words, we have a line lying on
$\mathcal{V}_{A}$. Because we are interested in the existence of nontrivial
points, there are $i,j\in\\{0,1,2,3,4\\}$ such that $i\neq j$ and linear forms
$a_{i}u+b_{i}v,a_{j}u+b_{j}v$ are not proportional. Thus, after linear change
of variables, without loss of generality, we can assume that $i=0,j=1$, and
$a_{0}=1,b_{0}=0,a_{1}=0,b_{1}=1$. Let $C_{i}$ be the coefficient of
$u^{i}v^{5-i}$ in the expansion of $\sum_{i=0}^{4}A_{i}(a_{i}u+b_{i}v)^{5}$
and consider the ideal $J$ generated by the polynomials
$C_{i},i=0,1,\ldots,5$. Moreover, let $\operatorname{Gb}(J)$ be a Gröbner
basis of the ideal $J$. Then, we have that

$\operatorname{Gb}(J)\cap\mathbb{Q}[a_{4},b_{4},A_{0},A_{1},A_{2},A_{3},A_{4}]=\\{a_{4}^{2}b_{4}^{3}A_{0}A_{1}A_{4},a_{4}^{3}b_{4}^{2}A_{0}A_{1}A_{4}\\},$

and quick computation reveals that any solution of the system
$C_{i}=0,i=0,\ldots,5$, leads to lines which generate only trivial points on
$\mathcal{V}_{A}$. Let us note that essentially the same result can be
obtained by using [1, Proposition 1.3], which says that if $L$ is a line
contained in $\mathcal{V}_{A},A=(1,1,1,1,1)$, then $L$ goes through a point
with 3 coordinates equal to 0.

In any way, the failure of the above approach suggests that if we want to
construct parametric solution of the equation defining $\mathcal{V}_{A}$, or
equivalently, a rational curve lying on $\mathcal{V}_{A}$, we need to look for
parametric solutions given by polynomials of degrees $>1$.

##  3\. The construction of a quadratic parametrization

In this section we will find one parameter family of 5-tuples $A$ such that
$\mathcal{V}_{A}$ contains the curve defined by quadratic forms. It is
tempting to work with the general form of such a curve, i.e., try to find
values $A\in\mathbb{Z}_{5}$ and $a_{i},b_{i},c_{i}\in\mathbb{Q}$ such that
$X_{i}(u,v)=a_{i}u^{2}+b_{i}uv+c_{i}v^{2},i=0,\ldots,4$, satisfy the identity

$0=\sum_{i=0}^{4}A_{i}(a_{i}u^{2}+b_{i}uv+c_{i}v^{2})^{5}=\sum_{j=0}^{10}D_{j}u^{10-j}v^{j},$

in the ring $\mathbb{Q}[u,v]$. Treating $a_{i},b_{i},c_{i},A_{i}$ for
$i=0,\ldots,4,$ as independent variables, we have that
$D_{j}\in\mathbb{Z}[A_{0},\ldots,A_{4},a_{0},\ldots,c_{4}]$. Thus, we are
interested in finding rational solutions of the system

$\mathcal{S}:\;D_{j}=0,\quad j=0,1,\ldots,10.$

To be more specific note that we are playing with a system involving 20
variables and 11 homogeneous polynomials. A naive count $20-11-1=8$ suggests
that the dimension of the variety defined by the system $\mathcal{S}$ is 8 and
the expectation that $\mathcal{S}$ has solutions in rational numbers is
reasonable. However, the resulting system is too complicated to be fully
investigated. Although we were trying quite hard, we were unable to solve
$\mathcal{S}$ without any additional assumptions on the shape of the form
$X_{i}(u,v)$. Thus, instead of working with the general quadratic forms, we
decided to work with forms

$\displaystyle X_{0}=s_{0}(u,v)=uv,$ $\displaystyle
X_{1}=s_{1}(u,v)=u^{2}-auv+v^{2},$ $\displaystyle
X_{2}=s_{2}(u,v)=u^{2}+auv+v^{2},$ $\displaystyle
X_{3}=s_{3}(u,v)=u^{2}+buv+cv^{2},$ $\displaystyle
X_{4}=s_{4}(u,v)=u^{2}+duv+ev^{2},$

where $a,b,c,d,e\in\mathbb{Q}$ need to be determined. Thus, let $C_{i}$ be the
$i$-th coefficient in the expansion

$\sum_{i=0}^{4}A_{i}s_{i}(u,v)^{5}=\sum_{i=0}^{10}C_{i}u^{i}v^{10-i}.$

We are interested in the rational solutions of the system

$\mathcal{S}^{\prime}:\;C_{i}=0,\quad i=0,1,\ldots,10,$

and, without loss of generality, we can assume that $A_{4}=1$.

Let us observe that the variable $A_{0}$ appears only in one polynomial, i.e.,
in $C_{5}$, and with the exponent 1. That means that it is enough to find
solutions of the system $C_{i}=0$ for $i\in\\{0,\ldots,10\\}\setminus\\{5\\}$,
and then compute the value of $A_{0}$ from $C_{5}=0$. We are thus working with
the polynomials lying in the ring $\mathbb{Q}[A_{1},A_{2},A_{3},a,b,c,d,e]$.

Let $I=<C_{0},\ldots,C_{4},C_{6},\ldots,C_{10}>$ denote the ideal generated by
the polynomials $C_{i}$ for $i\in\\{0,1,\ldots,10\\}\setminus\\{5\\}$. One can
compute the Gröbner basis $\operatorname{Gb}(I)$ of the ideal $I$. It contains
32 polynomials. The computation of the full basis took around 13 minutes.
However, for our purposes it is better to work with the basis containing
polynomials in variables $A_{3},e$ only. We have that

$\operatorname{Gb}(I)\cap\mathbb{Z}[A_{3},e]=\\{F_{1},F_{2},F_{3}\\},$

where

$F_{1}=\left(A_{3}+1\right)(e-1)^{6}\left(e^{2}+e+1\right)\left(3e^{2}+2e+3\right).$

Because $A_{3},e$ need to be rational we have that $(A_{3}+1)(e-1)=0$. First,
we consider the case $A_{3}+1=0$. Adding the polynomial $A_{3}+1$ to the ideal
$I$ we get the ideal $I^{\prime}$. The Gröbner basis
$\operatorname{Gb}(I^{\prime})$ of the ideal $I^{\prime}$ takes the form:

$\displaystyle\operatorname{Gb}(I^{\prime})=\\{$ $\displaystyle
c-e,(b-d)(e^{4}-1)(b-d),(b-d)(e^{2}-1)(d^{2}+2e),b^{2}-d^{2},$
$\displaystyle(b-d)(a^{2}-d^{2}-2e+2),A_{3}+1,(b-d)(e^{2}-1)(ad-2A_{2}),$
$\displaystyle(b-d)(ad+A_{2}d^{2}+2eA_{2}-2A_{2}),2aA_{2}-b+d,A_{1}+A_{2}\\}.$

It is clear that the necessary condition for the existence of rational
solutions of the system $\mathcal{S}^{\prime}$ is the existence of rational
solutions of the system, say $\mathcal{S}^{\prime\prime}$, defined by the
vanishing of each entry from $\operatorname{Gb}(I^{\prime})$. Simple
computation with the Mathematica procedure Solve reveals that
$\mathcal{S}^{\prime\prime}$ has only one, up to sign changes and
permutations, solution which may be useful. This solution has the following
form

$\begin{array}[]{llll}a=-\sqrt{d^{2}-4},&b=-d,&c=-1,&e=-1,\\\
A_{0}=64d(d^{2}-2),&A_{1}=\frac{d}{\sqrt{d^{2}-4}},&A_{2}=-A_{1},&A_{3}=-1.\end{array}$

There are also other solutions but they are defined over nontrivial algebraic
extensions of $\mathbb{Q}$ or lead to non interesting equalities
$s_{1}(u,v)=s_{2}(u,v),s_{3}(u,v)=s_{4}(u,v)$. To make the expression
$a=-\sqrt{d^{2}-4}$ rational one can use the substitution $d=(-1-t^{2})/t$,
where $t$ is a rational parameter. Thus, after necessary simplifications we
obtain $A(t)=(A_{0}(t),A_{1}(t),A_{2}(t),A_{3}(t),A_{4}(t))$, where

$A_{0}(t)=64t^{2}(1-t^{8}),\quad A_{1}(t)=-A_{2}(t)=t^{2}+1,\quad
A_{3}(t)=-A_{4}(t)=t^{2}-1$

and note that on the quintic threefold $\mathcal{V}_{A(t)}$ there is a
rational curve defined by the quadratic forms

(1) $\begin{cases}\begin{array}[]{lll}X_{0}&=&s_{0}(u,v)=uv,\\\
X_{1}&=&s_{1}(u,v)=tu^{2}+(t^{2}-1)uv+tv^{2},\\\
X_{2}&=&s_{2}(u,v)=tu^{2}-(t^{2}-1)uv+tv^{2},\\\
X_{3}&=&s_{3}(u,v)=tu^{2}-(t^{2}+1)uv-tv^{2},\\\
X_{4}&=&s_{4}(u,v)=tu^{2}+(t^{2}+1)uv-tv^{2}.\end{array}\end{cases}$

We are left with the case $e-1=0$. We apply exactly the same procedure as in
the case $A_{3}+1=0$ and find that there are no solutions which lead to
nontrivial identities. Summing up, we thus proved

######  Theorem 3.1.

Let $t\in\mathbb{Z}\setminus\\{-1,0,1\\}$ and put
$A(t)=(A_{0}(t),\ldots,A_{4}(t))$. The variety $\mathcal{V}_{A(t)}$ contains
infinitely many non-trivial integer points.

######  Remark 3.2.

In this context one can recall that there are quadratic parametrizations
living on the diagonal surface $X_{0}^{k}+X_{1}^{k}=X_{2}^{k}+X_{3}^{k}$, for
$k=5,6,7$. However, these parametrizations are defined over non-trivial
algebraic extension of $\mathbb{Q}$ (see the discussion in [2] and the work of
Reznick concerning linear relations between powers of binary quadratic forms
[6]).

We define the following counting function

$\mathcal{P}(N)=\\#\\{A=(A_{0},\ldots,A_{4}):\;\operatorname{max}\\{|A_{i}|\\}\leq
N,\gcd(A)=1,\;\mbox{and}\;\mathcal{V}_{A}(\mathbb{Z})\;\mbox{is infinite}\\}.$

Our findings allow us to deduce the following

######  Theorem 3.3.

We have $\mathcal{P}(N)\gg N^{1/10}$.

###### Proof.

For a given $t\in\mathbb{Z}\setminus\\{-1,0,1\\}$ we take
$A(t)=(A_{0}(t),\ldots,A_{4}(t))$ and observe that
$\gcd(A_{0}(t),\ldots,A_{4}(t))=1$ for even values of $t$. If $t$ is odd, we
have that $\gcd(A_{0}(t),\ldots,A_{4}(t))=2$. We clearly have
$\operatorname{max}\\{|A_{i}(t)|:\;i=0,1,2,3,4\\}=64t^{2}(t^{8}-1)$. Thus the
number of $A$’s such that $\operatorname{max}\\{|A_{i}|:\;i=0,1,2,3,4\\}\leq
N$ and $\mathcal{V}_{A}$ has infinitely many non-trivial integer points is not
smaller than the number of solutions of the inequality $64t^{2}(t^{8}-1)\leq
N$, i.e., we have at least $t\gg N^{1/10}$ positive integer values satisfying
required properties. We thus have $\mathcal{P}(N)\gg N^{1/10}$. ∎

######  Remark 3.4.

Let us observe that the solutions of $F_{t}(X_{0},\ldots,X_{4})=0$ given by
$X_{i}=s_{i}(u,v),i=0,\ldots,4$, we already constructed, satisfy two
additional equations, i.e.,

$L(X_{0},\ldots,X_{4})=Q(X_{0},\ldots,X_{4})=0,$

where

$L=4X_{0}+X_{1}-X_{2}+X_{3}-X_{4},\quad
Q=X_{1}^{2}+X_{2}^{2}-X_{3}^{2}-X_{4}^{2}.$

It is interesting to note that the forms $L,Q$ do not depend on $t$. Thus, for
given $A\in\mathbb{Z}^{5}$, it is natural to define the variety

$\mathcal{C}_{A}:\;F_{A}(X_{0},\ldots,X_{4})=L(X_{0},\ldots,X_{4})=Q(X_{0},\ldots,X_{4})=0.$

One can check that for a generic choice of the vector $A\in\mathbb{Z}^{5}$,
the variety $\mathcal{C}_{A}$ is a curve of genus $>1$. However, as we have
seen the genus of $\mathcal{C}_{A}$ can drop to 0. From Faltings theorem (see
[3]) we know that the necessary condition for $\mathcal{C}_{A}$ to have
infinitely many rational points is when the genus is $\leq 1$. We thus
formulate the following

######  Problem 3.5.

Characterize all 5-tuples of integers $A=(A_{0},\ldots,A_{4})$ such that the
curve $\mathcal{C}_{A}$ has genus $\leq 1$.

##  4\. An application

In this section we present a curious application of our construction of
solutions of the equation defining $\mathcal{V}_{A(t)}$. More precisely, we
construct infinitely many diagonal quintic forms
$G_{t},t\in\mathbb{Z}\setminus\\{-1,0,1\\}$, in four variables, and such that
the equation $G_{t}(X_{0},X_{1},X_{2},X_{3})=R(t)$ has infinitely many integer
solutions for suitable chosen integer $R(t)$.

Before we go on, let us recall the following well know property of Pell type
equation $V^{2}-dU^{2}=a$, where $a\in\mathbb{Z}\setminus\\{0\\}$ and
$d\in\mathbb{N}$ is not a square. If $(u,v)$, where $uv\neq 0$, is an integer
solution of this equation, and $(X_{0},Y_{0})$ is the fundamental solution of
the Pell equation $Y^{2}-dX^{2}=1$, then for each $n\in\mathbb{N}_{+}$, the
pair $(U_{n},V_{n})$ defined by the equality

$V_{n}+U_{n}\sqrt{d}=(v+u\sqrt{d})(Y_{0}+X_{0}\sqrt{d})^{n}$

is a solution of the equation $V^{2}-dU^{2}=a$. In particular, the existence
of one solution $(u,v),uv\neq 0$, of the equation $V^{2}-dU^{2}=a$ implies the
existence of infinitely many solutions.

######  Lemma 4.1.

The equation

(2) $s_{3}(u,v)=s_{3}(1,1)=-t^{2}-1,$

where $s_{3}(u,v)$ is given in (1), has infinitely many solutions $u,v$ in the
ring $\mathbb{Z}\left[\frac{1}{2},t\right]$.

###### Proof.

Let us note the equation (2) can be written in the following form

(3) $V^{2}-(t^{4}+6t^{2}+1)U^{2}=4t(t^{2}+1),$

where $V=2tv+(1+t^{2})u,U=u$. Let us write $P(t)=t^{4}+6t^{2}+1$. Thus, we
consider Pell type equation and look for solutions $U,V$ satisfying congruence
condition $V\equiv(1+t^{2})U\mkern 4.0mu({\operator@font mod}\mkern 6.0mu2t)$.

Let us note that (3) has a non trivial solution $(V,U)=((t+1)^{2},1)$.
Moreover, the Pell equation

$Y^{2}-P(t)X^{2}=1$

has the fundamental solution

$Y_{0}=Y_{0}(t)=\frac{1}{4}(t^{2}+1)(t^{2}+5),\quad
X_{0}=X_{0}(t)=\frac{1}{4}(t^{2}+3).$

As a consequence, we get that for each $n\in\mathbb{N}$ the pair
$(V_{n},U_{n})$ defined by

$V_{n}+U_{n}\sqrt{P(t)}=\left((t+1)^{2}+\sqrt{P(t)}\right)^{n}\left(\frac{1}{4}(t^{2}+1)(t^{2}+5)+\frac{1}{4}(t^{2}+3)\sqrt{P(t)}\right),$

is a solution of (3). Next, to obtain solutions of (2) we need to know that
$(V_{n}\equiv(1+t^{2})U_{n})/2t\in\mathbb{Z}\left[\frac{1}{2},t\right]$.
However, a simple induction on $n$ confirms that this is the case. Finally,
for each $n\in\mathbb{N}$ the pair $(v_{n},u_{n})$, where

(4) $u_{n}=U_{n},\quad v_{n}=\frac{1}{2t}(V_{n}-(1+t^{2})U_{n}),$

is a solution of (2). To see an example we take $n=1$ and get

$u_{1}=\frac{1}{2}(t^{4}+t^{3}+5t^{2}+3t+4),\quad
v_{1}=\frac{1}{2}(t^{3}+t^{2}+3t+1).$

For $n=2$ we get

$\displaystyle u_{2}$
$\displaystyle=\frac{1}{4}\left(t^{8}+t^{7}+11t^{6}+9t^{5}+39t^{4}+23t^{3}+49t^{2}+15t+16\right),$
$\displaystyle v_{2}$
$\displaystyle=\frac{1}{4}\left(t^{7}+t^{6}+9t^{5}+7t^{4}+23t^{3}+11t^{2}+15t+1\right).$

∎

######  Remark 4.2.

Using standard methods it is not difficult to prove that the following
continued fraction expansion

$\sqrt{(2t+1)^{4}+6(2t+1)^{2}+1}=[4t^{2}+4t+3;\overline{1,t^{2}+t-1,1,2(4t^{2}+4t+3)}]$

holds. Thus, if we replace $t$ by $2t+1$ in (2), then the resulting equation
has infinitely many solutions in the ring $\mathbb{Z}[t]$.

We are ready to prove the following.

######  Theorem 4.3.

Let
$G_{t}(X_{0},X_{1},X_{2},X_{3})=(t^{2}+1)(X_{0}^{5}-X_{1}^{5})+(1-t^{2})X_{2}^{5}+64t^{2}(1-t^{8})X_{3}^{5}$.
For each $t\equiv 1\mkern 4.0mu({\operator@font mod}\mkern 6.0mu2)$, the
Diophantine equation

$G_{t}(X_{0},X_{1},X_{2},X_{3})=(t^{2}-1)(t^{2}+1)^{5}$

has infinitely many solutions in integers.

###### Proof.

To get the proof it is enough to use the polynomials $u_{n},v_{n}$ given by
(4). Indeed, we know that $s_{3}(u_{n},v_{n})=-t^{2}-1$. Thus, for each
$n\in\mathbb{N}_{+}$ we can take

$X_{0,n}=s_{1}(u_{n},v_{n}),X_{1,n}=s_{2}(u_{n},v_{n}),X_{2,n}=s_{4}(u_{n},v_{n}),X_{3,n}=s_{0}(u_{n},v_{n})$

and observe that
$G_{t}(X_{0,n},X_{1,n},X_{2,n},X_{3,n})=(t^{2}-1)(t^{2}+1)^{5}$. ∎

For $B=(B_{0},B_{1},B_{2},B_{3})\in\mathbb{Z}^{4}$ let us put

$G_{B}(X_{0},X_{1},X_{2},X_{4})=B_{0}X_{0}^{5}+B_{1}X_{1}^{5}+B_{2}X_{2}^{5}+B_{3}X_{3}^{5}$

and define the counting function

$C_{b,B}(N)=\\#\\{(X_{0},X_{1},X_{2},X_{3})\in\mathbb{N}:\;|X_{i}|\leq
N\;\mbox{and}\;G_{B}(X_{0},X_{1},X_{2},X_{3})=b\\}.$

From Theorem 4.3 we immediately get the following.

######  Corollary 4.4.

There are infinitely many $B\in\mathbb{Z}^{4}$ satisfying $\gcd(B)=1$ and such
that there is an integer $b$ depending on $B$, such that

$C_{b,B}(N)\gg\log N.$

###### Proof.

For $t\in\mathbb{Z}\setminus\\{-1,0,1\\}$ take
$B=(t^{2}+1,-t^{2}-1,1-t^{2},64t^{2}(1-t^{8}))$ and
$b=(t^{2}-1)(t^{2}+1)^{5}$. ∎

######  Example 4.5.

We take $t=3$. From Theorem 4.3, we know that the equation

(5) $5X_{0}^{5}-5X_{1}^{5}-4X_{2}^{5}-1889280X_{3}^{5}=2^{7}5^{5}$

has infinitely many solutions in positive integers. Using the formulas for
$X_{i,n},i=0,1,2,3$, from the proof of Theorem 4.3, one can compute small
solutions of our equation. The solutions corresponding to $n=2,3$ are

$(37526,6982,38170,1909),\quad(183773534,34226638,186933610,9346681).$

Note that the obtained family of integer solutions does not cover all integer
solutions of (5). Indeed, due to reducibility of the quintic form
$5(X_{0}^{5}-X_{1}^{5})$, one can find all integer solutions of (5) satisfying
the condition $\operatorname{max}\\{|X_{2}|,|X_{3}|\\}\leq 10^{3}.$ In this
range we have the solutions

$\displaystyle(-166,-38,-170,-8),(38,166,-170,-8),(2,-14,10,1),\;(14,-2,10,1),$
$\displaystyle(-10,-90,90,5),\;(90,10,90,5),(-94,-542,550,28),\;(542,94,550,28).$

######  Remark 4.6.

According to our best knowledge, in the above result we have the first
explicit example of a diagonal quintic form $F$ in four variables and such
that there is an integer $b$ for which the Diophantine equation
$F(X_{0},X_{1},X_{2},X_{3})=b$ has infinitely many integer solutions
satisfying the condition $X_{0}X_{1}X_{2}X_{3}\neq 0$.

## Appendix

Coefficients $C_{i}$ (up to constant factor) in the expansion of the
polynomial

$\sum_{i=0}^{4}A_{i}s_{i}(u,v)^{5}=\sum_{j=0}^{10}C_{j}u^{10-j}v^{j}$

are given by:

$\displaystyle C_{0}$ $\displaystyle=A_{1}+A_{2}+A_{3}+1,$ $\displaystyle
C_{1}$ $\displaystyle=-aA_{1}+aA_{2}+A_{3}b+d,$ $\displaystyle C_{2}$
$\displaystyle=(2a^{2}+1)A_{1}+2a^{2}A_{2}+(2b^{2}+c)A_{3}+2d^{2}+e,$
$\displaystyle C_{3}$
$\displaystyle=-a(a^{2}+2)A_{1}+a(a^{2}+2)A_{2}+b(b^{2}+c)A_{3}+d^{3}+2de,$
$\displaystyle C_{4}$
$\displaystyle=(a^{4}+6a^{2}+2)(A_{1}+A_{2})+(b^{4}+6b^{2}c+2c^{2})A_{3}+d^{4}+6d^{2}e+2e^{2},$
$\displaystyle C_{5}$ $\displaystyle=A_{0}+a(a^{4}+20a^{2}+30)(A_{2}-A_{1})$
$\displaystyle\quad+b(b^{4}+20b^{2}c+30c^{2})A_{3}+d(d^{4}+20d^{2}e+30e^{2}),$
$\displaystyle C_{6}$
$\displaystyle=(a^{4}+6a^{2}+2)(A_{1}+A_{2})+c(b^{4}+6b^{2}c+2c^{2})A_{3}+e(d^{4}+6d^{2}e+2e^{2}),$
$\displaystyle C_{7}$
$\displaystyle=-a(a^{2}+2)A_{1}+a(a^{2}+2)A_{2}+bc^{2}(b^{2}+2c)A_{3}+de^{2}(d^{2}+2e),$
$\displaystyle C_{8}$
$\displaystyle=(2a^{2}+1)A_{1}+(2a^{2}+1)A_{2}+c^{3}(2b^{2}+c)A_{3}+2d^{2}e^{3}+e^{4},$
$\displaystyle C_{9}$ $\displaystyle=-aA_{1}+aA_{2}+A_{3}bc^{4}+de^{4},$
$\displaystyle C_{10}$ $\displaystyle=c^{5}A_{3}+A_{1}+A_{2}+e^{5}.$

The computation of the Gröbner basis $\operatorname{Gb}(I)$ of the ideal
$I=<C_{0},\ldots,C_{4},C_{6},\ldots,C_{10}>$ was performed with the procedure

GroebnerBasis$[I,\\{A_{1},A_{2},A_{3},a,b,c,d,e\\}]$.

The computation took around 17 minutes.

The computation of the intersection
$\operatorname{Gb}(I)\cap\mathbb{Q}[A_{3},e]$ was performed with the procedure

GroebnerBasis$[I,\\{A_{1},A_{2},A_{3},a,b,c,d,e\\},\\{A_{1},A_{2},a,b,c,d\\}]$.

The computation took less than 7 minutes.

The computation of the Gröbner basis $\operatorname{Gb}(I^{\prime})$ of the
ideal $I^{\prime}=<A_{3}+1,I>$ was performed with the procedure

GroebnerBasis$[I^{\prime},\\{A_{1},A_{2},A_{3},a,b,c,d,e\\}]$.

The computation took less than a second. To solve the resulting equations from
the set $\operatorname{Gb}(I^{\prime})=\\{f_{1},\ldots,f_{10}\\}$, we used the
procedure

Solve$[\\{f_{1},\ldots,f_{10}\\}=\\{0,\ldots,0\\},\\{A_{1},A_{2},A_{3},a,b,c,d,e\\}]$.

Acknowledgements. The author is grateful to two anonymous referees for a
careful reading of the paper and many suggestions which improved the
presentation.

## References

  * [1] A. Albano, S. Katz, Lines on the Fermat Quintic Threefold and the Infinitesimal Generalized Hodge Conjecture, Trans. Amer. Math. Soc. 324 (1) (1991), 353–368.
  * [2] N. D. Elkies, The ABC’s of number theory, Harvard Math. Rev. 1 (2007), 64–76.
  * [3] G. Faltings, Endlichkeitssätze für abelsche Varietäten über Zahlkörpern, Invent. Math., 73(3) (1983), 349–366.
  * [4] L. J. Lander, T. R. Parkin, Counterexample to Euler’s conjecture on sums of like powers, Bull. Amer. Math. Soc. 72(6) (1966), 1079–1079.
  * [5] A. M. Mustaţǎ, Singular plane sections and the conics in the Fermat quintic threefold, Pure Appl. Math. Q. 18(4) (2022), 1689–1721.
  * [6] B. Reznick, Linearly dependent powers of binary quadratic forms, Pac. J. Math. 303 (2) (2019), 729–755.
  * [7] D. Testa, Conics on the Fermat quintic threefold, talk on the Junior Number Theory Seminar, October 11, 2010. Mathematical Insitute, Oxford. Avaliable at: https://math.columbia.edu/ dejong/reu/lib/exe/fetch.php%3Fmedia=beamerjnts.pdf
  * [8] Wolfram Research, Inc., Mathematica, Version 13.2. (Champaign, IL, 2022).
  * [9] S. Xu, Degree 2 curves in the Dwork pencil, PhD Dissertation, Ohio State University (2008).

Maciej Ulas, Jagiellonian University, Institute of Mathematics, Łojasiewicza
6, 30-348 Kraków, Poland; email<EMAIL_ADDRESS>


#  $\ell_{1}$-Norm Minimization with Regula Falsi Type Root Finding Methods

Metin Vural, Aleksandr Y. Aravkin, and Sławomir Stańczak

###### Abstract

Sparse level-set formulations allow practitioners to find the minimum 1-norm
solution subject to likelihood constraints. Prior art requires this constraint
to be convex. In this letter, we develop an efficient approach for nonconvex
likelihoods, using Regula Falsi root-finding techniques to solve the level-set
formulation. Regula Falsi methods are simple, derivative-free, and efficient,
and the approach provably extends level-set methods to the broader class of
nonconvex inverse problems. Practical performance is illustrated using
$\ell_{1}$-regularized Student’s t inversion, which is a nonconvex approach
used to develop outlier-robust formulations.

###### Index Terms:

$\ell_{1}$-norm minimization, nonconvex models, Regula-Falsi, root-finding

##  I Introduction

Sparse recovery using $\ell_{1}$-norm minimization plays a major role in many
signal processing applications. Denoting $\textbf{y}\in\mathbb{R}^{M}$ as a
measurement vector, $\mbox{D}\in\mathbb{R}^{M\times N}$ as an overcomplete
matrix with $M<N$, and $\rho$ as the penalty that measures the data misfit,
the ‘noise-aware’ level-set problem is to minimize $\ell_{1}$-norm subject to
a misfit or likelihood constraint:

$(\mbox{P}_{\sigma})\ \ \ \ \
\underset{\textbf{x}\in\mathbb{R}^{N}}{\mbox{minimize}}\ \
\left\|\textbf{x}\right\|_{1}\ \ \mbox{s.t.}\ \
\rho(\textbf{y}-\mbox{D}\textbf{x})\leq\sigma,\ \ $

where $\sigma$ indicates the noise level. $\mbox{P}_{\sigma}$ is used in many
applications, including compressed sensing [1] [2], overcomplete signal
representation [3], [4], coding theory [5], and image processing [6].

An efficient way to solve $(\mbox{P}_{\sigma})$ is to develop an explicit
relationship with a simpler problem that can be directly solved with primal-
only methods, such as the prox-gradient algorithm [7]:

$(\mbox{P}_{\tau})\ \ \ \ \
\underset{\textbf{x}\in\mathbb{R}^{N}}{\mbox{minimize}}\ \ \
\rho(\textbf{y}-\mbox{D}\textbf{x})\ \ \mbox{s.t.}\ \
\left\|\textbf{x}\right\|_{1}\leq\tau.\ $

Exploiting the relationship between $\mbox{P}_{\sigma}$ and $\mbox{P}_{\tau}$
allows one to specify the noise tolerance $\sigma$, and then find the solution
by inexactly optimizing a sequence of simpler $(\mbox{P}_{\tau})$ problems.

It has been known for a long time that $(\mbox{P}_{\tau})$ and
$(\mbox{P}_{\sigma})$ can provide equivalent solutions [8], and the idea of
solving $(\mbox{P}_{\tau})$ to obtain the solution of $(\mbox{P}_{\sigma})$
was first proposed by [9, 10]. Their idea follows the optimality trade-off
between the minimum $\ell_{1}$-norm and the least squares data misfit, which
generates a differentiable convex Pareto frontier. This optimality tracing is
formulated as a non-linear equation root finding problem, i.e. getting the
exact $\tau$ for a given noise tolerance $\sigma$, and is solved by an inexact
Newton Method. The resulting level-set approach has been generalized to other
instances of convex programming by [11, 7].

In the most general case, the relationship between $(\mbox{P}_{\tau})$ and
$(\mbox{P}_{\sigma})$ does not require convexity [11, Theorem 2.1]. However,
practical implementations of the root-finding approach require convexity of
the Pareto frontier to guarantee success of the root finding procedure,
limiting the approach to the convex case. Current implementations favor
Newton’s method, which requires derivatives. To address this issue, an
extension using an inexact secant method has also been developed [7].

In this paper, we introduce Regula Falsi type derivative-free non-linear
equation root finding schemes to solve $(\mbox{P}_{\sigma})$. They are
bracketing type methods that offer convergence guarantee for convex and
nonconvex models with the proper choices of root searching interval: two
initial points with the opposite signs assures convergence [12]. Regula Falsi
type methods do not require convexity to trace the root, allowing nonconvex
loss functions in the $(\mbox{P}_{\sigma})$ formulations. Finally, these
methods are also derivative free. All of these advantages allow Regula Falsi
type methods to be applied to cases where Newton, secant, and their variants
are not guaranteed to converge.

Moving outside of the convex class opens the way for using many useful
nonconvex models in $(\mbox{P}_{\sigma})$ formulations. For example, in [13]
and [14] consider mixture models whose negative log-likelihood are nonconvex,
with applications to high-dimensional inhomogeneus data where number of
covariates could be larger than sample size. A second application area uses
nonconvex Student’s t likelihoods to develop outlier-robust approaches [15,
16, 17]. In this paper, we show how Regula Falsi type root finding methods can
be used with the nonconvex Student’s t loss, as well the convex least-squares
and Huber losses.

This paper is organized as follows. In Section II, a Pareto frontier that
reveals the relation between $(\mbox{P}_{\tau})$ and $(\mbox{P}_{\sigma})$ is
defined and Regula Falsi type methods are introduced. Section III presents the
proposed $(\mbox{P}_{\sigma})$ solver while the simulation results are
discussed in Section IV.

##  II Pareto Frontier and Regula Falsi-Type Root Finding Methods

Under simple ‘active constraint’ conditions, problems $(\mbox{P}_{\tau})$ and
$(\mbox{P}_{\sigma})$ are equivalent for some pair $(\tau,\sigma)$ [11].
Pareto frontier approaches use root finding and inexact solutions to a
sequence of $(\mbox{P}_{\tau})$ to solve $(\mbox{P}_{\sigma})$.

###  II-A Pareto Optimality

###### Definition 1

i) Pareto optimal is the minimal achievable feasible point of a feasible set.
ii) The set that comprised of Pareto optimal points is called the Pareto
frontier.

In this work, we also seek to solve $(\mbox{P}_{\sigma})$ by working with
$(\mbox{P}_{\tau})$. Specifically, we are interested in the optimal objective
value of the $(\mbox{P}_{\tau})$ for a given y and $\tau$ which can be
expressed with following

$\nu(\tau):=\underset{\textbf{x}}{\inf}\\{\rho(\mbox{D}\textbf{x}-\textbf{y})|\
\left\|\textbf{x}\right\|_{1}\leq\tau\\},$ (1)

and the corresponding Pareto frontier can be defined as

$\psi(\tau):=\nu(\tau)-\sigma.$ (2)

###### Theorem 1

i) If $\rho$ is a convex function (e.g. $\ell_{2}$-norm, Huber function), then
so is $\psi$. ii) If $\rho$ is a nonconvex function, convexity of $\psi$ does
not follow. When $\rho$ is quasi-convex function, then so is $\psi$.

###### Proof 1

Let us consider any two solutions $\textbf{x}_{1}$ and $\textbf{x}_{2}$ of
$(\mbox{P}_{\tau})$ for any $\tau_{1}$ and $\tau_{2}$ respectively. Since
$\ell_{1}$-norm is convex, for any $\beta\in[0,1]$ following holds

$\begin{split}\left\|\beta\textbf{x}_{1}+(1-\beta)\textbf{x}_{2}\right\|_{1}\leq\beta\left\|\textbf{x}_{1}\right\|_{1}+(1-\beta)\left\|\textbf{x}_{2}\right\|_{1}\\\
=\beta\tau_{1}+(1-\beta)\tau_{2}.\ \ \ \ \ \ \ \ \ \end{split}$ (3)

An immediate outcome of eq. (3) is that
$\beta\textbf{x}_{1}+(1-\beta)\textbf{x}_{2}$ is a feasible point of
$(\mbox{P}_{\tau})$ with $\tau=\beta\tau_{1}+(1-\beta)\tau_{2}$. Thus we can
write the following inequality

$\begin{split}\nu(\beta\tau_{1}+(1-\beta)\tau_{2})\leq\rho(\mbox{D}(\beta\textbf{x}_{1}+(1-\beta)\textbf{x}_{2})-\textbf{y})\
\ \ \ \ \\\
=\rho(\beta(\mbox{D}\textbf{x}_{1}-\textbf{y})+(1-\beta)(\mbox{D}\textbf{x}_{2}-\textbf{y})).\end{split}$
(4)

i) If $\rho$ is convex, then

$\begin{split}\rho(\beta(\mbox{D}\textbf{x}_{1}-\textbf{y})+(1-\beta)(\mbox{D}\textbf{x}_{2}-\textbf{y}))\leq\beta\rho(\mbox{D}\textbf{x}_{1}-\textbf{y})+\\\
(1-\beta)\rho(\mbox{D}\textbf{x}_{2}-\textbf{y}))=\beta\nu(\tau_{1})+(1-\beta)\nu(\tau_{2}),\end{split}$
(5)

that shows $\nu$ is convex as well as $\psi$.
ii) If $\rho$ is quasi-convex, then

$\begin{split}\rho(\beta(\mbox{D}\textbf{x}_{1}-\textbf{y})+(1-\beta)(\mbox{D}\textbf{x}_{2}-\textbf{y}))\leq\
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \\\
\max\\{\rho(\mbox{D}\textbf{x}_{1}-\textbf{y}),\rho(\mbox{D}\textbf{x}_{2}-\textbf{y})\\}=\max\\{\nu(\tau_{1}),\nu(\tau_{2})\\},\end{split}$
(6)

that shows $\nu$ is quasi-convex as well as $\psi$.

Pareto optimal points are unique for $(\mbox{P}_{\tau})$ with convex and
quasi-convex losses $\rho$ that can be infered from [18, Theorem 1.1, Theorem
1.2], [19]. Also, the feasible set of $(\mbox{P}_{\tau})$ enlarges as $\tau$
increases, thus $\psi(\tau)$ is nonincreasing [20]. In Fig. 1 an abstract
$\psi(\tau)$ is depicted for convex and quasi-convex losses $\rho$ where the
red line represents the $\sigma$ level.

Obtaining the solution of $(\mbox{P}_{\sigma})$ by solving $(\mbox{P}_{\tau})$
proceeds as follows. We start with a ${\tau}$ parameter to solve
$(\mbox{P}_{\tau})$, and using the solution of $(\mbox{P}_{\tau})$, find a new
$\tau$ value. We proceed iteratively until $\psi(\tau_{\sigma})\to 0$.
$\tau_{\sigma}$ occurs at the intersection of the red line and black curve in
Fig 1, where we immediately see that the solution of $(\mbox{P}_{\tau})$ is
also a solution of the $(\mbox{P}_{\sigma})$, a fact proven formally by [11].
Finding $\tau_{\sigma}$ can be formulated as a nonlinear root finding problem.

(a) Convex $\rho$

(b) Quasi-convex $\rho$

Figure 1: Pareto frontiers for convex and quasi-convex losses $\rho$.

###  II-B Regula Falsi Type Methods

Our aim is to

$\mbox{find}\ \ \ \tau\ \ \ \mbox{such that}\ \ \ \psi(\tau)=0.$ (7)

If $\rho$ is nonconvex, neither Newton’s method nor secant variants are
guaranteed to solve (7). In particular, the tangent lines may cross in the
feasible region, and secant lines may not bracket the feasible area. In
contrast, regardless of shape of the $\rho$, bracketing type root finding
methods are guaranteed to solve (7). Here, we develop Regula Falsi type
methods for (7).

We denote the solution of a nonlinear equation of $f$ by $x^{*}$, i.e
$f(x^{*})=0$. With this notation, Regula Falsi type methods starting with the
points $a$ and $b$ proceed as follows.

  1. 1.

Calculate the secant line between $a$ and $b$,

$s_{ab}=\frac{f(b)-f(a)}{b-a},$ (8)

and find the point where (8) intersects the x-axis, which is
$c=b-\frac{f(b)}{s_{ab}}$.

  2. 2.

Calculate $f(c)$. If $f(c)=0$ then $x^{*}=c$, otherwise continue.

  3. 3.

Adjust the new interval: if $f(c)f(b)<0$, $x^{*}$ should be in between $b$ and
$c$. Set

$a=b,\ b=c,\ \ \text{and}\ \ f(a)=f(b),\ f(b)=f(c),$ (9)

if $f(c)f(b)>0$, $x^{*}$ should be in between $a$ and $c$.

$b=c,\ \ \text{and}\ \ f(a)=\mu f(a),\ f(b)=f(c),$ (10)

where $\mu$ is the scaling factor.

  4. 4.

Check the ending condition: if $|b-a|\leq\epsilon$, stop the iteration. Take

$x^{*}=\begin{cases}b,\ \ \mbox{if}\ \ |f(b)|\leq|f(a)\\\ a,\ \ \mbox{if}\ \
|f(b)|>|f(a)\end{cases},$ (11)

if $|b-a|>\epsilon$, continue the iteration, go back to $1)$ with the values
$a,b$ and $f(a),f(b)$ from $3)$.

TABLE I: Regula Falsi-type methods with different $\mu$ values. Method | $\mu$
---|---
Regula Falsi | $1$
Illinois | $0.5$
Pegasus | $\frac{f(b)}{f(b)+f(c)}$
Anderson-Björck |  $1-\frac{f(c)}{f(b)}$, and in case $1\leq\frac{f(c)}{f(b)}$ set $\gamma=0.5$.

Regula Falsi type methods differ from each other in the choice of the scaling
factor $\mu$. Several commonly considered $\mu$ in the literature is
summarized in Table I. Additional options for $\mu$ are studied in [21], [22].

##  III Solving $(\mbox{P}_{\sigma})$

###  III-A $(\mbox{P}_{\tau})$ Solver

In order to solve $(\mbox{P}_{\sigma})$, we repeatedly solve
$(\mbox{P}_{\tau})$. $(\mbox{P}_{\tau})$ can be solved using the simple
projected gradient method

$\textbf{x}^{(k)}=\text{proj}_{\tau\mathbb{B}_{1}}\left(\textbf{x}^{(k-1)}+\gamma\mbox{D}^{T}\nabla\rho(\textbf{y}-\mbox{D}\textbf{x}^{(k-1)})\right).$
(12)

####  III-A1 Projection onto the $\ell_{1}$-ball

Projection of a vector $\textbf{a}=[a_{1},a_{2},...,a_{N}]$ onto the
$\ell_{1}$-ball can be written as following

$\text{proj}\left(\textbf{a},\tau\right)=\left\\{\begin{array}[]{c
l}\textbf{a},&\text{if}\ \ \left\|\textbf{a}\right\|_{1}\leq 1\\\
\mbox{sgn}(a_{i})\mbox{max}\\{|a_{i}|-\kappa,0\\},&\ \ \ \
\text{else}\end{array}\right.$ (13)

where $\kappa$ is the Lagrangian multiplier of
$\text{proj}_{1}\left(\textbf{a},\tau\right)$ [23]. The tricky part of the
projection is to find the $\kappa$ that satisifes Karush-Kuhn-Tucker
optimality condition $\sum_{i=1}^{N}\left(|a_{i}|-\kappa\right)=\tau$ in an
efficient way.

To find $\kappa$, we utilized the simple, sorting based approach introduced in
[24]. Additional variations of this method are described in [25].

To find $\kappa$:

  * •

Sort $|\textbf{a}|$ as: $c_{1}\geq c_{2}\geq...\geq c_{N}$ ,

  * •

Find $K=\underset{1\leq k\leq N}{\mbox{max}}\left\\{k\
|\left(\sum_{j=1}^{k}c_{j}-\tau\right)/k\leq c_{k}\right\\}$,

  * •

Calculate $\kappa=\left(\sum_{k=1}^{K}c_{k}-\tau\right)/K$.

To solve $(\mbox{P}_{\tau})$, we used a projected gradient method with the
spectral line search strategy discussed by [9], with the projection steps
given in III-A1.

###  III-B Solving $(\mbox{P}_{\sigma})$

####  III-B1 Bracketing

In order to choose the root searching interval, we consider a well-known
decomposition method called method of frames (mof) [26]. The mof decomposition
of a signal y can be obtained with the inverse linear mapping such that
$\textbf{x}_{MF}=\mbox{D}^{T}(\mbox{D}\mbox{D}^{T})^{-1}\textbf{y}=\arg\min\left\\{\left\|\textbf{x}\right\|_{2}\
\ \mbox{s.t.}\ \ \textbf{y}=\mbox{D}\textbf{x}\right\\}$. Many common loss
functions $\rho$ are nonnegative and vanish at the origin, including gauges
and nonconvex losses considered in this study. For these losses, under the
assumption that D is full row-rank,
$\rho(\textbf{y}-\mbox{D}\textbf{x}_{MF})=0$ and $\psi(\tau_{MF})=-\sigma$
with $\tau_{MF}=\left\|\textbf{x}_{MF}\right\|_{1}$. For the left endpoint, we
consider $\textbf{x}=0$, and $\tau=0$, with loss equal to $\rho(\textbf{y})$.
Bracketing the root searching interval between the points $\textbf{x}_{MF}$
and $0$ ensures finding a solution for (7) since they provide two initial
points with opposite signs for $\psi$, as long as $\rho(\textbf{y})>\sigma$.

####  III-B2 Solving $(\mbox{P}_{\sigma})$

We combine the proposed Regula Falsi methods and a $(\mbox{P}_{\tau})$ solver
to solve $(\mbox{P}_{\sigma})$ as follows:

  * •

Choose initial $\tau$ values.

Choose two initial values with opposite signs to ensure convergence of Regula
Falsi type Methods. The default choice is given by $\tau=0$ and
$\tau=\tau_{MF}$.

  * •

Apply the steps of Regula Falsi type methods.

Every iteration of the Regula Falsi-type methods requires solving
$(\mbox{P}_{\tau})$, except at $\tau=0$ and $\tau=\tau_{MF}$.

  * •

Terminate once the stopping criteria are met.

##  IV Simulations

In order to examine the performances of Regula Falsi type methods given in
Table I, we created a test environment and benchmark by using Sparco framework
[27]. Real-valued problems are chosen from Sparco for the simulations among
this collection of test problems that includes many examples from the
literature. Details about the problems and related publications can be found
in [27].

Figure 2: From left to right, $\nu(\tau)$ for the gauss-en problem with
$\rho_{l}$, $\rho_{h}$ and $\rho_{s}$.

Performances of the Regula Falsi type methods are investigated for three
different loss functions $\rho$ which are Least squares
$\rho_{l}(\textbf{x})=\left\|\textbf{x}\right\|_{2}$, Huber

$\displaystyle\rho_{h}(\textbf{x})_{i}=\sum_{i=1}^{N}\begin{cases}\ \ \
\frac{x_{i}^{2}}{2\delta},\ \ \ \ \ \mbox{if}\ \ |x_{i}|\leq\delta\\\
|x_{i}|-\frac{\delta}{2},\ \ \ \mbox{otherwise}\end{cases},$ (14)

and Student’s t
$\rho_{s}(\textbf{x})=\sum_{i=1}^{N}\nu\log\left(1+x_{i}^{2}/\nu\right)$ where
$\delta$ and $\nu$ are the tunning parameters for $\rho_{h}$ and $\rho_{s}$,
respectively; we take $\delta=5\times 10^{-3}$ and $\nu=10^{-2}$ in our
simulations. $N,M$ and $\rho(\textbf{y})$ values for the chosen problems are
given in Table II.

We solve $(\mbox{P}_{\sigma})$ for a range of $\sigma$ values, chosen relative
to $\rho(\mathbf{y})$, in particular $5\times 10^{-1}\rho(\mathbf{y})$,
$5\times 10^{-2}\rho(\mathbf{y})$ and $5\times 10^{-3}\rho(\mathbf{y})$. We
compute residuals
$\rho(\textbf{r}_{\sigma})=\rho(\textbf{y}-\mbox{D}\textbf{x}_{\sigma})$,
norms $\left\|\textbf{x}_{\sigma}\right\|_{1}$, the number of nonzero (nnz)
for each solution $\textbf{x}_{\sigma}$, and iter the total solves of
$(\mbox{P}_{\tau})$ to reach these solutions; results are displayed in Table
III.

Newton’s method requires fewer $(\mbox{P}_{\tau})$ solves (see Table III).
However, solving (7) is more expensive for Newton’s method than for Regula
Falsi-type methods since the derivative calculation of the nonlinear equation
is required along with the function evaluation, while Regula Falsi-type
methods need only the function evaluation. From a robustness standpoint,
Newton, secant, and their variants are not guaranteed to converge for
nonconvex loss functions, in contrast to Regula Falsi-type methods.

The Pareto frontier $\nu(\tau)$ is shown for the gauss-en problem with losses
$\rho_{l}$, $\rho_{h}$ and $\rho_{s}$ in Figure 2. We expect similar patterns
in many problems. As expected, the Pareto frontier is nonconvex, and Newton
iterations will not stay in the feasible area for $\rho_{s}$ in this example,
since the tangent lines can leave the feasible region.

Figure 3 shows a typical compressed sensing example. A $20$-sparse vector is
recovered using a normally distributed Parseval frame
$\mbox{D}\in\mathbb{R}^{175\times 600}$. A measurement is generated according
to $\textbf{y}=\mbox{D}\textbf{x}+\textbf{w}+\zeta$, where the noise w is zero
mean normal error with the variance of $0.005$ and $\zeta$ has five randomly
placed outliers with a zero mean normal distribution variance of $4$.
$(\mbox{P}_{\sigma})$ solved with the $\sigma=\rho(\zeta)$ for a fair
comparison of $\rho_{l}$, $\rho_{h}$ and $\rho_{s}$. Huber loss is less
sensitive to outliers in measurement data than least-squares, but Student’s t
outperforms Huber loss since it grows sublinearly as outliers increase, a
property also noted by [11].

Problems | id | $M$ | $N$ | $\rho_{l}(\textbf{y})$ | $\rho_{h}(\textbf{y})$ | $\rho_{s}(\textbf{y})$
---|---|---|---|---|---|---
cos-spike | $3$ | $1024$ | $2048$ | $102.2423$ | $2378.8$ | $25.09$
gauss-en | $11$ | $256$ | $1024$ | $99.9055$ | $1272.5$ | $8.957$
jitter | $902$ | $200$ | $1000$ | $0.4476$ | $4.6881$ | $0.0901$
TABLE II: $N,M$, $\rho(\textbf{y})$ values for the problem setups.

##  V Conclusion

In this note, we developed a new approach using bracketing Regula Falsi-type
methods, that enable level-set methods to be applied to sparse optimization
problems with nonconvex likelihood constraints, significantly expanding their
usability. These methods achieve comparable performance to Newton’s method for
root finding on convex problems, and are guaranteed to converge in the
nonconvex case, where Newton and secant variants may fail.

Figure 3: Left, top to bottom: true signal, reconstructions with least squares, Huber and Student’s t losses. Right, top to bottom: true errors, least squares, Huber and Student’s t residuals.  TABLE III: Simulation Results for Solving $(\mbox{P}_{\sigma})$. |  |  | least squares | Huber ($\delta=5\times 10^{-3}$) | Student’s t ($\nu=10^{-2}$)
---|---|---|---|---|---
Problems | $\sigma/\rho(\mathbf{y})$ | Methods | $\rho_{l}(\textbf{r}_{\sigma})$ | $\left\|\textbf{x}_{\sigma}\right\|_{1}$ | $nnz$ | $iter$ | $\rho_{h}(\textbf{r}_{\sigma})$ | $\left\|\textbf{x}_{\sigma}\right\|_{1}$ | $nnz$ | $iter$ | $\rho_{s}(\textbf{r}_{\sigma})$ | $\left\|\textbf{x}_{\sigma}\right\|_{1}$ | $nnz$ | $iter$
cos-spike | 0.5 | Regula Falsi | $51.12$ | $66.24$ | $2$ | $10$ | $1189.4$ | $68.328$ | $2$ | $8$ | $12.545$ | $94.289$ | $10$ | $14$
Illinois | $51.12$ | $66.24$ | $2$ | $7$ | $1189.4$ | $68.328$ | $2$ | $7$ | $12.545$ | $94.289$ | $10$ | $7$
Pegasus | $51.12$ | $66.24$ | $2$ | $7$ | $1189.4$ | $68.328$ | $3$ | $6$ | $12.545$ | $94.289$ | $10$ | $6$
And.-Björck | $51.12$ | $66.24$ | $2$ | $9$ | $1189.4$ | $68.328$ | $3$ | $9$ | $12.545$ | $94.289$ | $10$ | $10$
Newton | $51.12$ | $66.24$ | $2$ | $3$ | $1189.4$ | $68.328$ | $2$ | $3$ | $-$ | $-$ | $-$ | $-$
0.05 | Regula Falsi | $5.112$ | $188.4$ | $75$ | $85$ | $118.94$ | $134.71$ | $2$ | $68$ | $1.2105$ | $171.09$ | $79$ | $72$
Illinois | $5.112$ | $188.4$ | $75$ | $13$ | $118.94$ | $134.71$ | $2$ | $15$ | $1.2214$ | $172.65$ | $78$ | $16$
Pegasus | $5.112$ | $188.4$ | $75$ | $12$ | $118.94$ | $134.71$ | $2$ | $14$ | $1.259$ | $170.95$ | $76$ | $34$
And.-Björck | $5.112$ | $188.4$ | $75$ | $27$ | $118.94$ | $134.71$ | $2$ | $32$ | $1.251$ | $170.85$ | $75$ | $50$
Newton | $5.112$ | $188.4$ | $75$ | $5$ | $118.94$ | $134.7$ | $2$ | $4$ | $-$ | $-$ | $-$ | $-$
0.005 | Regula Falsi | $0.511$ | $235.6$ | $123$ | $396$ | $11.893$ | $229.02$ | $127$ | $451$ | $0.1272$ | $231.15$ | $124$ | $383$
Illinois | $0.511$ | $235.6$ | $123$ | $19$ | $11.894$ | $229.02$ | $125$ | $15$ | $0.1183$ | $231.15$ | $124$ | $30$
Pegasus | $0.511$ | $235.6$ | $123$ | $19$ | $11.894$ | $229.02$ | $130$ | $14$ | $0.118$ | $231.16$ | $121$ | $27$
And.-Björck | $0.511$ | $235.6$ | $123$ | $34$ | $11.894$ | $229.02$ | $130$ | $21$ | $0.1273$ | $231.13$ | $122$ | $19$
Newton | $0.511$ | $235.6$ | $123$ | $5$ | $11.894$ | $229.02$ | $125$ | $3$ | $-$ | $-$ | $-$ | $-$
gauss-en | 0.5 | Regula Falsi | $49.95$ | $11.9$ | $16$ | $9$ | $636.27$ | $11.97$ | $19$ | $9$ | $4.479$ | $16.6$ | $139$ | $11$
Illinois | $49.95$ | $11.9$ | $16$ | $7$ | $636.27$ | $11.97$ | $19$ | $6$ | $4.479$ | $16.6$ | $139$ | $8$
Pegasus | $49.95$ | $11.9$ | $16$ | $5$ | $636.27$ | $11.97$ | $19$ | $5$ | $4.479$ | $16.6$ | $139$ | $6$
And.-Björck | $49.95$ | $11.9$ | $16$ | $7$ | $636.27$ | $11.97$ | $19$ | $7$ | $4.479$ | $16.6$ | $139$ | $8$
Newton | $49.95$ | $11.9$ | $16$ | $4$ | $636.27$ | $11.97$ | $19$ | $4$ | $-$ | $-$ | $-$ | $-$
0.05 | Regula Falsi | $4.995$ | $26.45$ | $35$ | $26$ | $63.63$ | $26.406$ | $50$ | $27$ | $0.448$ | $27.82$ | $39$ | $24$
Illinois | $4.995$ | $26.45$ | $35$ | $11$ | $63.63$ | $26.406$ | $50$ | $14$ | $0.448$ | $27.82$ | $39$ | $15$
Pegasus | $4.995$ | $26.45$ | $35$ | $11$ | $63.63$ | $26.406$ | $50$ | $11$ | $0.448$ | $27.82$ | $39$ | $15$
And.-Björck | $4.995$ | $26.45$ | $35$ | $15$ | $63.63$ | $26.406$ | $50$ | $27$ | $0.448$ | $27.82$ | $39$ | $28$
Newton | $4.995$ | $26.45$ | $35$ | $4$ | $63.63$ | $26.406$ | $50$ | $4$ | $-$ | $-$ | $-$ | $-$
0.005 | Regula Falsi | $0.499$ | $28.06$ | $35$ | $208$ | $6.3624$ | $28.036$ | $46$ | $209$ | $0.045$ | $28.12$ | $1024$ | $207$
Illinois | $0.499$ | $28.06$ | $35$ | $19$ | $6.3627$ | $28.036$ | $46$ | $19$ | $0.045$ | $28.12$ | $1024$ | $27$
Pegasus | $0.499$ | $28.06$ | $35$ | $19$ | $6.3627$ | $28.036$ | $46$ | $20$ | $0.045$ | $28.12$ | $1024$ | $24$
And.-Björck | $0.499$ | $28.06$ | $35$ | $58$ | $6.3627$ | $28.036$ | $46$ | $62$ | $0.045$ | $28.12$ | $1024$ | $65$
Newton | $0.499$ | $28.06$ | $35$ | $3$ | $6.3628$ | $28.036$ | $46$ | $4$ | $-$ | $-$ | $-$ | $-$
jitter | 0.5 | Regula Falsi | $0.224$ | $0.766$ | $3$ | $7$ | $2.344$ | $0.6959$ | $3$ | $7$ | $0.045$ | $0.4548$ | $2$ | $9$
Illinois | $0.224$ | $0.766$ | $3$ | $6$ | $2.344$ | $0.6958$ | $3$ | $7$ | $0.045$ | $0.4548$ | $2$ | $7$
Pegasus | $0.224$ | $0.766$ | $3$ | $6$ | $2.344$ | $0.6958$ | $3$ | $6$ | $0.045$ | $0.4548$ | $2$ | $6$
And.-Björck | $0.224$ | $0.766$ | $3$ | $8$ | $2.344$ | $0.6958$ | $3$ | $8$ | $0.045$ | $0.4548$ | $2$ | $9$
Newton | $0.224$ | $0.766$ | $3$ | $3$ | $2.344$ | $0.6958$ | $3$ | $3$ | $-$ | $-$ | $-$ | $-$
0.05 | Regula Falsi | $0.022$ | $1.537$ | $3$ | $39$ | $0.2343$ | $1.4338$ | $3$ | $43$ | $0.005$ | $1.2587$ | $3$ | $54$
Illinois | $0.022$ | $1.537$ | $3$ | $12$ | $0.2344$ | $1.4338$ | $3$ | $15$ | $0.005$ | $1.2585$ | $3$ | $14$
Pegasus | $0.022$ | $1.537$ | $3$ | $12$ | $0.2344$ | $1.4338$ | $3$ | $14$ | $0.005$ | $1.2585$ | $3$ | $12$
And.-Björck | $0.022$ | $1.537$ | $3$ | $30$ | $0.2344$ | $1.4338$ | $3$ | $39$ | $0.005$ | $1.2585$ | $3$ | $41$
Newton | $0.022$ | $1.537$ | $3$ | $2$ | $0.2344$ | $1.4338$ | $3$ | $4$ | $-$ | $-$ | $-$ | $-$
0.005 | Regula Falsi | $0.002$ | $1.614$ | $3$ | $375$ | $0.0233$ | $1.5646$ | $3$ | $391$ | $0.0005$ | $1.5086$ | $3$ | $413$
Illinois | $0.002$ | $1.614$ | $3$ | $19$ | $0.0234$ | $1.5644$ | $3$ | $16$ | $0.0005$ | $1.508$ | $3$ | $16$
Pegasus | $0.002$ | $1.614$ | $3$ | $20$ | $0.0234$ | $1.5644$ | $3$ | $14$ | $0.0005$ | $1.508$ | $3$ | $16$
And.-Björck | $0.002$ | $1.614$ | $3$ | $35$ | $0.0234$ | $1.5644$ | $3$ | $27$ | $0.0005$ | $1.508$ | $3$ | $107$
Newton | $0.002$ | $1.614$ | $3$ | $2$ | $0.0235$ | $1.5643$ | $3$ | $5$ | $-$ | $-$ | $-$ | $-$

## References

  * [1] E. J. Candes, J. Romberg, and T. Tao, “Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information,” _IEEE Transactions on Information Theory_ , vol. 52, no. 2, pp. 489–509, 2006\.
  * [2] D. L. Donoho, “Compressed sensing,” _IEEE Trans. Inf. Theor._ , vol. 52, no. 4, p. 1289–1306, Apr. 2006. [Online]. Available: https://doi.org/10.1109/TIT.2006.871582
  * [3] D. L. Donoho and X. Huo, “Uncertainty principles and ideal atomic decomposition,” _IEEE Transactions on Information Theory_ , vol. 47, no. 7, pp. 2845–2862, 2001.
  * [4] J. . Fuchs, “On sparse representations in arbitrary redundant bases,” _IEEE Transactions on Information Theory_ , vol. 50, no. 6, pp. 1341–1344, 2004.
  * [5] E. J. Candes and T. Tao, “Decoding by linear programming,” _IEEE Transactions on Information Theory_ , vol. 51, no. 12, pp. 4203–4215, 2005.
  * [6] M. Lustig, J. H. Lee, D. L. Donoho, and J. M. Pauly, “Faster imaging with randomly perturbed, undersampled spirals and —l—1 reconstruction,” in _in Proceedings of the 13th Annual Meeting of ISMRM_ , 2005, p. 685.
  * [7] A. Y. Aravkin, J. V. Burke, D. Drusvyatskiy, M. P. Friedlander, and S. Roy, “Level-set methods for convex optimization,” _Mathematical Programming_ , vol. 174, no. 1, pp. 359–390, 2019.
  * [8] S. Foucart and H. Rauhut, _A Mathematical Introduction to Compressive Sensing_ , ser. Applied and Numerical Harmonic Analysis. Springer New York, 2013.
  * [9] E. van den Berg and M. Friedlander, “Probing the pareto frontier for basis pursuit solutions,” _SIAM Journal on Scientific Computing_ , vol. 31, no. 2, pp. 890–912, 2009. [Online]. Available: https://doi.org/10.1137/080714488
  * [10] ——, “Sparse optimization with least-squares constraints,” _SIAM Journal on Optimization_ , vol. 21, no. 4, pp. 1201–1229, 2011. [Online]. Available: https://doi.org/10.1137/100785028
  * [11] A. Y. Aravkin, J. V. Burke, and M. P. Friedlander, “Variational properties of value functions,” _SIAM Journal on optimization_ , vol. 23, no. 3, pp. 1689–1717, 2013.
  * [12] G. Dahlquist and Å. Björck, _Numerical Methods_ , ser. Dover Books on Mathematics. Dover Publications, 2003\. [Online]. Available: https://books.google.de/books?id=armfeHpJIwAC
  * [13] N. Städler, P. Buehlmann, and S. Van De Geer, “l1-penalization for mixture regression models,” _Test_ , vol. 19, no. 2, pp. 209–256, 2010.
  * [14] P. Buehlmann and S. Geer, “Non-convex loss functions and l1-regularization,” _Statistics for High-Dimensional Data_ , pp. 293–338, 2011.
  * [15] “Robust and trend-following kalman smoothers using student’s t*,” _IFAC Proceedings Volumes_ , vol. 45, no. 16, pp. 1215 – 1220, 2012, 16th IFAC Symposium on System Identification.
  * [16] A. Y. Aravkin, J. V. Burke, and G. Pillonetto, “Sparse/robust estimation and kalman smoothing with nonsmooth log-concave densities: Modeling, computation, and theory,” _The Journal of Machine Learning Research_ , vol. 14, no. 1, pp. 2689–2728, 2013.
  * [17] A. Aravkin, M. P. Friedlander, F. J. Herrmann, and T. Van Leeuwen, “Robust inversion, dimensionality reduction, and randomized sampling,” _Mathematical Programming_ , vol. 134, no. 1, pp. 101–125, 2012.
  * [18] P. M. Pardalos, A. Žilinskas, and J. Žilinskas, _Non-convex multi-objective optimization_. Springer, 2017.
  * [19] K. Miettinen, “Some methods for nonlinear multi-objective optimization,” in _International conference on evolutionary multi-criterion optimization_. Springer, 2001, pp. 1–20.
  * [20] E. Van den Berg, “Convex optimization for generalized sparse recovery,” Ph.D. dissertation, University of British Columbia, 2009.
  * [21] S. Galdino, “A family of regula falsi root-finding methods.”
  * [22] J. A. Ford, “Improved algorithms of illinois-type for the numerical solution of nonlinear equations.”
  * [23] J. Duchi, S. Shalev-Shwartz, Y. Singer, and T. Chandra, “Efficient projections onto the l1-ball for learning in high dimensions,” in _ICML ’08: Proceedings of the 25th international conference on Machine learning_ , New York, NY, USA, 2008, pp. 272–279. [Online]. Available: http://doi.acm.org/10.1145/1390156.1390191
  * [24] M. Held, P. Wolfe, and H. P. Crowder, “Validation of subgradient optimization,” _Math. Program._ , vol. 6, no. 1, pp. 62–88, Dec. 1974. [Online]. Available: https://doi.org/10.1007/BF01580223
  * [25] L. Condat, “Fast Projection onto the Simplex and the l1 Ball,” _Mathematical Programming, Series A_ , vol. 158, no. 1, pp. 575–585, Jul. 2016. [Online]. Available: https://hal.archives-ouvertes.fr/hal-01056171
  * [26] I. Daubechies, “Time-frequency localization operators: a geometric phase space approach,” _IEEE Transactions on Information Theory_ , vol. 34, no. 4, pp. 605–612, July 1988.
  * [27] E. van den Berg, M. P. Friedlander, G. Hennenfent, F. J. Herrmann, R. Saab, and O. Yilmaz, “Algorithm 890: Sparco: A testing framework for sparse reconstruction,” _ACM Trans. Math. Softw._ , vol. 35, no. 4, Feb. 2009. [Online]. Available: https://doi.org/10.1145/1462173.1462178


2.5cm2.5cm2.5cm2.5cm

# Contractions in perfect graphs

Alexandre Dupont-Bouillard  LIPN, CNRS UMR 7030, Université Sorbonne Paris
Nord, France111 dupont-bouillard, fouilhoux, grappe<EMAIL_ADDRESS>Pierre
Fouilhoux  LIPN, CNRS UMR 7030, Université Sorbonne Paris Nord, France111
dupont-bouillard, fouilhoux, grappe<EMAIL_ADDRESS>Roland Grappe  LIPN, CNRS
UMR 7030, Université Sorbonne Paris Nord, France111 dupont-bouillard,
fouilhoux, grappe<EMAIL_ADDRESS>Mathieu Lacroix  LIPN, CNRS UMR 7030,
Université Sorbonne Paris Nord, France111 dupont-bouillard, fouilhoux, grappe,
<EMAIL_ADDRESS>
###### Abstract

In this paper, we characterize the class of contraction perfect graphs which
are the graphs that remain perfect after the contraction of any edge set. We
prove that a graph is contraction perfect if and only if it is perfect and the
contraction of any single edge preserves its perfection. This yields a
characterization of contraction perfect graphs in terms of forbidden induced
subgraphs, and a polynomial algorithm to recognize them. We also define the
utter graph $u(G)$ which is the graph whose stable sets are in bijection with
the co-2-plexes of $G$, and prove that $u(G)$ is perfect if and only if $G$ is
contraction perfect.

Keywords— perfect graphs, contraction perfect, co-2-plexes, forbidden induced
subgraphs

## Introduction

A graph $G$ is called _perfect_ if $\omega(H)=\chi(H)$ for every induced
subgraph $H$ of $G$, where $\omega(H)$ is the clique number of $H$ and
$\chi(H)$ its chromatic number. Contracting any pair of vertices, that is,
identifying both vertices, does not always preserve perfection. For instance,
perfection is destroyed if there is an induced path of odd length between
those vertices.

Two nonadjacent vertices in a graph form an even pair if every induced path
between them has an even number of edges. Fonlupt and Uhry [10] proved that
contracting an even pair in a perfect graph preserves perfection, and Meyniel
proved what is called the Even Pair Lemma [20]: no minimally imperfect graph
contains an even pair. Concerning the associated decision problems, Bienstock
[2] proved that the following are CoNP-complete in the general case: deciding
whether a given pair of vertices of a graph form an even pair, and deciding
whether a given graph contains an even pair. Nevertheless, in perfect graphs,
both problems become solvable in polynomial time [6]. A graph is perfectly
contractile if for every induced subgraph there exists a sequence of even pair
contraction yielding a clique. In [17], a subclass of perfectly contractile
graph is given which leads to a polynomial combinatorial algorithm for the
coloring problem for that class.

In this paper, we approach contractions in perfect graphs with a slightly
different point of view: we are interested in the graphs for which the
contraction of any set of edges preserves perfection, and we call them
contraction perfect. Since perfection is preserved under taking induced
subgraphs, contraction perfect graphs can be seen as the graphs in which every
induced minor is perfect, where an induced minor is a graph obtained by
deleting vertices and contracting edges. A class of graph is induced minor
closed if, for any element of that class, each of its induced minors also
belongs to that class.

A co-$2$-plex in a graph is a set of vertices inducing a subgraph of maximum
degree at most one. This notion, or rather its complement version, was
introduced in 1978 by Seidman and Foster [23] to seek communities in a graph
with more freedom than when looking for cliques—a clique is a set of pairwise
adjacent vertices. Indeed, a $k$-plex is a set $W$ of vertices inducing a
graph where every vertex has degree at least $|W|-k$, and cliques are special
cases of $2$-plexes. The underlying optimization problem is to find a maximum
weight $k$-plex in a given weighted graph. For any fixed $k$ and hence for
$k=2$, this problem is NP-hard [1]. Hence, by complementing the graph, so is
the problem of finding a maximum co-2-plex. It turns out that this latter
optimization problem, which can be seen as a relaxation of the maximum stable
set problem—a stable set is a set of vertices inducing a subgraph of maximum
degree at most 0—, behaves well in contraction perfect graphs.

This topic has been especially lively the past few years, mostly in the design
of practical algorithms that find a maximum weight $k$-plex. For this problem,
there are exact algorithms [29], algorithms based on local search [22, 5, 12,
15, 4], heuristics [27], branch and bound algorithms, some of which
incorporate machine learning ingredients [1, 21, 28, 25, ijcai2021p233, 3,
13], and quadratic models [24]. From a more combinatorial optimization point
of view, a combinatorial algorithm is devised in [19], and polyhedral studies
are conducted in [1, 18]. The problem of enumerating the $k$-plexes also
received some attention [9, 26, 14]. In [19], a parameterized algorithm is
proposed to both find the smallest set of vertices whose removal gives a graph
with vertices of maximal degree $k$ and the maximum co-$(k\\!+\\!1)$-plex
problem. The two latter problems parameterized by the size of the solution are
not FPT reducible hence, no other results can be deduced for the maximum
co-$k\\!+\\!1$-plex problem.

As we shall see, our approach of contractions in perfect graphs yields a
family of graphs in which the co-2-plex problem is solvable in polynomial
time.

#### Contributions.

We start with a surprising result: contraction perfect graphs are
characterized, among perfect graphs, as those for which the contraction of any
single edge preserves perfection. Building upon this result, we characterize
contraction perfect graphs in terms of forbidden induced subgraphs. As another
byproduct, we get that the associated recognition problem, that is, the
problem of deciding whether a given graph is contraction perfect, is solvable
in polynomial time.

It turns out that contraction perfect graphs are graphs in which the maximum
weight co-2-plex problem is solvable in polynomial time. To prove this, we
introduce the utter graph of a graph: it is a graph in which the stable sets
correspond to the co-2-plexes of the original graph. We first give sufficient
conditions for an induced minor closed graph class to both contain a graph and
its utter graph. These conditions allow us to derive another characterization
of contraction perfect graphs: a graph is contraction perfect if and only if
its utter graph is perfect. Since finding a maximum weight stable set can be
done in polynomial time in perfect graphs [8], this yields the announced
complexity result for the maximum weight co-$2$-plex. We also strengthen the
connection between a graph and its utter graph for split, trivially perfect,
and chordal graphs.

#### Outline.

In Section 1, we first provide a forbidden induced subgraph characterization
for the graphs remaining perfect after the contraction of any single edge. We
show that these graphs are exactly contraction perfect graphs in Section 1.2.
This yields the forbidden induced subgraph characterization of contraction
perfect graphs in Section 1.3. Consequently, deciding if a given graph is
contraction perfect can be done in polynomial time.

In Section 2, we introduce the utter graph of a graph. This yields another
characterization of contraction perfect graphs in Section 2.1 as the graphs
whose utter graphs are perfect. As a byproduct, we get that a maximum weight
co-2-plex can be found in polynomial time in a contraction perfect graphs. In
Section 2.2, we strengthen the link with the utter graph for a few subclasses
of contraction perfect graphs.

#### Definitions.

All the graphs in this paper are simple and connected. Given a graph
$G=(V,E)$, we denote its complement by $\overline{G}=(V,\overline{E})$, where
$\overline{E}=\\{uv:uv\notin E\\}$. We denote by $V(G)$ (resp. $E(G)$) the
vertex (resp. edge) set of $G$. Two vertices $u$ and $v$ are _adjacent_ if
$uv\in E(G)$. A vertex is universal if it is adjacent to all the other
vertices. Given a subset of vertices $W\subseteq V$, let $E(W)$ denote the set
of edges of $G$ having both endpoints in $W$ and $\delta(W)$ the set of all
edges having exactly one endpoint in $W$. When $W$ is a singleton $\\{w\\}$,
we will simply write $\delta(w)$. We say that the edges in $\delta(w)$ are
incident to $w$, and two edges sharing an extremity are also said incident. A
matching is a set of pairwise nonincident edges. For $F\subseteq E$, let
$V(F)$ denote the set of vertices incident to any edge of $F$. Given
$W\subseteq V$, the graph $G[W]=(W,E(W))$ is the subgraph induced by $W$ in
$G$. When $H$ is an induced subgraph of $G$, we say that $G$ contains $H$.
Given a vertex $u\in V$, we denote by $N_{u}=\\{w\in V:uw\in E\\}$ its
neighborhood in $G$, and by $\overline{N}_{u}=N_{u}\cup\\{u\\}$ its closed
neighborhood. Two vertices $u$ and $v$ are true (resp. false) twins if
$\overline{N}_{u}=\overline{N}_{v}$ (resp. $N_{u}=N_{v})$.

A path (resp. hole) is a graph induced by a sequence of vertices
$(v_{1},\dots,v_{p})$ whose edge set is $\\{v_{i}v_{i+1}:\ i=1,\dots,p-1\\}$
(resp. $\\{v_{i}v_{i+1}:\ i=1,\dots,p-1\\}\cup\\{v_{1}v_{p}\\}$ with $p\geq
4$). Note that this definition usually corresponds to induced paths. A subset
of vertices induces a path (resp. hole) if its elements can be ordered into a
sequence inducing a path (resp. hole). An _antipath_ (resp. antihole) of $G$
is a path (resp. hole) of $\overline{G}$. The size of a graph $H$ is $|V(H)|$,
and its parity is the parity of $|V(H)|$.

The contraction of an edge $uv$ in $G$ consists in deleting $u$ and $v$, and
adding a new vertex $w$ and the edges $wz$ for all $z\in N_{u}\cup N_{v}$.
This new graph is denoted $G/uv$. For $F\subseteq E$, we denote by $G/F$ the
graph obtained from $G$ by contracting all the edges in $F$. The _image_ of a
vertex $v$ of $G$ in $G/F$ is the vertex of $G/F$ to which $v$ is contracted,
and the _image_ of a set of edges $L$ is the set of the images of the vertices
of $V(L)$ in $G/F$. An edge $uv$ and a vertex $w$ are adjacent by contraction
if $w$ is adjacent to $x_{uv}$ in $G/uv$, where $x_{uv}$ is the image of $uv$
in $G/uv$. In other words, at least one of $uw$ and $vw$ is in $E$. Two edges
$uv$ and $xy$ are adjacent by contraction if contracting both edges results in
two adjacent vertices, that is,
$\delta(\\{u,v\\})\cap\delta(\\{x,y\\})\neq\emptyset$.

Given a total order on a finite set of elements, an _interval_ is a subset of
consecutive elements following that order. _The interval graph_
$G_{\mathcal{I}}$ of a given finite set of intervals $\mathcal{I}$ is the
graph having one vertex per interval in $\mathcal{I}$ and an edge between two
vertices if their corresponding intervals have a nonempty intersection.

##  1 Contraction perfect graphs

This section investigates how contracting edges in a perfect graph impacts its
perfection. It relies on the strong perfect graph theorem [7], which states
that perfect graphs are the graphs that contain neither odd holes nor odd
antiholes. We start by characterizing when the contraction of an edge destroys
the perfection of a graph. In the second and third subsections, we provide two
characterizations of contraction perfect graphs: the first one compares
contractions of single edges with contractions of sets of edges, and the
second one is in terms of forbidden induced subgraphs.

We start by proving a parity result about interval graphs that will be used in
Section 1.1 but might be of independent interest. A set of intervals is an
_odd intersection interval set_ if the non-empty intersection of any subset of
intervals is an interval of odd cardinality.

######  Lemma 1.1.

Given an odd intersection interval set $\mathcal{I}$, the union of the
intervals associated with every connected component of $G_{\mathcal{I}}$ has
odd cardinality.

Proof. It is enough to prove the result when $G_{\mathcal{I}}$ is connected.
We proceed by induction on $|\mathcal{I}|$, the case $|\mathcal{I}|=1$ being
immediate. Let $I$ and $I^{\prime}$ be two intersecting intervals of
$\mathcal{I}$. Hence, $I\cup I^{\prime}$ is an interval. Let
$\mathcal{I^{\prime}}$ be obtained from $\mathcal{I}$ by replacing $I$ and
$I^{\prime}$ by $I\cup I^{\prime}$. Since $\mathcal{I}$ is an odd intersection
interval set, $|(I\cup I^{\prime})\cap K|=|I\cap K|+|I^{\prime}\cap K|-|I\cap
I^{\prime}\cap K|$ is odd or zero for each intersection $K$ of any subset of
intervals of $\mathcal{I}$. Hence, $\mathcal{I}^{\prime}$ is also an odd
intersection interval set. Moreover, $G_{\mathcal{I^{\prime}}}$ is connected
as it is obtained from $G_{\mathcal{I}}$ by contracting the edge whose
extremities are the vertices associated with $I$ and $I^{\prime}$. Since
$|\mathcal{I}^{\prime}|<|\mathcal{I}|$, the induction hypothesis implies that
the union of intervals of $\mathcal{I}^{\prime}$ has odd cardinality. By
definition, the latter set is equal to the union of the intervals of
$\mathcal{I}$, which ends the proof. ∎

###  1.1 When does the contraction of an edge destroy perfection?

By the strong perfect graph theorem, if the contraction of an edge $e$ in a
perfect graph $G$ destroys its perfection, this implies that $G/e$ contains an
odd hole or an odd antihole. Moreover, since $G$ is perfect, the image of $e$
must be a vertex of such a forbidden induced subgraph. Lemmas 1.2 and 1.4
characterize when contracting an edge yields an odd hole or an odd antihole,
respectively. Both results will be used in the proof of Theorem 1.5 which
characterizes when the contraction of an edge destroys the perfection of a
graph.

######  Lemma 1.2.

If $G/F$ contains a hole $H$ for some edge set $F$, then $G$ contains a hole
of size at least $|V(H)|$.

Proof. We proceed by induction on $|F|$. The result holds if $|F|=0$.
Otherwise, some vertex $v$ of $H$ is obtained by contracting the edges of a
connected subgraph $(V^{\prime},F^{\prime})$ of $G$ with $\emptyset\neq
F^{\prime}\subseteq F$. Let $a$ and $b$ be the neighbors of $V^{\prime}$ in
$H$, and let $P$ be an $ab$-path in $G[V^{\prime}\cup\\{a,b\\}]$. Then,
$V(H)\setminus\\{v\\}\cup V(P)$ induces a hole of $G/(F\setminus F^{\prime})$
of size at least $|V(H)|$, and induction concludes. ∎

As we shall see in Lemma 1.4, when the contraction of an edge destroys the
perfection of $G$ by creating an odd antihole, this implies that $G$ contains
the following specific structure.

######  Definition 1.3.

An edge $e$ and an even antipath $P$ induced by $(w_{1},\dots,w_{p})$ with
$p\geq 6$ form an _expanded antihole_ if one extremity of $e$ is adjacent to
all vertices of $P$ but $w_{1},w_{p-1},w_{p}$, and the other extremity is
adjacent to all vertices of $P$ but $w_{1},w_{2},w_{p}$.

Figure 1 represents an expanded antihole where $(w_{1},\dots,w_{p})$ induces
an even antipath. An edge $e$ is _involved_ in an expanded antihole if there
exists an even antipath forming with $e$ an expanded antihole. Note that, by
definition of an expanded antihole, the extremities of $e$ are not vertices of
$P$, and contracting $uv$ yields an odd antihole. Moreover, if $e=uv$, either
$(u,w_{2},\dots,w_{p-1},v)$ or $(v,w_{2},\dots,w_{p-1},u)$ induces an even
antipath that forms an expanded antihole with edge $w_{1}w_{p}$.

$u$$v$$w_{p}$$w_{p-1}$$w_{2}$$w_{1}$$w_{3},\dots,w_{p-2}$ Figure 1: An
expanded antihole.

Note that if one relaxes the adjacency requirement in the definition an
expanded antihole to: ”each vertex $w_{2},\dots,w_{p-1}$ is adjacent to one
extremity of $e$”, contracting $e$ still yields an odd antihole of $G/e$.
However, in this case, $G$ is not necessarily perfect. The following lemma
asserts that the only case where $G$ is perfect and $G/e$ contains an odd
antihole of size at least 7 is when $G$ contains an expanded antihole.

######  Lemma 1.4.

Let $G$ be a perfect graph, $H$ a subgraph of $G$, and $uv$ an edge of $E(H)$.
$H/uv$ is an odd antihole of $G/uv$ of size at least 7 if and only if $H$ is
an expanded antihole formed by $uv$ and the antipath induced by
$V(H)\setminus\\{u,v\\}$.

Proof. $(\Leftarrow)$ By definition, if $H$ is an expanded antihole involving
$uv$, then $H/uv$ is an odd antihole of $G/uv$.

$(\Rightarrow)$ Let us denote by $w_{uv}$ the vertex obtained by contracting
$uv$. Since $H/uv$ is an antihole, $V(H)\setminus\\{u,v\\}$ can be ordered
into the sequence $(w_{1},\dots,w_{p})$ with $p\geq 6$ inducing an even
antipath in $G$. The set of vertices of a maximal antipath of
$H[N_{u}\setminus v]$ (resp. $H[N_{v}\setminus u]$) forms an interval of
$(w_{2},\dots,w_{p-1})$. Let $\mathcal{P}^{u}$ (resp. $\mathcal{P}^{v}$) be
the set of these intervals, and
$\mathcal{I}=\mathcal{P}^{u}\cup\mathcal{P}^{v}$. Since $G$ is perfect, $H$
contains no antihole and then, the interval $(w_{2},\dots,w_{p-1})$ does not
belong to $\mathcal{I}$.

Suppose that interval graph $G_{\mathcal{I}}$ associated to $\mathcal{I}$ is
not connected. Then, there exists $i\in\\{2,\dots,p-2\\}$ such that no
interval of $\mathcal{I}$ contains both $w_{i}$ and $w_{i+1}$. By definition
of $\mathcal{I}$, $\\{u,v,w_{i},w_{i+1}\\}$ induces a path of $H$ with
extremities $w_{i}$ and $w_{i+1}$. Since $p\geq 6$, there exists
$z\in\\{w_{1},w_{p}\\}$ adjacent to both $w_{i}$ and $w_{i+1}$. As $z$ is
adjacent to neither $u$ nor $v$, $\\{z,w_{i},u,v,w_{i+1}\\}$ induces an odd
hole of $G$, a contradiction to its perfection. Hence, $G_{\mathcal{I}}$ is
connected.

Note that every interval $I=\\{w_{i},\dots,w_{j}\\}$ of $\mathcal{I}$ has odd
cardinality, as otherwise $\\{w_{i-1},w_{i},\dots,w_{j},$ $w_{j+1}\\}$ would
induce, together with $u$ if $I\in\mathcal{P}^{u}$ or $v$ if
$I\in\mathcal{P}^{v}$, an odd antihole of $G$, contradicting its perfection.
By Lemma 1.1, since $p$ is even and $G_{\mathcal{I}}$ is connected,
$\mathcal{I}$ is not an odd intersection interval set. Moreover, the
intersection of more than two intervals of $\mathcal{I}$ is empty by
definition of $\mathcal{P}^{u}$ and $\mathcal{P}^{v}$. Hence, there exists
$I\in\mathcal{P}^{u}$ and $I^{\prime}\in\mathcal{P}^{v}$ whose intersection is
nonempty and has even cardinality. Let $I=\\{w_{i},\dots,w_{k}\\}$ and
$I^{\prime}=\\{w_{j},\dots,w_{\ell}\\}$ with $2\leq i\leq j\leq k\leq\ell\leq
p-1$, Figure 2 gives an illustration. Since $|I|$ and $|I^{\prime}|$ are odd
and $|I\cap I^{\prime}|$ is even, $2\leq i<j<k<\ell\leq p-1$. Suppose that
$j>3$. Then, $w_{1}$ is adjacent to $w_{j-1},\dots,w_{k+1}$ so
$\\{w_{1},v,w_{j-1},\dots,w_{k+1},u\\}$ induces an odd antihole of $G$, a
contradiction. Hence, $j=3$. Similarly, one can prove that $k=p-2$. Hence, $u$
is adjacent to $w_{2},\dots,w_{p-2}$ and $v$ is adjacent to
$w_{3},\dots,w_{p-1}$. Therefore, $(w_{1},\dots,w_{p})$ and the edge $uv$ form
an expanded antihole. ∎

$v$$u$$w_{1}$$w_{p-1}$$w_{2}$$w_{p}$$I$$I^{\prime}$$w_{\ell}$$\dots$$\dots$$w_{k+1}$$w_{k}$$\dots$$w_{j}$$w_{j-1}$$\dots$$\dots$$w_{i}$
Figure 2: Illustration of the proof of Lemma 1.4 (the doted lines
represent nonedges and dots the remaining vertices of the antipath).

######  Theorem 1.5.

Let $G=(V,E)$ be a perfect graph and $uv\in E$. The graph $G/uv$ is not
perfect if and only if $G$ contains an even hole of size at least 6 containing
$uv$ or an expanded antihole involving $uv$.

Proof. $(\Leftarrow)$ In both cases, as mentioned before, contracting $uv$
destroys perfection.

$(\Rightarrow)$ Suppose that $G/uv$ is not perfect. If $G/uv$ contains an odd
hole $H$, then $G$ contains a hole $H^{\prime}$ of size at least $|V(H)|$ by
Lemma 1.2. Since $G$ is perfect, $|V(H^{\prime})|$ is even and at least 6, and
contains $uv$. Otherwise, $G/uv$ contains an odd antihole hence, by Lemma 1.4,
$G$ contains an expanded antihole involving $uv$. ∎

###  1.2 Contracting an edge or a set of edges?

We prove that contraction perfect graphs are characterized by the contraction
of single edges.

######  Theorem 1.6.

A perfect graph is contraction perfect if and only if it remains perfect by
the contraction of any single edge.

Proof. To prove the nontrivial direction, let $G=(V,E)$ be a perfect graph and
$F\subseteq E$ be such that $G/F$ is not perfect. We will prove that $G/e$ is
not perfect for some $e\in E$. Without loss of generality, suppose that $F$
has minimum size, that is, $G/F^{\prime}$ is perfect for all
$F^{\prime}\subsetneq E$ such that $|F^{\prime}|<|F|$. Since $G/F$ is not
perfect, it contains an odd hole or an odd antihole. Suppose that $G/F$
contains an odd hole $C$. By Lemma 1.2, $G$ contains a hole $D$ with
$|V(D)|\geq|V(C)|$. Since $G$ is perfect, $|V(D)|$ is even and at least $6$.
Then, $G/e$ contains the odd hole $D/e$ for any $e\in E(D)$ and thus is not
perfect.

From now on, we may assume that $G$ and $G/F^{\prime}$ for all
$F^{\prime}\subseteq E$ contain no hole of size at least 5. Hence, $G/F$
contains odd antiholes and let us denote by $(w_{0},\dots,w_{p})$ one of them
where $p\geq 6$.

We will first prove that $F$ is a matching. To do this, let us suppose that
$F$ contains two adjacent edges $uv$ and $vw$ whose image in $G/F$ is without
loss of generality $w_{0}$. Let $G^{\prime}=G/(F\setminus\\{uv,vw\\})$. Since
$G^{\prime}/\\{uv,vw\\}$ contains an odd antihole, and since $G^{\prime}/uv$
is perfect by minimality of $F$ and has no hole of size at least 5, then, by
Theorem 1.5, $G^{\prime}/uv$ contains an expanded antihole formed by the even
antipath $P_{0}=(w_{1},\dots w_{p})$, and the edge $x_{uv}w$ where $x_{uv}$ is
the image of $uv$ in $G^{\prime}$.

Without loss of generality suppose that $x_{uv}$ is adjacent to
$\\{w_{2},\dots,w_{p-2}\\}$ and $w$ is adjacent to
$\\{w_{3},\dots,w_{p-1}\\}$. Note that $v$ is not adjacent to $w_{2}$ in $G$,
as otherwise $G^{\prime}/vw$ contains the odd antihole induced by
$\\{x_{vw},w_{1},\dots,w_{p}\\}$ —where $x_{vw}$ is the image $vw$ in
$G^{\prime}/vw$— which contradicts the minimality assumption on $F$. Now,
$G^{\prime}$ contains $uw$ as otherwise $\\{u,v,w,w_{p-1},w_{2}\\}$ induces an
odd hole of $G^{\prime}$, contradicting its perfection. But now,
$G^{\prime}/uw$ contains the odd antihole induced by
$\\{x_{uw},w_{1},\dots,w_{p}\\}$ where $x_{uw}$ is the vertex obtained by
contracting edge $uw$. This contradicts the minimality assumption on $F$,
hence $F$ is a matching.

We now prove that $F$ only contains one edge. Let $uv$ and
$u^{\prime}v^{\prime}$ be two edges of $F$. By minimality assumption, their
images are vertices of $\\{w_{0},\dots,w_{p}\\}$, and up to node relabelling,
let us suppose that the image of $uv$ is $w_{0}$ and the one of
$u^{\prime}v^{\prime}$ is $w_{i}$ with $i\in\\{1,\dots,p/2\\}$. Set
$G^{\prime}=G/(F\setminus\\{uv,u^{\prime}v^{\prime}\\})$. By Lemma 1.4, $uv$
forms with $P_{0}=\\{w_{1},\dots,w_{p}\\}$ an expanded antihole of
$G^{\prime}/u^{\prime}v^{\prime}$. Similarly, $u^{\prime}v^{\prime}$ forms
with $P_{i}=\\{w_{i+1},\dots,w_{p},w_{0},\dots,w_{i-1}\\}$ an expanded
antihole of $G^{\prime}/uv$. By definition of expanded antiholes, we suppose
without loss of generality that $u$ (resp. $u^{\prime}$) is adjacent to
$w_{2}$ (resp. $w_{i-2}$) but not to $w_{p-1}$ (resp. $w_{i+2}$). Hence,
$H_{u}=\\{u,w_{1},\dots,w_{p-1}\\}$ induces an even antihole of
$G^{\prime}/u^{\prime}v^{\prime}$, similarly
$\\{w_{0},\dots,w_{i-1},u^{\prime},w_{i+2},\dots,w_{p},\\}$ induces an even
antihole of $G^{\prime}/uv$. Figure 3 gives an illustration of $H_{u}\cup
u^{\prime}\setminus\\{w_{i},w_{i+1}\\}$, which induces an antihole in
$G^{\prime}$ of size $p-1$, and hence is odd. This contradicts the minimality
assumption on $F$. Therefore $F$ cannot contain two edges, so $G$ does not
remain perfect by the contraction of the edge of $F$. ∎

$w_{0}$$v$$u$$w_{1}$$\cdots$$w_{i-1}$$w_{i}$$u^{\prime}$$v^{\prime}$$w_{i+1}$$w_{i+2}$$\cdots$$w_{p-1}$$w_{p}$
Figure 3: Illustration for the proof of Theorem 1.6:
the odd antihole $H_{u}\cup u^{\prime}\setminus\\{w_{i},w_{i+1}\\}$ of
$G^{\prime}$ is given in light gray

###  1.3 Characterization by forbidden induced subgraphs

By definition, a perfect graph remains perfect by any vertex set deletion.
Thus, a forbidden induced subgraph characterization may be hoped for, and this
tremendous result is the strong perfect graph theorem. Since perfect graphs do
not remain perfect by any edge set contraction (a hole of size 6—which is
perfect—does not remain perfect by the contraction of a single edge), there is
no characterization of perfect graphs by forbidden induced minors.

By definition of contraction perfect graphs, a characterization in terms of
forbidden induced minors can be directly deduced from the strong perfect graph
theorem. Indeed, if a graph is not contraction perfect, then there exists an
edge set contraction and a vertex set deletion that gives an odd hole or an
odd antihole. Therefore, odd hole and odd antiholes are the induced minors to
be forbidden in order to ensure contraction perfection. This list of forbidden
induced minors is inclusionwise minimal because of the strong perfect graph
theorem.

A list of forbidden induced subgraphs that characterizes contraction perfect
graphs would be the set of graphs that yield an odd hole or an odd antihole by
an edge set contraction. Using Theorem 1.6, which limits the set of such
candidates, this section gives the minimal forbidden induced subgraph
characterization of contraction perfect graphs.

######  Corollary 1.7.

A graph is contraction perfect if and only if it contains no hole of size at
least 5, no odd antihole, and no expanded antihole.

Proof. $(\Rightarrow)$ By Theorem 1.5 and the strong perfect graph theorem, a
graph containing one of these structures is not contraction perfect.

$(\Leftarrow)$ If the graph is not perfect, then it contains an odd hole or an
odd antihole. If the graph is perfect but not contraction perfect, then there
exists an edge whose contraction destroys the perfection of the graph by
Theorem 1.6. By Theorem 1.5, this implies that the graph contains an even hole
of size at least 6 or an expanded antihole. ∎

The next lemma gives an example of a non trivial contraction perfect graph
class and will be used as a technical lemma. Remark that $H$ is an induced
subgraph of $G$ if and only if $\overline{H}$ is an induced subgraph of
$\overline{G}$.

######  Lemma 1.8.

Antipaths are contraction perfect.

Proof. The complement $\overline{P}$ of an antipath $P$ is a path. Since the
path $\overline{P}$ is perfect, $P$ is perfect by the weak perfect graph
theorem [16]. An antipath only contains holes of size at most 4. An antipath
contains no antihole since $\overline{P}$ contains no hole. Moreover, an
antipath contains no expanded antihole. Indeed, any contraction of an edge
$uv$ in $P$ yields a vertex whose neighborhood has size at least $|V(P)|-2$.
Hence the degree of such a vertex is too large for the latter to belong to an
antihole. Hence, by Lemma 1.4, $P$ does not contain any expanded antihole
involving $uv$. The result holds by Corollary 1.7. ∎

Note that that the list of forbidden induced subgraphs of Corollary 1.7 is
inclusionwise minimal. Indeed, if it were not the case, then one forbidden
induced subgraph of Corollary 1.7 would contain another one as a proper
induced subgraph, which is not the case as shown in the next observation.

A graph is minimally non contraction perfect if it is not contraction perfect
and each of its proper induced subgraphs is contraction perfect.

######  Observation 1.9.

Expanded antiholes, odd antiholes and holes of size at least 5 are minimally
non contraction perfect.

Proof. Every proper induced subgraph of a hole is a set of disjoint paths and
hence is contraction perfect. Every proper induced subgraph of an odd antihole
is a set of fully connected antipaths, the complement of such a graph is a set
of disjoint paths that is contraction perfect.

We will show that expanded antiholes are minimally non contraction perfect by
considering the complement of an expanded antihole. Let us consider $G$ an
expanded antihole. Note that, $\overline{G}$ contains no antihole of size more
than 6 since it contains precisely 6 vertices whose degree is greater or equal
to 3, that are $W=\\{u,v,w_{1},w_{2},w_{p-1},w_{p}\\}$. Indeed, since an
antihole of size at least 6 is a regular graph whose vertices have degree at
least 3, these are the only candidates that may belong to such an antihole.
Since $\overline{G}[W]$ is not regular, it is not an antihole of size 6, this
proves that $G$ does not contain any holes of size at least 6. Obviously,
$\overline{G}$ does not contain any complement of an expanded antihole as
proper induced subgraphs. Now, note that the holes of $\overline{G}$ are even,
which means that $G$ only contains even antiholes and hence, no hole of size
5. By Corollary 1.7, expanded antiholes are contraction perfect. ∎

######  Corollary 1.10.

Recognizing contraction perfect graphs can be done in polynomial time.

Proof. By Theorem 1.6, deciding whether a graph $G=(V,E)$ is contraction
perfect amounts to check if $G$ is perfect and if, for each contraction of a
single edge, the resulting graph is perfect. Each of these $|E|+1$ perfection
tests can be done in polynomial time [8]. ∎

##  2 Utter graph and co-2-plexes

###  2.1 Perfection of the utter graph

Let $S$ be a co-2-plex. The vertex edge representation of a $S$ is a couple
$(W,F)$ where $W$ are the isolated vertices of $G[S]$ and $F$ are its isolated
edges. Then, by definition of co-2-plexes, $F$ is a matching and contracting
$F$ gives $|F|$ isolated vertices nonadjacent to $W$. In other words, $W$ and
the image of $F$ in $G/F$ form a stable set of $G/F$ of size $|W|+|F|$.

We use this remark to define the utter graph of a graph $G$ in which the
stable sets are in bijection with the co-2-plexes of $G$. The _utter graph_
$u(G)$ of a graph $G=(V,E)$ has vertex set $V\cup E$ and two vertices in
$u(G)$ are adjacent if and only if their corresponding elements in $G$ are
either adjacent, incident, or adjacent by contraction in $G$. Figure 4 gives
an illustration of this definition where the vertices $12$ and $23$ of $u(G)$
respectively correspond to the edges $12$ and $23$ of $G$. For each edge $uv$
of $G$, $G/uv$ is the subgraph of $u(G)$ induced by $V\setminus\\{u,v\\}\cup
uv$ where $uv$ denotes the vertex of $u(G)$ associated with edges $uv$.
Similarly, for a matching $F\subseteq E$, $G/F$ is the subgraph of $u(G)$
induced by $V\setminus V(F)$ and the vertices of $u(G)$ associated with edges
in $F$.

$1$$2$$3$ (a) $G$

$1$$2$$3$$23$$12$ (b) $u(G)$

Figure 4: A graph $G$ and its utter graph $u(G)$.

######  Lemma 2.1.

There is a bijection between the co-2-plexes of $G$ and the stable sets of
$u(G)$.

Proof. By definition of utter graphs, a vertex subset $W$ and an edge set $F$
is a vertex edge representation $(W,F)$ if and only if $W\cup T$ is a stable
set of $u(G)$. ∎

Note that by definition of contraction perfect graphs, adding a true twin to
any vertex preserves contraction perfection. Moreover, the forbidden induced
subgraph characterization also proves that adding false twins preserves
contraction perfection. Indeed, none of these forbidden induced subgraphs
contain false twins. This gives the following replication lemma for
contraction perfect graphs.

######  Lemma 2.2.

Adding true or false twins preserves contraction perfection.

We say that a graph class is _replicable_ if adding true twins to any graph of
that class yields another graph of that class.

######  Theorem 2.3.

Let $\mathcal{C}$ be a induced minor closed and replicable graph class, then
$G\in\mathcal{C}$ if and only if $u(G)\in\mathcal{C}$.

Proof. ($\Leftarrow$) Since $G$ is an induced subgraph of $u(G)$, the result
follows from the assumptions on $\mathcal{C}$.

($\Rightarrow$) Let $\widetilde{G}$ be obtained from $G$ by adding, for every
edge $uv\in E$, a twin $u^{\prime}$ (resp. $v^{\prime}$) to $u$ (resp. $v$).
By construction, $\widetilde{G}$ contains the edge $u^{\prime}v^{\prime}$. Let
$F$ be the set of such edges for every edge $uv\in E$. Note that,
$\widetilde{G}/F=u(G)$ and that $\widetilde{G}/F$ is obtained by adding true
twins and contracting edges. Since $\mathcal{C}$ is replicable and induced
minor closed, $u(G)$ belongs to $\mathcal{C}$. ∎

######  Observation 2.4.

The conditions given in Theorem 2.3 are not necessary.

Proof. Consider the sequence $G_{i+1}=u(G_{i})$, for $i\in\mathbb{Z}^{+}$,
where $G_{0}=C_{4}$. Let $\mathcal{C}$ be the set of all $G_{i}$ completed by
induction with the graphs whose utter graph is in $\mathcal{C}$. Then, for any
graph $G$ and its utter graph $u(G)$, we have that $G\in\mathcal{C}$ if and
only if $u(G)\in\mathcal{C}$. Note that each $G_{i}$ contains a $C_{4}$ and by
construction, if $G$ is in $\mathcal{C}$, then there exists
$i\in\mathbb{Z}^{+}$ such that, $G=G_{i}$ or there exists $k\in\mathbb{Z}^{+}$
such that $u^{k}(G)=G_{i}$. Since $G$ is a clique if and only if $u(G)$ is a
clique, no element of $\mathcal{C}$ is a clique, in particular
$K_{2}=(\\{v_{1},v_{2}\\},\\{v_{1}v_{2}\\})$ is not in $\mathcal{C}$ but is an
induced subgraph of every element in $\mathcal{C}$. Hence $\mathcal{C}$ is not
induced minor closed. ∎

Since the class of contraction perfect graphs is replicable by Lemma 2.2 and
induced minor closed by definition, the following equivalence can be deduced
from Theorem 2.3.

######  Corollary 2.5.

A graph is contraction perfect if and only if its utter graph is contraction
perfect.

Now, we show that contraction perfect graphs are precisely those for which the
utter graph is perfect. This means that every perfect utter graph is also
contraction perfect.

######  Corollary 2.6.

A graph is contraction perfect if and only if its utter graph is perfect.

Proof. Let $G=(V,E)$ be a graph.

$(\Leftarrow)$ By definition of utter graphs, $G$ and $G/e$ for $e\in E$ are
induced subgraphs of $u(G)$. Hence, all those graphs are perfect since $u(G)$
is. By Theorem 1.6, this implies that $G$ is contraction perfect.

$(\Rightarrow)$ If $G$ is contraction perfect, then so is $u(G)$ by Theorem
2.5. By definition of contraction perfect graphs, this implies that $u(G)$ is
perfect. ∎

Given a cost function $c$ on the vertices of $G$, let
$\widetilde{c}_{u}=c_{u}$, for all $u\in V$, and
$\widetilde{c}_{uv}=c_{u}+c_{v}$, for all $uv\in E$. Then finding a maximum
$c$-weighted co-2-plex in $G$ is equivalent to finding a maximum
$\widetilde{c}$-weighted stable set in $u(G)$, and then can be done in
polynomial time [11]. This gives the following corollary by Theorem 2.6.

######  Corollary 2.7.

Finding a maximum weight co-2-plex in a contraction perfect graph is solvable
in polynomial time.

Therefore when $u(G)$ is perfect, computing a minimum covering by stable sets
in $u(G)$ can be done in polynomial time. Note that a minimum cover of a graph
by stable sets is exactly a graph coloring. A further question is whether a
graph coloring of $u(G)$ helps us to find a minimum covering of $G$ by
co-2-plexes. However, coloring the utter graph yields several coverings of
$G$. Two opposite examples can be obtained as follows: a covering using only
the stable sets of $u(G)[V]$, which are stable sets of $G$; and a covering
using the stables of $u(G)[E]$ which are sets of edges of $G$ pairwise
nonadjacent by contraction.

In Figure 4, a covering of $G$ by co-$2$-plexes involves two co-$2$-plexes,
whereas a coloring of $u(G)$ is composed of four stables sets. Hence the two
problems are not equivalent. An open question is whether a minimum co-2-plex
covering of $G$ can be deduced from a given coloring of $u(G)$. Indeed, in
Figure 4, both examples given in the previous paragraphs yield minimal
coverings of $G$ $\\{\\{1,3\\},\\{2\\}\\}$ and $\\{\\{12\\},\\{23\\}\\}$.

###  2.2 Subclasses of perfect graphs

This section shows how Theorem 2.3 applies to other graph classes. A split
graph is a graph whose vertex set can be partitioned into a stable set and a
clique. A split graph is equivalently, a graph that does not contain $C_{4}$
or its complement. A set of intervals is _nested_ if every couple of interval
either has an empty intersection or one is contained in the other. A trivially
perfect graph is an interval graph built from a nested interval set.
Equivalently, a trivially perfect graph is a graph with no hole or path of
size 4. For $k\geq 3$, a $k$-hole-free graph is a graph whose holes are all of
size at most $k$. The well-known chordal graph are the $3$-hole-free graphs.

Trivially perfect graphs are interval graphs, split and interval graphs are
chordal. All these graph classes are contraction perfect, which is not the
case for $k$-hole-free graphs with $k\geq 4$.

A graph class $\mathcal{C}$ is said stable by utter graphs if:
$G\in\mathcal{C}$ if and only if $u(G)\in\mathcal{C}$.

######  Corollary 2.8.

The split (resp. trivially perfect, interval, chordal, $k$-hole-free) graphs
are stable by utter graphs. However, perfect graphs are not stable by utter
graphs.

Proof. One can show that all these graph classes are induced minor closed and
replicable. We only detail the case of interval graphs.

Every induced subgraph $G_{\mathcal{I}}[W]$ of an interval graph
$G_{\mathcal{I}}$ is the interval graph built from the interval set containing
intervals of $\mathcal{I}$ associated with $W$. Contracting an edge $uv$ in
$G_{\mathcal{I}}$ corresponds to replacing the intervals associated with $u$
and $v$ in $\mathcal{I}$ by the union of both intervals. Adding a true twin to
a vertex $v$ in an interval graph $G_{\mathcal{I}}$ corresponds to duplicating
the interval associated with $v$ in $\mathcal{I}$. Then, from Theorem 2.3,
interval graphs are stable by utter graphs.

Note that, for the $k$-hole-free graphs, the induced minor closeness follows
from their definition and Lemma 1.2. A counter example for a perfect graph to
be not stable by utter graphs is $C_{6}$ which is perfect, but whose utter
graph contains many $C_{5}$. ∎

Since the complement of perfect graphs are perfect, a natural question is to
investigate the complement of contraction perfect graphs. However,
$\overline{C_{6}}$ is an antihole of size 6, hence contraction perfect, but
$C_{6}$ is not.

######  Observation 2.9.

The complement of a contraction perfect graph is not necessarily contraction
perfect.

## Conclusion

In this paper, we approach edge contraction in perfect graphs by
characterizing the contraction perfect graphs in several manners: by
contracting either a single edge or an edge set, by forbidden induced
subgraphs and by the utter graph perfection. As a byproduct, the recognition
of contraction perfect graphs is polynomial. Moreover, using utter graphs, the
maximum weight co-2-plex problem becomes solvable in polynomial time in
contraction perfect graphs. Finally, we focus on particular subclasses of
perfect graphs.

For $k=2$, it remains an intriguing question whether a coloring of the utter
graph can be used to get a minimal covering of the starting graph with
co-$2$-plexes. When $k>2$, another interesting question is whether some
extension of utter graphs could capture co-$k$-plexes as familiar
combinatorial objects, like stable sets in utter graphs do for co-2-plexes.
From a polyhedral point of view, the equivalence between co-2-plexes of a
graph and stable sets of its utter graph will give extended formulations for
the co-2-plexe polytope from the stable set polytope.

Contraction perfect graphs being a new subclass of perfect graphs, one may
also be interested in combinatorial algorithms to find a maximum clique/stable
set or a minimum coloring on such graphs. Since, unlike for perfect graphs,
the complement of a contraction perfect graph is not necessarily contraction
perfect, finding a maximum clique or a stable set may lead to distinct
studies.

## Acknowledgments

We thank Daria Pchelina for her contribution to Lemma 1.1.

## References

  * [1] Balasundaram, B., Butenko, S., and Hicks, I. Clique relaxations in social network analysis: The maximum $k$-plex problem.  Operations Research 59, 1 (2011), 133–142.
  * [2] Bienstock, D. On the complexity of testing for odd holes and induced odd paths.  Discrete Mathematics 90, 1 (1991), 85–92.
  * [3] Chang, L., Xu, M., and Strash, D. Efficient maximum k-plex computation over large sparse graphs.  Proc. VLDB Endow. 16, 2 (2022), 127–139.
  * [4] Chen, P., Wan, H., Cai, S., Li, J., and Chen, H. Local search with dynamic-threshold configuration checking and incremental neighborhood updating for maximum k-plex problem.  Proceedings of the AAAI Conference on Artificial Intelligence 34, 03 (2020), 2343–2350.
  * [5] Chen, P., Wan, H., Cai, S., Luo, W., and Li, J. Combining reinforcement learning and configuration checking for maximum k-plex problem.  ArXiv abs/1906.02578 (2019).
  * [6] Chudnovsky, M., Cornuéjols, G., Liu, X., Seymour, P. D., and Vuskovic, K. Recognizing berge graphs.  Comb. 25, 2 (2005), 143–186.
  * [7] Chudnovsky, M., Robertson, N., Seymour, P., and Thomas, R. The strong perfect graph theorem.  Annals of Mathematics 164 (2006), 51–229.
  * [8] Cornuéjols, G., Liu, X., and Vuskovic, K. A polynomial algorithm for recognizing perfect graphs.  vol. 2003, pp. 20 – 27.
  * [9] Dai, Q., Li, R.-H., Qin, H., Liao, M., and Wang, G. Scaling up maximal k-plex enumeration.  345–354.
  * [10] Fonlupt, J., and Uhry, J.-P. Transformations which preserve perfectness and h-perfectness of graphs.  83–95.
  * [11] Grötschel, M., Lovász, L., and Schrijver, A. Polynomial algorithms for perfect graphs.  In Topics on Perfect Graphs, C. Berge and V. Chvátal, Eds., vol. 88 of North-Holland Mathematics Studies. North-Holland, 1984, pp. 325–356.
  * [12] Hsieh, S.-Y., Kao, S.-S., and Lin, Y.-S. A swap-based heuristic algorithm for the maximum $k$ -plex problem.  IEEE Access 7 (2019), 110267–110278.
  * [13] Huang, Y., and Shen, C. Learning computation bounds for branch-and-bound algorithms to k-plex extraction.  CoRR abs/2208.05763 (2022).
  * [14] Jabbour, S., Mhadhbi, N., Raddaoui, B., and Sais, L. A declarative framework for maximal k-plex enumeration problems.  In Adaptive Agents and Multi-Agent Systems (2022).
  * [15] Jin, Y., Drake, J. H., Benlic, U., and He, K. Effective reinforcement learning based local search for the maximum k-plex problem.  ArXiv abs/1903.05537 (2019).
  * [16] Lovász, L. Normal hypergraphs and the perfect graph conjecture.  Discrete Mathematics 2, 3 (1972), 253–267.
  * [17] Maffray, F., and Trotignon, N. A class of perfectly contractile graphs.  Journal of Combinatorial Theory, Series B 96, 1 (2006), 1–19.
  * [18] McClosky, B., and Hicks, I. The co-2-plex polytope and integral systems.  Siam Journal on Discrete Mathematics 23 (2009), 1135–1148.
  * [19] McClosky, B., and Hicks, I. Combinatorial algorithms for the maximum $k$-plex problem.  J. Comb. Optim. 23 (2012), 29–49.
  * [20] Meyniel, H. A new property of critical imperfect graphs and some consequences.  European Journal of Combinatorics 8, 3 (1987), 313–316.
  * [21] Okubo, Y., Matsudaira, M., and Haraguchi, M. Detecting maximum k-plex with iterative proper l-plex search.  In Discovery Science (Cham), Springer International Publishing 2014, pp. 240–251.
  * [22] Pullan, W. Local search for the maximum k-plex problem.  J. Heuristics 27, 3 (2021), 303–324.
  * [23] Seidman, S., and Foster, B. A graph‐theoretic generalization of the clique concept.  Journal of Mathematical Sociology 6 (1978), 139–154.
  * [24] Stetsyuk, P. I., Khomiak, O., Blokhin, Y., and Suprun, A. A. Optimization problems for the maximum k-plex*.  Cybernetics and Systems Analysis 58 (2022), 530–541.
  * [25] Wang, Y., Jian, X., Yang, Z., and Li, J. Query optimal k-plex based community in graphs.  Data Sci. Eng. 2, 4 (2017), 257–273.
  * [26] Wang, Z., Chen, Q., Hou, B., Suo, B., Li, Z., Pan, W., and Ives, Z. G. Parallelizing maximal clique and k-plex enumeration over graph data.  Journal of Parallel and Distributed Computing 106 (2017), 79–91.
  * [27] Wu, K., Gao, J., Chen, R., and Cui, X. Vertex selection heuristics in branch-and-bound algorithms for the maximum k-plex problem.  International Journal on Artificial Intelligence Tools 28, 05 (2019), 1950015.
  * [28] Zheng, J., Jin, M., Jin, Y., and He, K. Relaxed graph color bound for the maximum k-plex problem.  CoRR abs/2301.07300 (2023).
  * [29] Zhou, Y., Hu, S., Xiao, M., and Fu, Z.-H. Improving maximum k-plex solver via second-order reduction and graph color bounding.  Proceedings of the AAAI Conference on Artificial Intelligence 35, 14 (2021), 12453–12460.