11institutetext:  Centre for Economic and Regional Studies, Budapest, Hungary;
11email<EMAIL_ADDRESS>22institutetext: Budapest University of
Technology and Economics, Budapest, Hungary

# Recognizing when a preference system is close to admitting a master list

Ildikó Schlotter 1122

###### Abstract

A preference system $\mathcal{I}$ is an undirected graph where vertices have
preferences over their neighbors, and $\mathcal{I}$ admits a master list if
all preferences can be derived from a single ordering over all vertices. We
study the problem of deciding whether a given preference system $\mathcal{I}$
is _close to_ admitting a master list based on three different distance
measures. We determine the computational complexity of the following
questions: can $\mathcal{I}$ be modified by (i) $k$ swaps in the preferences,
(ii) $k$ edge deletions, or (iii) $k$ vertex deletions so that the resulting
instance admits a master list? We investigate these problems in detail from
the viewpoint of parameterized complexity and of approximation. We also
present two applications related to stable and popular matchings.

##  1 Introduction

A preference system models a set of agents as an undirected graph where agents
are vertices, and each agent has preferences over its neighbors. Preference
systems are a fundamental concept in the area of matching under preferences
which, originating in the seminal work of Gale and Shapley [21] on stable
matchings, is a prominent research field in the intersection of algorithm
design and computational social choice that has steadily gained attention over
the last two decades.

Preference systems may admit a master list, that is, a global ranking over all
agents from which agents derive their preferences. Master lists arise
naturally in many practical scenarios such as P2P networks [20, 35], job
markets [28], and student housing assignments [39]. Consequently, master lists
and its generalizations have been the focus of research in several papers [28,
33, 29, 8, 38, 11, 13].

In this work we aim to investigate the computational complexity of recognizing
preference systems that are _close to_ admitting a master list. Such instances
may arise as a result of noise in the data set, or in scenarios where a global
ranking of agents is used in general, with the exception of a few anomalies.

###  1.1 Our contribution

We introduce three measures to describe the distance of a given preference
system $\mathcal{I}$ from the class of preference systems admitting a master
list. The first measure, $\Delta^{\textup{swap}}(\mathcal{I})$ is based on the
swap distance between agents’ preferences, while the measures
$\Delta^{\textup{edge}}(\mathcal{I})$ and
$\Delta^{\textup{vert}}(\mathcal{I})$ are based on classic graph operations,
the deletion of edges or vertices; precise definitions follow in Section 2. We
study in detail the complexity of computing these values for a given
preference system $\mathcal{I}$. After proving that computing any of these
three measures is $\mathsf{NP}$-hard, we apply the framework of parameterized
complexity and of approximation algorithms to gain a more fine-grained
insight.

In addition to the problems of computing
$\Delta^{\textup{swap}}(\mathcal{I})$, $\Delta^{\textup{edge}}(\mathcal{I})$,
and $\Delta^{\textup{vert}}(\mathcal{I})$, we briefly look at two
applications. First, we show that if a strict preference system $\mathcal{I}$
is close to admitting a master list, then we can bound the number of stable
matchings as a function of the given distance measure. This yields an
efficient way to solve a wide range of stable matching problems in instances
that are close to admitting a master list. Second, we consider an optimization
problem over popular matchings where the task is to find a maximum-utility
popular matching while keeping the number (or cost) of blocking edges low. We
prove that this notoriously hard problem can be efficiently solved if
preferences are close to admitting a master list. In both of these
applications, the running time of the obtained algorithms heavily depends on
the distance measure used.

###  1.2 Related work

Master lists have been extensively studied in the context of stable matchings
[28, 29, 8, 13]. Various models have been introduced in the literature to
generalize master lists, and capture preferences that are similar to each
other in some sense. Closest to our work might be the paper by Bredereck et
al. [8] who examine the complexity of multidimensional stable matching
problems on instances that are, in some sense, close to admitting a master
list. Abraham et al. investigated a setting where agent pairs are ranked
globally [1]. Bhatnagar et al. [4] examined three restrictions on preference
systems: the $k$-attribute model where agents are evaluated through a linear
function of $k$ attributes, the $k$-range model where for each agent $p$ on
one side of a bipartite preference system the rankings of $p$ by the agents on
the other side falls into a range of size $k$, and the $k$-list model where
agents can be partitioned into $k$ types, and agents of the same type have
identical preferences. Meeks and Rastegari studied hard problems under a
variant of the $k$-list model [38]. Khanchandani and Wattenhofer considered a
distributed stable matching problem in a bipartite $k$-range model [33]. Cheng
and Rosenbaum [11] examined the expressive powers of the $k$-range,
$k$-attribute, and a bipartite version of the $k$-list model in terms of the
rotation poset realized by such preference systems.

Restricted preference profiles have been also extensively studied in the
broader context of computational social choice; see the survey by Elkind et
al. [17]. In election systems, computing the Kemeny score [32] for a multiset
of votes (where each vote is a total linear order over a set of candidates) is
analogous to computing the value $\Delta^{\textup{swap}}(\mathcal{I})$ for a
preference system $\mathcal{I}$, although there are some differences between
these two problems. Apart from the literature on the computational complexity
of computing the Kemeny score (see e.g. [2, 27, 3, 19]), our work also relates
to the problem of computing certain distance measures between elections which
has been investigated by Boehmer et al. [6]. Distance from a strongly
unanimous profile (where all votes coincide) has been considered as a
parameter in the study by Gupta et al. on committee selection [23].

####  1.2.1 Organization.

We start with the preliminaries in Section 2, and define our three distance
measures and the corresponding problems in Section 3. Section 4 contains our
main results, first for strict and then for weak preferences, and we present
our two applications in Section 5. We conclude with a short summary and some
suggestions for future research in Section 6.

##  2 Preliminaries

Let us now introduce our notation, giving all necessary definition about
directed and undirected graphs, preference systems, and certain concepts of
computational complexity theory.

###  2.1 Graph-theoretic notions

We define most of the basic graph-related concepts we need for directed
graphs, as the corresponding concepts for undirected graphs are usually
defined analogously. We use the notation $[n]=\\{1,\dots,n\\}$ for any
$n\in\mathbb{Z}^{+}$.

Directed graphs. For a directed graph (or _digraph_) $D$, we denote by $V(D)$
and $A(D)$ its vertex and arc set, respectively; each arc is an ordered pair
of vertices. For some vertex $v\in V(G)$ we let $N^{-}_{D}(v)$ and
$N^{+}_{D}(v)$ denote the set containing $v$’s _in-_ and _out-neighbors_ in
$D$, respectively. A _loop_ is an arc $(v,v)$ for some $v\in V(D)$, and two
arcs are _parallel_ if they both point from $a$ to $b$ for some $a,b\in V(D)$.
In this paper, parallel arcs will be labelled, and we will be able to identify
them via their labels. A _source_ in $D$ is a vertex with in-degree 0, and a
_sink_ is one with out-degree 0. A _path_ in $D$ is a series
$v_{1},\dots,v_{p}$ of distinct vertices such that $(v_{i},v_{i+1})\in A(D)$
for each $i\in[p-1]$; if additionally, $(v_{p},v_{1})$ is also an arc in $D$,
then these vertices form a _cycle_ in $D$. We say that $D$ is acyclic, if it
contains no cycles. The vertices of an acyclic digraph can be listed in a
_topological order_ which is a strict order $v_{1},\dots,v_{n}$ of the
vertices of $D$ such that any arc $(v_{i},v_{j})\in A(D)$ satisfies $i<j$.

Graph operations. A _subgraph_ of $D$ is a graph obtained by deleting some
edges and vertices from $D$. For a set $X$ of edges or vertices in $D$, we let
$D-X$ denote the subgraph of $D$ obtained by deleting $X$ from $D$. For a set
$W\subseteq V(D)$ of vertices, we let $D[W]=D-(V(D)\setminus W)$ denote the
subgraph _induced_ by $W$. We may interpret paths or cycles in $G$ also as
subgraphs of $G$. By _subdividing_ an arc $(u,v)$ we mean replacing $(u,v)$
with two new arcs $(u,x)$ and $(x,v)$ where $x$ is a newly introduced vertex;
the inverse operation is _lifting_ the vertex $x$ from the path $(u,x,v)$. By
_contracting_ a subgraph $D^{\prime}$ of $D$ we mean the following: we replace
$V(D^{\prime})$ with a new vertex $x$, and for each arc $e\in A(D)$ we replace
any endpoint of $e$ contained in $D^{\prime}$ by $x$; if any loops are created
in the process, we delete them.

Undirected graphs. Given an undirected graph $G$, we let $V(G)$ and $E(G)$
denote its vertex and edge set, respectively; each edge is a set of two of
vertices. For some vertex $v\in V(G)$ we let $N_{G}(v)$ denote the set
containing $v$’s _neighbors_ in $G$. All other concepts defined in the
previous two paragraphs are defined analogously for undirected graphs. A
_clique_ is a set $K\subseteq V(G)$ of vertices such that there is an edge
between each two vertices of $K$. The _bidirected_ version of $G$ is obtained
by replacing each edge $\\{u,v\\}\in E(G)$ by two arcs $(u,v)$ and $(v,u)$.

###  2.2 Preference systems

A _preference system_ is defined as a pair $\mathcal{I}=(G,\preceq)$ where $G$
is an undirected graph and $\preceq=\\{\preceq_{v}:v\in V(G)\\}$ where
$\preceq_{v}$ is a weak or a strict order over $N_{G}(v)$ for each vertex
$v\in V(G)$, indicating the _preferences_ of $v$. For some $v\in V(G)$ and
$a,b\in N_{G}(v)$, we say that $v$ _prefers_ $b$ to $a$, denoted by
$a\prec_{v}b$, if $a\not\preceq_{v}b$. We write $a\sim_{v}b$, if
$a\preceq_{v}b$ and $b\preceq_{v}a$. A _tie_ in $v$’s preferences is a maximal
set $T\subseteq N_{G}(v)$ such that $t\sim_{v}t^{\prime}$ for each $t$ and
$t^{\prime}$ in $T$. If each tie has size 1, then $\mathcal{I}$ is a _strict
preference system_ , and we may denote it by $(G,\prec)$.

Deletions and Swaps. For a set $X$ of edges or vertices in $G$, let
$\mathcal{I}-X$ denote the preference system whose underlying graph is $G-X$
and where the preferences of each vertex $v\in V(G-X)$ is the restriction of
$\preceq_{v}$ to $N_{G-X}(v)$. We may refer to $\mathcal{I}-X$ as a sub-
instance of $\mathcal{I}$.

If vertex $v$ has strict preferences $\prec_{v}$ in $\mathcal{I}$, then a
_swap_ is a triple $(a,b;v)$ with $a,b\in N_{G}(v)$, and it is _admissible_ if
$a$ and $b$ are consecutive111Vertices $a$ and $b$ are consecutive in $v$’s
preferences, if either $a\prec_{v}b$ but there is no vertex $c$ with
$a\prec_{v}c\prec_{v}b$, or $b\prec_{v}a$ but there is no vertex $c$ with
$b\prec_{v}c\prec_{v}a$. in $v$’s preferences. _Performing_ an admissible swap
$(a,b;v)$ in $\mathcal{I}$ means switching $a$ and $b$ in $v$’s preferences;
the resulting preference system is denoted by $\mathcal{I}\lhd(a,b;v)$. For a
set $S$ of swaps, $\mathcal{I}\lhd S$ denotes the preference system obtained
by performing the swaps in $S$ in $\mathcal{I}$ in an arbitrary order as long
as each swap is admissible (if this is not possible, $\mathcal{I}\lhd S$ is
undefined). For non-strict preferences, similar notions will be discussed in
Section 3.

Master Lists. A weak or strict order $\preceq^{\textup{ml}}$ over $V(G)$ is a
_master list_ for $(G,\preceq)$, if for each $v\in V(G)$, the preferences of
$v$ are _consistent_ with $\preceq^{\textup{ml}}$, that is, $\preceq_{v}$ is
the restriction of $\preceq^{\textup{ml}}$ to $N_{G}(v)$. We will denote by
$\mathcal{F}_{\textup{ML}}$ the family of those preference systems that admit
a master list. Notice that $\mathcal{F}_{\textup{ML}}$ is closed under taking
subgraphs: if we delete a vertex or an edge from a preference system in
$\mathcal{F}_{\textup{ML}}$, the remainder still admits a master list.

Stable and popular matchings. A _matching_ in a preference system
$\mathcal{I}$ is a set of edges such that no two of them share an endpoint.
For an edge $\\{a,b\\}$ in $M$, we say that $M$ _matches_ $a$ to $b$ and vice
versa, and we denote this by setting $M(a)=b$ and $M(b)=a$. A vertex $v$ in
$G$ is _unmatched_ in $M$ if no edge of $M$ has $v$ as its endpoint. A
blocking edge for $M$ is an edge $\\{a,b\\}$ of $G$ such that (i) either $a$
is unmatched in $M$ or $M(a)\prec_{a}b$, and (ii) either $b$ is unmatched in
$M$ or $M(b)\prec_{b}a$. The set of blocking edges for $M$ is denoted by
$\textup{bp}(M)$, and $M$ is _stable_ if $\textup{bp}(M)=\emptyset$. For a
preference system $\mathcal{I}$, we will denote by $\mathcal{S}(\mathcal{I})$
the set of stable matchings in $\mathcal{I}$.

We say that a vertex $v$ prefers some matching $M$ over another matching
$M^{\prime}$, if either $v$ is unmatched in $M^{\prime}$ but matched in $M$,
or it is matched in both but $M^{\prime}(v)\prec_{v}M(v)$. For two matchings
$M$ and $M^{\prime}$ in $\mathcal{I}$, we say that $M$ is _more popular than_
$M^{\prime}$, if the number of vertices that prefer $M$ to $M^{\prime}$ is
more than the number of vertices preferring $M^{\prime}$ to $M$. A matching
$M$ in _popular_ in $\mathcal{I}$, if there is no matching more popular than
$M$.

###  2.3 Computational complexity

We assume that the reader is familiar with the basic concepts and tools of
classic computational complexity theory, such as $\mathsf{NP}$-hardness and
polynomial-time reductions.

Parameterized complexity. In the framework of parameterized complexity, each
problem instance $\mathcal{I}$ is associated with an integer $k$, and the aim
is to find algorithms whose running time is $f(k)|\mathcal{I}|^{O(1)}$ for
some computable function $f$; such an algorithm is called _fixed-parameter
tractable_ (or FPT) with parameter $k$. The basic complexity class in the
parameterized framework is $\mathsf{W}[1]$, and if a parameterized problem is
proved to be $\mathsf{W}[1]$-hard, then this is considered a strong evidence
that it is not FPT with the given parameterization. To show that a given
parameterized problem $\mathcal{P}$ is $\mathsf{W}[1]$-hard, it suffices to
give a _parameterized_ or _FPT reduction_ from another $\mathsf{W}[1]$-hard
problem $\mathcal{Q}$, which is a function $f$ that for each instance
$(\mathcal{I},k)$ of the problem $\mathcal{Q}$ computes in FPT time an
equivalent instance $(\mathcal{I}^{\prime},k^{\prime})$ of $\mathcal{P}$ such
that $k^{\prime}\leq g(k)$ for some function $g$.

Approximation. For a minimization problem $\mathcal{P}$, let
$\textup{obj}_{\mathcal{P}}$ denote its objective function, and let
$\textup{OPT}_{\mathcal{P}}(\mathcal{I})=\textup{obj}_{\mathcal{I}}(S)$ denote
the value of an optimal solution $S$ for an instance $\mathcal{I}$ of
$\mathcal{P}$. For some $c\geq 1$, an algorithm is a _$c$ -approximation_ or
an approximation with _factor_ $c$ for $\mathcal{P}$, if for any instance
$\mathcal{I}$ of $\mathcal{P}$ it returns a solution $S$ for $\mathcal{I}$
with $\textup{obj}_{\mathcal{P}}(S)\leq c\cdot\textup{OPT}_{\mathcal{P}}(I)$.
For two minimization problems $\mathcal{P}_{1}$ and $\mathcal{P}_{2}$, an
_approximation preserving reduction_ [41, Section A.3.1] from
$\mathcal{P}_{1}$ to $\mathcal{P}_{2}$ consists of two functions $f$ and $g$
computable in polynomial time such that

  * (i)

for any instance $\mathcal{I}_{1}$ of $\mathcal{P}_{1}$, function $f$ yields
an instance $\mathcal{I}_{2}=f(\mathcal{I}_{1})$ of $\mathcal{P}_{2}$ with
$\textup{OPT}_{\mathcal{P}_{2}}(\mathcal{I}_{2})\leq\textup{OPT}_{\mathcal{P}_{1}}(\mathcal{I}_{1})$,
and

  * (ii)

for any solution $S_{2}$ of $\mathcal{I}_{2}$, function $g$ yields a solution
$S_{1}=g(S_{2})$ for $\mathcal{I}_{1}$ with
$\textup{obj}_{\mathcal{I}_{1}}(S_{1})\leq\textup{obj}_{\mathcal{I}_{2}}(S_{2})$.

Given such a reduction, an approximation algorithm $\mathcal{A}$ for
$\mathcal{P}_{2}$ with factor $c$ yields an approximation algorithm for
$\mathcal{P}_{1}$ with the same factor.

Some of our intractability results hold under certain standard complexity-
theoretic assumptions such as $\mathsf{W}[1]\neq\mathsf{FPT}$ or the so-called
_Unique Games Conjecture_ [34] which we will use in our paper without giving
its precise definition.

For more on these topics, we refer the reader to the books [22, 15, 14, 41].

##  3 Problem definition and initial results

In Section 3.1 we introduce the notion of a _preference digraph_ , a directed
graph associated with a given preference system, which can be exploited to
obtain a useful characterization of preference systems that admit a master
list. In Section 3.2 we define our three measures for describing the distance
of a preference system from $\mathcal{F}_{\textup{ML}}$, and observe a simple
fact regarding the relationship between these distances.

###  3.1 Characterization of $\mathcal{F}_{\textup{ML}}$ through the
preference diraph

With a strict preference system $\mathcal{I}=(G,\prec)$ where $G=(V,E)$, we
associate an arc-labelled directed graph $D_{\mathcal{I}}$ that we call the
_preference digraph_ of $\mathcal{I}$. We let $D_{\mathcal{I}}$ have the same
set of vertices as $G$, and we define the arcs in $D_{\mathcal{I}}$ by adding
an arc $(a,b)$ labelled with $v$ whenever $a\prec_{v}b$ holds for some
vertices $a,b$ and $v$ in $V$. Note that several parallel arcs may point from
$a$ to $b$ in $D_{\mathcal{I}}$, each having a different label, so we have
$|V(D_{\mathcal{I}})|=|V|$ but $|A(D_{\mathcal{I}})|=O(|V|\\!\cdot\\!|E|)$.
Observation 3.1 immediately follows from the fact that acyclic digraphs admit
a topological order.

######  Observation 3.1.

A strict preference system $(G,\prec)$ admits a master list if and only if the
preference digraph of $G$ is acyclic.

For a preference system $\mathcal{I}=(G,\preceq)$ with $G=(V,E)$ that is not
necessarily strict we extend the concept of the preference digraph of
$\mathcal{I}$ as follows. Again, we let $D_{\mathcal{I}}$ have $V$ as its
vertex set, but now we add two types of arcs to $D_{\mathcal{I}}$: for any $v$
in $V$ and $a,b\in N_{G}(V)$ with $a\neq b$ we add a _strict arc_ $(a,b)$ with
label $v$ whenever $a\prec_{v}b$, and we add a pair of _tied arcs_ $(a,b)$ and
$(b,a)$, both with label $v$, whenever $a\sim_{v}b$. Note that this way we
indeed generalize our definition above for the preference digraph of strict
preference systems. We will call a cycle of $D_{\mathcal{I}}$ that contains a
strict arc a _strict cycle_. The following lemma is a straightforward
generalization of Observation 3.1.

######  Lemma 3.2.

A preference system $(G,\preceq)$ admits a master list if and only if no cycle
of the preference digraph of $G$ is strict.

###### Proof.

By definition, $(G,\preceq)\in\mathcal{F}_{\textup{ML}}$ if and only if there
exists a weak order $\preceq^{\textup{ml}}$ on $V$ such that $\preceq_{v}$ is
the restriction of $\preceq^{\textup{ml}}$ to $N_{G}(v)$ for any $v\in V$.

Let $C$ be a cycle in $D_{\mathcal{I}}$, and suppose that a master list
$\preceq^{\textup{ml}}$ exists for $\mathcal{I}$. Note that for any arc
$(a,b)$ in $C$ we know that $a\preceq_{v}b$ for some $v\in V$, implying
$a\preceq^{\textup{ml}}b$. As this holds for any arc on the cycle, we get that
only $a\sim^{\textup{ml}}b$ is possible, and therefore no arc on $C$ can be
strict.

For the other direction, suppose that no cycle in $D_{\mathcal{I}}$ contains a
strict arc. Let us define a master list $\preceq^{\textup{ml}}$ on $V$ as
follows. First, we let $a\sim^{\textup{ml}}b$ whenever $a$ is reachable from
$b$ via tied arcs. Clearly, $\sim^{\textup{ml}}$ is symmetric, and moreover,
if $a\sim^{\textup{ml}}b$, then $a\prec_{v}b$ is not possible for any $v\in
V$, as otherwise a path from $b$ to $a$ via tied arcs would form a cycle with
the strict arc $(a,b)$ with label $v$. Furthermore, contracting all tied arcs
creates an acyclic digraph $D^{\prime}$. Let $\prec^{\textup{top}}$ be a
topological ordering on the vertices of $D^{\prime}$. For each $v\in V$, let
$\varphi(v)$ denote the vertex of $D^{\prime}$ to which $v$ has been
contracted. We set $a\prec^{\textup{ml}}b$ whenever
$\varphi(a)\prec^{\textup{top}}\varphi(b)$ holds. It is easy to see that
$\prec^{\textup{ml}}$ is a weak ordering on $V$.

To see that $\prec^{\textup{ml}}$ is a master list for $\mathcal{I}$, let $a$
and $b$ be two distinct vertices in $V$. First note that $a\sim_{v}b$ for some
$v\in V$ immediately implies $a\sim^{\textup{ml}}b$. Second, if $a\prec_{v}b$
for some $v\in V$, then we already know $a\not\sim^{\textup{ml}}b$, yielding
$\varphi(a)\neq\varphi(b)$. Therefore, $D^{\prime}$ contains an arc from
$\varphi(a)$ to $\varphi(b)$, yielding
$\varphi(a)\prec^{\textup{top}}\varphi(b)$ and hence $a\prec^{\textup{ml}}b$.

###  3.2 Measuring the distance from $\mathcal{F}_{\textup{ML}}$

Let us now define our three measures to describe the distance of a given
strict preference system $\mathcal{I}=(G,\prec)$ from the family
$\mathcal{F}_{\textup{ML}}$ of preference systems that admit a master list:

  * •

$\Delta^{\textup{swap}}(\mathcal{I})=\min\\{|S|:S$ is a set of swaps in
$\mathcal{I}$ such that $\mathcal{I}\lhd S\in\mathcal{F}_{\textup{ML}}\\}$;

  * •

$\Delta^{\textup{edge}}(\mathcal{I})=\min\\{|S|:S\subseteq
E(G),\mathcal{I}-S\in\mathcal{F}_{\textup{ML}}\\}$;

  * •

$\Delta^{\textup{vert}}(\mathcal{I})=\min\\{|S|:S\subseteq
V(G),\mathcal{I}-S\in\mathcal{F}_{\textup{ML}}\\}$.

The measures $\Delta^{\textup{edge}}(\mathcal{I})$ and
$\Delta^{\textup{vert}}(\mathcal{I})$ can be easily extended for preference
systems that are not necessarily strict, since the above definitions are well-
defined for any preference system $(G,\preceq)$.

Extending the measure $\Delta^{\textup{swap}}(\mathcal{I})$ for non-strict
preference systems is, however, not entirely straightforward. If there are
ties in the preferences of some vertex $v$, how can we define an admissible
swap? In this paper we use the following definition for swap distance, which
seems to be standard in the literature [7, 10]. Let $\preceq_{u}$ and
$\preceq_{v}$ be weak orders. If they are not defined over the same sets, then
the _swap distance_ of $\preceq_{u}$ and $\preceq_{v}$, denoted by
$\Delta(\preceq_{u},\preceq_{v})$ is $\infty$, otherwise

$\Delta(\preceq_{u},\preceq_{v})=|\\{\\{a,b\\}:a\prec_{u}b\textrm{ but
}b\preceq_{v}a\\}|+|\\{\\{a,b\\}:a\sim_{u}b\textrm{ but }a\not\sim_{v}b\\}|.$

For two preferences systems $\mathcal{I}=(G,\preceq)$ and
$\mathcal{I}^{\prime}=(G^{\prime},\preceq^{\prime})$ with $G=(V,E)$ and
$G^{\prime}=(V^{\prime},E^{\prime})$, we let their swap distance, denoted by
$\Delta(\mathcal{I},\mathcal{I}^{\prime})$, be $\infty$ if they are not
defined over the same vertex set; otherwise (that is, if $V=V^{\prime}$) we
let $\Delta(\mathcal{I},\mathcal{I}^{\prime})=\sum_{v\in
V}\Delta(\preceq_{v},\preceq^{\prime}_{v})$. Using this, we can define

$\Delta^{\textup{swap}}(\mathcal{I})=\min\left\\{\Delta(\mathcal{I},\mathcal{I}^{\prime}):\mathcal{I}^{\prime}\in\mathcal{F}_{\textup{ML}}\right\\}.$

The following lemma follows easily from the definitions.

######  Lemma 3.3.

$\Delta^{\textup{swap}}(\mathcal{I})\geq\Delta^{\textup{edge}}(\mathcal{I})\geq\Delta^{\textup{vert}}(\mathcal{I})$
for any preference system $\mathcal{I}$.

###### Proof.

Suppose that $\Delta^{\textup{swap}}(\mathcal{I})=k$, meaning that $\sum_{v\in
V}\Delta(\preceq_{v},\preceq^{\prime}_{v})\leq k$ for some instance
$\mathcal{I}^{\prime}=(G,\preceq^{\prime})\in\mathcal{F}_{\textup{ML}}$. Let
$U$ be the family containing all pairs of the form $(\\{a,b\\},v)$ for which
$a\prec_{v}b$ but $b\preceq^{\prime}_{v}a$, or $a\sim_{v}b$ but
$a\not\sim^{\prime}_{v}b$. By definition, $|U|=\sum_{v\in
V}\Delta(\preceq_{v},\preceq^{\prime}_{v})\leq k$. Note that for each
$(\\{a,b\\},v)\in U$, deleting the edge $e=\\{a,v\\}$ from $G$ decreases the
distance of $\mathcal{I}$ from $\mathcal{I}^{\prime}$, that is,
$\Delta(\mathcal{I}-e,\mathcal{I}^{\prime}-e)\leq k-1$ (clearly, the same
holds for the edge $\\{b,v\\}$ as well). Repeating this for each pair in $U$,
we can delete a set $S$ of at most $k$ edges from $G$ so that
$\Delta(\mathcal{I}-S,\mathcal{I}^{\prime}-S)=0$. Since
$\mathcal{F}_{\textup{ML}}$ is closed under edge deletions, we know
$\mathcal{I}^{\prime}-S\in\mathcal{F}_{\textup{ML}}$, implying
$\Delta^{\textup{edge}}(\mathcal{I})\leq|S|\leq k$.

Proving the remaining statement of the lemma is easier: instead of deleting
$k=\Delta^{\textup{edge}}(\mathcal{I})$ edges to obtain an instance
$\mathcal{I}^{\prime}\in\mathcal{F}_{\textup{ML}}$, we can simply delete a set
of at most $k$ vertices covering these edges in $G$ to get a sub-instance of
$\mathcal{I}^{\prime}$. This shows
$\Delta^{\textup{vert}}(\mathcal{I})\leq\Delta^{\textup{edge}}(\mathcal{I})$.

Let Master List by Swaps (or MLS for short) be the problem whose input is a
preference system $\mathcal{I}$ and an integer $k$, and the task is to decide
whether $\Delta^{\textup{swap}}(\mathcal{I})\leq k$. Assuming that
$\mathcal{I}$ is a strict preference system, a set $S$ of at most $k$ swaps
whose application in $\mathcal{I}$ yields an instance admitting a master list
is called a _solution_ for the instance $(\mathcal{I},k)$ of MLS. We define
the Master List by Edge Deletion (or MLED) and the Master List by Vertex
Deletion (or MLVD) problems and their solution concepts analogously.

####  3.2.1 MLS versus the Kemeny Score problem.

We note that the MLS problem for a strict preference system $(G,\prec)$ on a
graph $G=(V,E)$ can be reformulated as an instance of the Kemeny Score problem
where votes are allowed to be incomplete, by setting $V$ as the candidate set
and interpreting each $\prec_{v}$, $v\in V$, as a vote containing only the
candidates $N_{G}(v)$; we refer to Betzler et al. [3] for a precise definition
of this variant of Kemeny Score. Note that even if $G$ is a complete graph,
$N_{G}(v)$ excludes $v$, and thus MLS differs from the classic form of the
Kemeny Score problem where each vote is a ranking over the whole candidate
set. We further remark that, when considering weak orders, MLS and Kemeny
Score significantly differ in the way they treat ties [27, 3]. We will comment
in more detail on the connection between our findings for MLS and the known
results for Kemeny Score in Section 4.1.

##  4 Computing the distance from admitting a master list

Let us now present our main results on recognizing when a given preference
list is close to admitting a master list. We investigate the classical and
parameterized complexity of the problem of determining each of the three
distance measures defined in Section 2 for a given preference system, that is,
the problems MLS, MLED, and MLVD. In Section 4.1 we consider strict preference
systems, and then extend our results for weakly ordered preferences in Section
4.2.

###  4.1 Strict preferences

We are going to show that computing the distance from
$\mathcal{F}_{\textup{ML}}$ is computationally hard for each of our three
distance measures. In particular, Theorem 4.1 presents a reduction from
Feedback Arc Set to MLS and also to MLED, and Theorem 4.5 provides a reduction
from the Hitting Set problem to MLVD. Although both of these classic problems
are $\mathsf{NP}$-hard, their approximability and their parameterized
complexity for the standard parameterization—where the parameter is the
desired value for the objective function—differs considerably, suggesting that
the problem of computing the three distance measures may behave differently
when viewed from the perspective of approximation or of parameterized
complexity. Indeed, intrinsic differences between our three problems under
examination will surface when we consider their computational complexity in
finer detail.

We start with Theorem 4.1 showing that we cannot expect a polynomial-time
algorithm for MLS or for MLED and even a polynomial-time approximation is
unlikely to exist already for bipartite graphs. As already mentioned, the
proof of Theorem 4.1 relies on a connection between MLS, MLED, and the
Feedback Arc Set problem which, given a directed graph $D$ and an integer $k$,
asks whether there exists a set of at most $k$ arcs in $D$ whose deletion from
$D$ yields an acyclic graph. Interestingly, the connection of this problem to
MLS and to MLED can be used both ways: on the one hand, it serves as the basis
of our reduction for proving computational hardness, and on the other hand, we
will be able to apply already existing algorithms for Feedback Arc Set in our
quest for solving MLS and MLED.

######  Theorem 4.1.

MLS and MLED are both $\mathsf{NP}$-hard, and assuming the Unique Games
Conjecture they are $\mathsf{NP}$-hard to approximate by any constant factor
in polynomial time. All of these hold even if the input graph is bipartite
with all vertices on one side having degree 2, and preferences are strict.

###### Proof.

We give a reduction from the $\mathsf{NP}$-hard Feedback Arc Set problem that
proves the theorem for both MLS and MLED. Let digraph $D=(V,E)$ and an integer
$k$ be the input of Feedback Arc Set.

Given $D$, we create the following bipartite preference system
$\mathcal{I}=(G,\prec)$. For each arc $e=(a,b)\in E$, we create a dummy vertex
$z_{e}$ whose neighbors are $a$ and $b$, and we set $a\prec_{z_{e}}b$. We set
$V\cup Z$ as the set of vertices in $G$ where $Z=\\{z_{e}:e\in E\\}$. To
define the preferences of agents in $V$, we fix an arbitrary strict ordering
$\prec^{Z}$ over the set $Z$ of dummy vertices, and let $\prec_{v}$ be the
restriction of $\prec^{Z}$ to $N_{G}(v)$ for each $v\in V$. Note that $G$ can
be obtained from the undirected version of $D$ by subdividing every edge, and
therefore $G$ is bipartite. Moreover, the preference digraph $D_{\mathcal{I}}$
of $\mathcal{I}$ is the disjoint union of $D_{\mathcal{I}}[Z]$, which is
acyclic, and $D_{\mathcal{I}}[V]$, which is exactly the digraph $D$, with each
arc $(a,b)$ labelled by $z_{(a,b)}$.

We claim that the following three statements are equivalent:

  * (1)

$\Delta^{\textup{swap}}(\mathcal{I})\leq k$;

  * (2)

$\Delta^{\textup{edge}}(\mathcal{I})\leq k$;

  * (3)

there exists a feedback arc set of size at most $k$ in $D$.

First note that (1) $\Rightarrow$ (2) is implied by Lemma 3.3.

To prove (2) $\Rightarrow$ (3), suppose that $S$ is a set of at most $k$ edges
in $G$ such that $\mathcal{I}-S$ admits a master list $\prec^{\textup{ml}}$.
Recall that $|N_{G}(z)|=2$ for each $z\in Z$ and $E(G)\subseteq Z\times V$.
Define an arc set $F_{S}=\\{e\in E:z_{e}\textrm{ is incident to some edge in
}S\\}$; notice that $|F_{S}|\leq|S|\leq k$. Then $F$ is a feedback arc set,
since the restriction of $\prec^{\textup{ml}}$ on $V$ is a topological order
for $V$ in $D-F_{S}$. Indeed, if $e=(a,b)\in E\setminus F_{S}$ then
$(z_{e},a),(z_{e},b)$ are both present in $\mathcal{I}-S$, implying that
$a\prec_{z_{e}}b$ is consistent with the master list in $\mathcal{I}-S$, that
is, $a\prec^{\textup{ml}}b$.

To prove (3) $\Rightarrow$ (1), suppose that $F$ is a feedback arc set of size
at most $k$ in $D$. W.l.o.g. we may assume that $F$ is inclusion-minimal, and
thus reversing each arc of $F$ in $D$ results in an acyclic digraph
$D_{\overleftarrow{F}}$. Accordingly, let us “reverse” the preferences of the
agents corresponding to edges in $F$, that is, let $S$ be the set of swaps
that switches $a$ and $b$ for each $e=(a,b)\in F$ in the preferences of
$z_{e}$. Note that swapping $a$ and $b$ in the preferences if $z_{\\{a,b\\}}$
is admissible, since $N_{G}(z_{e})=\\{a,b\\}$, and it is equivalent to
reversing the arc $(a,b)$ in the preference digraph. Thus we obtain that the
preference digraph of the instance $\mathcal{I}\lhd S$ is acyclic, as it is
the disjoint union of $D_{\mathcal{I}}[Z]$ and the digraph
$D_{\overleftarrow{F}}$. This means that $\mathcal{I}\lhd
S\in\mathcal{F}_{\textup{ML}}$ by Observation 3.1, implying
$\Delta^{\textup{swap}}(\mathcal{I})\leq|S|\leq k$.

Hence, our claim holds and the reduction is correct, showing
$\mathsf{NP}$-hardness for both MLS and MLED.

To show our inapproximability result, let $f(D)$ denote the instance
$\mathcal{I}$ created in the above reduction ($\mathcal{I}$ is an instance of
MLS as well as one of MLED). The above arguments prove that an optimal
solution for $f(D)=\mathcal{I}$ has the same size as a feedback arc set for
$D$ of minimum size. Moreover, for any set $S$ of edges in $G$ that is a
solution for our MLED instance $\mathcal{I}$, the arc set $F_{S}$ is a
feedback arc set in $D$ with $|F_{S}|\leq|S|$, so setting $g(S)=F_{S}$ yields
that the pair $(f,g)$ is an approximation preserving reduction from Feedback
Arc Set to MLED. Similarly, for any set $S^{\prime}$ of swaps in $\mathcal{I}$
that is a solution for our MLS instance $\mathcal{I}$, using the arguments of
Lemma 3.3 we can compute a set $h(S^{\prime})$ of at most $|S^{\prime}|$ edges
in $G$ for which $\mathcal{I}-h(S^{\prime})\in\mathcal{F}_{\textup{ML}}$, so
setting $g^{\prime}(S^{\prime})=F_{h(S^{\prime})}$ yields that
$(f,g^{\prime})$ is an approximation preserving reduction from Feedback Arc
Set to MLS. By the results of Guruswami [24], we know that no polynomial-time
algorithm can obtain a constant-factor approximation for Feedback Arc Set
unless the Unique Games Conjecture fails, ruling out a polynomial-time
constant-factor approximation algorithm both for MLS and for MLED under the
same assumption.

Thanks to Lemma 1 below, for any strict preference system $\mathcal{I}$ we can
decide whether $\Delta^{\textup{swap}}(\mathcal{I})\leq k$ for some
$k\in\mathbb{N}$ by applying the FPT algorithm of Lokshtanov et al. [36] for
Feedback Arc Set on the preference digraph $D_{\mathcal{I}}$ and parameter
$k$. Their algorithm runs in time $O(k!4^{k}k^{6}(n+m))$ on an input graph
with $n$ vertices and $m$ arcs [36]. If $G=(V,E)$ is the graph underlying
$\mathcal{I}$, then $D_{\mathcal{I}}$ has $|V|$ vertices and
$O(|V|\\!\cdot\\!|E|)$ arcs, implying a running time of
$O(k!4^{k}k^{6}|V|\\!\cdot\\!|E|)$.

######  Lemma 1.

For a strict preference system $\mathcal{I}$,
$\Delta^{\textup{swap}}(\mathcal{I})\leq k$ if and only if the preference
digraph of $\mathcal{I}$ admits a feedback arc set of size at most $k$.

###### Proof.

Let $\mathcal{I}=(G,\prec)$ be a strict preference system with $G=(V,E)$ as
its underlying graph, and let $D_{\mathcal{I}}$ be the preference digraph of
$\mathcal{I}$. Observe that performing a swap that is admissible in the
preferences of some vertex $v\in V$ corresponds to reversing an arc in
$D_{\mathcal{I}}$ with label $v$. Hence, a set $S$ of swaps such that
$\mathcal{I}\lhd S\in\mathcal{F}_{\textup{ML}}$ directly yields a feedback arc
set of size $|S|$ for the preference digraph $D_{\mathcal{I}}$.

To see the other direction, we need to show that a feedback arc set $F$ for
$D_{\mathcal{I}}$ can be turned into a set $S$ of admissible swaps in
$\mathcal{I}$ with $|S|\leq|F|$. We can assume w.l.o.g. that $F$ is inclusion-
minimal. Given $F$, we iteratively find an arc $f=(a,b)\in F$ with label $v$
such that $(a,b)$ is an admissible swap in $v$’s preferences, and then proceed
with the instance $\mathcal{I}^{\prime}$ resulting from
$\mathcal{I}\lhd(a,b;v)$ and the set $F\setminus\\{f\\}$ which is a feedback
arc set for the preference digraph of $\mathcal{I}\lhd(a,b;v)$.

It remains to show that we can always find a suitable arc $f=(a,b)\in F$ with
label $v$ such that $(a,b)$ is an admissible swap in $v$’s preferences.
Suppose otherwise, and let $(a,b)\in F$ with label $v$ be such that the
distance between $a$ and $b$ in $v$’s preferences is as small as possible. As
$(a,b;v)$ is not a suitable swap in $\mathcal{I}$, there exists a vertex $c$
between $a$ and $b$ in $v$’s preferences. This yields a path $P=(a,c,b)$ in
$D_{\mathcal{I}}$ with both of its arcs having label $v$. Since $F$ is
inclusion-minimal, $P$ cannot be a path in $D_{\mathcal{I}}-F$, and so at
least one of its arcs is in $F$, contradicting our choice of $f$.

######  Corollary 4.2.

If preferences are strict, then MLS is fixed-parameter tractable with
parameter $k$, and can be solved in time
$O(k!4^{k}k^{6}|V|\\!\\!\cdot\\!\\!|E|)$.

We remark that the connection between Kemeny Score and Feedback Arc Set has
already been noted by Bartholdi III et al. [2] who proved its
$\mathsf{NP}$-completeness. The variant of Kemeny Score with incomplete votes
was investigated by Betzler et al. [3]; they proved its fixed-parameter
tractability when parameterized by the desired value of the Kemeny score. This
already implies that MLS is fixed-parameter tractable with parameter $k$,
although the running time we obtain in Corollary 4.2 is better than the one
stated in [3, Theorem 10], mainly due to the improvement by Lokshtanov et al.
[35] over the original FPT algorithm for Feedback Arc Set by Chen et al. [9].

In contrast to MLS, the MLED problem is $\mathsf{W}[1]$-hard with $k$ as the
parameter; the reduction is from Multicolored Clique [18].

######  Theorem 4.3.

MLED is $\mathsf{W}[1]$-hard with parameter $k$, even for strict preferences.

###### Proof.

We are going to present a reduction from the $\mathsf{W}[1]$-hard Multicolored
Clique problem [18], where the input is an undirected graph $G$ and a
parameter $k$ with the vertex set of $G$ partitioned into $k$ independent sets
$V^{1},\dots,V^{k}$, and the task is to find a clique of size $k$ in $G$.
Clearly, such a clique must contain one vertex from each set $V^{i}$,
$i\in[k]$. Let us denote by $v^{i}_{1},v^{i}_{2},\dots,v^{i}_{|V^{i}|}$ the
vertices in $V^{i}$. We are going to construct a preference system
$\mathcal{I}=(G^{\prime},\prec)$ and an integer $k^{\prime}$ such that $G$
contains a clique of size $k$ if and only if there exists a set $S$ of at most
$k^{\prime}$ edges in $G^{\prime}$ such that
$\mathcal{I}-S\in\mathcal{F}_{\textup{ML}}$.

Instead of defining $G^{\prime}$ directly, we are going to define a digraph
$D$ that will be the preference digraph of $\mathcal{I}$. Furthermore, we will
explicitly label only a subset of the arcs in $D$, and declare the remaining
arcs as _fixed_ , meaning that they represent a set $k^{\prime}+1$ parallel
arcs, each labelled by distinct dummy vertices. First, we create a set
$\\{a_{e},a^{\prime}_{e},b_{e},b^{\prime}_{e}:e\in E(G)\\}$ and a set
$\\{v,v^{\prime}:v\in V(G)\\}$ of vertices. Next, for each $i\in[k]$ and each
$v\in V^{i}$ we create a gadget $D_{v}$ as follows. For each
$j\in[k]\setminus\\{i\\}$, let $E^{j}(v)$ denote the set of edges in $G$ that
connect $v$ with some vertex in $V^{j}$, and let $n_{v}^{j}=|E^{j}(v)|$. Let
us create a bijection $\sigma_{v}^{j}:[n_{v}^{j}]\rightarrow E^{j}(v)$. The
gadget $D_{v}$ will contain $v$ as a source and $v^{\prime}$ as a sink, and we
define $k-1$ arc-disjoint paths from $v$ to $v^{\prime}$: for each $1\leq j<i$
we add the path

$P_{v}^{j}=(v,a_{\sigma_{v}^{j}(1)},a^{\prime}_{\sigma_{v}^{j}(1)},a_{\sigma_{v}^{j}(2)},a^{\prime}_{\sigma_{v}^{j}(2)},\dots,a_{\sigma_{v}^{j}(n_{v}^{j})},a^{\prime}_{\sigma_{v}^{j}(n_{v}^{j})},v^{\prime}),$

and for each $i<j\leq k$ we add the path

$P_{v}^{j}=(v,b_{\sigma_{v}^{j}(1)},b^{\prime}_{\sigma_{v}^{j}(1)},b_{\sigma_{v}^{j}(2)},b^{\prime}_{\sigma_{v}^{j}(2)},\dots,b_{\sigma_{v}^{j}(n_{v}^{j})},b^{\prime}_{\sigma_{v}^{j}(n_{v}^{j})},v^{\prime}).$

If $E^{j}(v)=\emptyset$, then the corresponding path from $v$ to $v^{\prime}$
consist solely of the arc $(v,v^{\prime})$. For each arc
$(a_{e},a^{\prime}_{e})$ appearing in $D_{v}$ we add $b_{e}$ as its label, and
conversely, for each arc $(b_{e},b^{\prime}_{e})$ appearing in $D_{v}$ we add
$a_{e}$ as its label; we declare all remaining arcs in $D$ as fixed.

Next, for each $i\in[k]$, we chain the gadgets corresponding to vertices of
$V^{i}$ into a cycle by adding an arc
$((v^{i}_{\ell})^{\prime},v^{i}_{\ell+1})$ for each $\ell\in[|V^{i}|]$, where
we define $v^{i}_{|V^{i}|+1}:=v^{i}_{1}$. We declare each of these arcs as
fixed. Let $D^{i}$ denote the directed graph created thus far on the vertices
$\\{V(D_{v}):v\in V^{i}\\}$; note that for any two indices $i\neq j$, the
digraphs $D^{i}$ and $D^{j}$ are vertex-disjoint, and there are no arcs
running between them. Observe also that every cycle in $D^{i}$ traverses all
vertices $\\{v,v^{\prime}:v\in V^{i}\\}$, using some path $P_{v}^{j}$ for each
$v\in V^{i}$ to get from $v$ to $v^{\prime}$. We let the union of
$D^{1},\dots,D^{k}$ be the subgraph of $D$ induced by all non-dummy vertices.

To finish the construction of $D$, it remains to take care of dummy vertices
(recall that by definition, $V(D)=V(G^{\prime})$). Let $Z$ be the set of dummy
vertices introduced while creating the fixed arcs, and let $\prec^{Z}$ be an
arbitrary ordering on $Z$. Note that each dummy $z\in Z$ is used only once,
when creating some fixed arc $e_{z}$ in $D$ (meaning that $z$ is the label of
one of the $k^{\prime}+1$ parallel arcs which together constitute the fixed
arc $e_{z}$), so $N_{G^{\prime}}(z)$ is the set of endpoints of $e_{z}$. We
then define the preferences of all non-dummy vertices so that they prefer non-
dummy vertices to dummies, and their preferences between dummies are derived
from $\prec^{Z}$. Observe that our instance $\mathcal{I}=(G^{\prime},\prec)$
and its preference digraph $D$ are now well-defined. Finally, we set
$k^{\prime}=\binom{k}{2}$.

We claim that $G$ admits a clique of size $k$ if and only if there exists a
set $S$ of at most $k^{\prime}$ edges in $G^{\prime}$ such that
$\mathcal{I}-S\in\mathcal{F}_{\textup{ML}}$.

First assume that the vertices $x_{1},\dots,x_{k}$ form a clique in $G$. We
define a corresponding set $S=\\{\\{a_{e},b_{e}\\}:e=\\{x_{i},x_{j}\\}\textrm{
for some }1\leq i<j\leq k\\}$. Notice that deleting an edge
$\\{a_{e},b_{e}\\}$ from $\mathcal{I}$ corresponds to deleting two arcs from
the preference subgraph $D$, namely the arc $(a_{e},a^{\prime}_{e})$ labelled
with $b_{e}$ and the arc $(b_{e},b^{\prime}_{e})$ labelled with $a_{e}$.
Hence, the deletion of $S$ removes an arc from each of the paths
$P_{x_{i}}^{j}$ with $1\leq i<j\leq k$, which ensures for each $i\in[k]$ that
there is no path from $x_{i}$ to $x^{\prime}_{i}$. Hence, the preference
digraph of $\mathcal{I}-S$ is indeed acyclic, and thus
$\mathcal{I}-S\in\mathcal{F}_{\textup{ML}}$ by Observation 3.1.

Assume now that there exists a set $S\subseteq E(G^{\prime})$ with $|S|\leq
k^{\prime}$ such that $\mathcal{I}-S\in\mathcal{F}_{\textup{ML}}$. Notice that
fixed arcs in $D$ are also present as arcs in the preference digraph $D_{S}$
of $\mathcal{I}-S$, by our bound $|S|\leq k^{\prime}$. Also, for each
$i\in[k]$ there must exist some $x_{i}\in V^{i}$ for which there is no path in
$D_{S}$ from $x_{i}$ to $x^{\prime}_{i}$, as otherwise these paths together
with the fixed arcs between gadgets form a cycle. Inspecting the gadget
$D_{x_{i}}$, it is clear that the deletion of $S$ must remove at least one arc
on the path $P_{x_{i}}^{j}$ for each $j\in[k]\setminus\\{i\\}$, which can be
achieved by deleting some edge of $G^{\prime}$ incident to $a_{e}$ or to
$b_{e}$ for some $e\in E^{j}(x_{i})$. This means that we have to remove at
least $k-1$ arcs from each $D^{i}$, a total of at least $k(k-1)=2k^{\prime}$
arcs. This can only be achieved by the deletion of $|S|\leq k^{\prime}$ edges,
if the deletion of each edge in $S$ from $G^{\prime}$ results in the removal
of exactly two arcs (as no edge deletion can remove more than $2$ arcs from
the preference digraph labelled by non-dummy vertices), and hence cannot
involve any vertices of the form $a^{\prime}_{e}$ or $b^{\prime}_{e}$.
Therefore, $S$ must contain a set of $\binom{k}{2}$ edges of the form
$\\{a_{e},b_{e}\\}$ whose deletion from $G^{\prime}$ results in the removal of
an arc from each of the paths $P^{j}_{x_{i}}$ for each $1\leq i<j\leq k$. This
is only possible if $S$ consists of the edge set of a clique consisting of the
vertices $x_{1},\dots,x_{k}$.

Although Theorem 4.3 provides strong evidence that there is no FPT algorithm
for MLED with parameter $k$, and by Theorem 4.1 we cannot hope for a
polynomial-time approximation algorithm for MLED either, our next result shows
that combining these two approaches yields a way to deal with the
computational hardness of the problem. Namely, Theorem 4.4 provides a
2-approximation for MLED whose running time is FPT with parameter $k$. This
result again relies heavily on the connection between MLED and Feedback Arc
Set.

######  Theorem 4.4.

There exists an algorithm that achieves a 2-approximation for MLED if
preferences are strict, and runs in FPT time with parameter $k$.

2-approximation FPT algorithm for MLED (strict preferences). Let the strict
preference system $\mathcal{I}=(G,\prec)$ with underlying graph $G=(V,E)$ and
$k\in\mathbb{N}$ be our input for MLED. See Algorithm 1 for a formal
description.

First, we construct a directed graph $H_{\mathcal{I}}$ by setting

$\displaystyle V(H_{\mathcal{I}})$ $\displaystyle=$ $\displaystyle
V\cup\\{a_{v}^{-},a_{v}^{+}:\\{a,v\\}\in E\\},$ $\displaystyle
A(H_{\mathcal{I}})$ $\displaystyle=$
$\displaystyle\\{(a_{c}^{+},b_{c}^{-}):a,b,c\in
V,a\prec_{c}b\\}\cup\,\\{(a_{v}^{-},a),(a,a_{v}^{+}):v\in V,a\in N_{G}(v)\\}.$

Next, we compute a minimum feedback arc set $F$ in $H_{\mathcal{I}}$ using the
algorithm by Lokshtanov et al. [36]. Notice that w.l.o.g. we may assume that
$F$ only contains arcs incident to some vertex in $V$, as we can replace any
arc $(a_{c}^{+},b_{c}^{-})$ with the sole arc leaving $b_{c}^{-}$, namely
$(b_{c}^{-},b)$, since all cycles containing $(a_{c}^{+},b_{c}^{-})$ must also
go through $(b_{c}^{-},b)$.

Finally, we return the set $S_{F}=\\{\\{a,v\\}\in E:(a,a_{v}^{+})\in F\textrm{
or }(a_{v}^{-},a)\in F\\}$.

Algorithm 1 Obtaining a 2-approximation for MLED on input $(\mathcal{I},k)$
with strict preferences

1:Construct the graph $H_{\mathcal{I}}$.

2:Let $F$ be a solution for Feedback Arc Set on input $(H_{\mathcal{I}},k)$.

3:Ensure that each arc in $F$ is incident to some vertex in $V$ by replacing
all arcs of $F$ entering some $a_{v}^{-}$ with $(a_{v}^{-},a)$.

4:Return $S_{F}=\\{\\{a,v\\}\in E:(a,a_{v}^{+})\in F\textrm{ or
}(a_{v}^{-},a)\in F\\}$.

###### of Theorem 4.4.

We prove that Algorithm 1 gives a 2-approximation, that is, if there exists a
set $S$ of at most $k$ edges in $G$ such that $\mathcal{I}-S$ admits a master
list $\prec^{\textup{ml}}$, then Algorithm 1 returns a solution for
$\mathcal{I}$ of size at most $2|S|\leq 2k$.

For a given instance $\mathcal{I}=(G,\prec)$, consider the directed graph
$H_{\mathcal{I}}$ constructed by the algorithm. Observe first that contracting
for each $v\in V$ the subgraph of $H_{\mathcal{I}}$ induced by
$\\{v\\}\cup\\{v_{a}^{+},v_{a}^{-}:a\in N_{G}(v)\\}$ in $H_{\mathcal{I}}$
yields exactly the preference digraph of $\mathcal{I}$ (without the arc-
labelling). Furthermore, $H_{\mathcal{I}}$ is acyclic if and only if the
preference subgraph of $\mathcal{I}$ is acyclic.

Take any vertex $a\in V$ incident to some edge in $S$; let
$\\{a,b_{1}\\},\dots,\\{a,b_{t}\\}$ be the edges of $S$ incident to $a$.
Instead of deleting these edges, it is also possible to “move” the vertices in
$B=\\{b_{1},\dots,b_{t}\\}$ within the preferences of $a$ to obtain an
instance $\mathcal{I}^{\prime}$ whose preferences are consistent with
$\prec^{\textup{ml}}$: when representing $a$’s preferences as a list, each
$b\in B$ needs to be moved either to the left (becoming more preferred by $a$)
or to the right (becoming less preferred by $a$). In the former case we mark
the arc $(b,b_{a}^{+})$, and in the latter case we mark $(b_{a}^{-},b)$.
Clearly, we have marked at most $2|S|\leq 2k$ arcs in $H_{\mathcal{I}}$, since
for each edge $\\{a,b\\}\in S$ we may need to move $a$ in $b$’s preferences,
and also to move $b$ in $a$’s preferences, and each such move results in
marking one arc.

We claim that the set $M$ of marked arcs is a feedback arc set in
$H_{\mathcal{I}}$. Suppose for contradiction that there is a cycle $C$ in
$H_{\mathcal{I}}-M$. Observe that $C$ can be decomposed into paths of length 3
of the form $(a,a_{c}^{+},b_{c}^{-},b)$. For such a path it follows that
$a\prec^{\textup{ml}}_{c}b$ holds: first, $a\prec_{c}b$ holds in $G$ by
construction, and we have not moved $a$ up in $c$’s preferences (by
$(a,a_{c}^{+})\notin M$), nor have we moved $b$ down in $c$’s preferences (by
$(b_{c}^{-},b)\notin M$), so $c$ still prefers $b$ to $a$ in the instance
$\mathcal{I}^{\prime}$ whose preferences are consistent with
$\prec^{\textup{ml}}$. Therefore, the cycle $C$ implies a cycle in the
preference digraph of $\mathcal{I}-S$, a contradiction. Thus, $M$ is a
feedback arc set of size at most $2k$.

This implies that Algorithm 1 will produce a feedback arc set $F$ for
$H_{\mathcal{I}}$ of size at most $2k$ on line 2. It remains to show that the
set $S_{F}$ is indeed a solution for our instance $\mathcal{I}$ of MLED.
Consider the changes in the digraph $H_{\mathcal{I}}$ as a result of deleting
the edges of $S_{F}$ from $\mathcal{I}$. Note that the deletion of $S_{F}$
from $\mathcal{I}$ ensures the removal of all arcs in $F$ from
$H_{\mathcal{I}}$ (since deleting an edge $\\{a,b\\}$ from $G$ corresponds to
removing the vertices $a_{b}^{+},a_{b}^{-},b_{a}^{+},$ and $b_{a}^{-}$ and all
arcs incident to them from $H_{\mathcal{I}}$), so the resulting digraph
$H_{\mathcal{I}-S_{F}}$ is acyclic. Recall that $H_{\mathcal{I}-S_{F}}$ is
acyclic if and only if the preference digraph of $\mathcal{I}-S_{F}$ is
acyclic. Thus by Observation 3.1 we get
$\mathcal{I}-S_{F}\in\mathcal{F}_{\textup{ML}}$. This proves that Algorithm 1
yields a 2-approximation.

Note that $H_{\mathcal{I}}$ has $|V|+2|E|$ vertices and at most
$|V|\\!\\!\cdot\\!\\!|E|+4|E|$ arcs. The total running time of Algorithm 1 is
therefore $O(k!4^{k}k^{6}|V|\\!\\!\cdot\\!\\!|E|)$ which is indeed FPT with
parameter $k$.

Contrasting our positive results for MLS and MLED, a reduction from the
classic Hitting Set problem [30] shows that MLVD is computationally hard both
in the classic and in the parameterized sense, and cannot be approximated by
any FPT algorithm, as stated by Theorem 4.5.

######  Theorem 4.5.

MLVD is $\mathsf{NP}$-hard and $\mathsf{W}[2]$-hard with parameter $k$.
Furthermore, no FPT algorithm with $k$ as the parameter can achieve an
$f(k)$-approximation for MLVD for any computable function $f$, unless
$\mathsf{FPT}=\mathsf{W}[1]$. All of these hold even if the input graph is
bipartite and preferences are strict.

###### Proof.

We present a reduction from the Hitting Set problem. The input of Hitting Set
is a set $U$ (the _universe_), a family $S_{1},\dots,S_{m}$ of subsets of $U$,
and an integer $k$; the task is to find a hitting set of size at most $k$,
where a _hitting set_ is a set $H\subseteq U$ such that $H\cap
S_{i}\neq\emptyset$ for each $i\in[m]$.

Given an instance $\mathcal{H}=(U,S_{1},\dots,S_{m},k)$, let $u(S_{i},j)$ be
the $j$-th item in $S_{i}$ for each $j\in[|S_{i}|]$. We construct a bipartite
preference system $\mathcal{I}=(G,\prec)$ as follows. For each $i\in[m]$ and
$j\in[|S_{i}|]$, we create an agent $x_{S_{i}}^{j}$. The vertex set of $G$ is
$V=X\cup U$ where $X=\\{x_{S_{i}}^{j}:i\in[m],j\in[|S_{i}|]\\}$, and we define
the edge set of $G$ by connecting $u(S_{i},j)$ for each $i\in[m]$ and
$j\in[|S_{i}|]$ to both $x_{S_{i}}^{j}$ and $x_{S_{i}}^{j+1}$ (where we define
$x_{S_{i}}^{|S_{i}|+1}=x_{S_{i}}^{1}$ for each $i$); we set also
$x_{S_{i}}^{j}\prec_{u(S_{i},j)}x_{S_{i}}^{j+1}$. Note that $G$ is bipartite.
To define the full preferences of agents in $U$, we further add that for any
agent $u\in U$ whose neighborhood contains some agents $x_{S_{i}}^{j}$ and
$x_{S_{i^{\prime}}}^{j^{\prime}}$ with $i\neq i^{\prime}$, we let
$x_{S_{i}}^{j}\prec_{u}x_{S_{i^{\prime}}}^{j^{\prime}}$ exactly if
$i<i^{\prime}$. To finish the definition of the preferences in $\mathcal{I}$,
we fix an arbitrary strict ordering $\prec^{U}$ over the universe $U$ as a
master list over $U$, i.e., for any $x\in X$ we set $u\prec_{x}u^{\prime}$ for
some $u$ and $u^{\prime}$ in $U$ if and only if $u\prec^{U}u^{\prime}$.

We claim that there exists a hitting set of size at most $k$ for $\mathcal{H}$
if and only if $\Delta^{\textup{vert}}(\mathcal{I})\leq k$.

Suppose first that $S$ is a set of at most $k$ vertices in $G$ such that
$\mathcal{I}-S$ admits a master list $\prec^{\textup{ml}}$. Let $H_{S}$ be the
union of $S\cap U$ and $\\{u(S_{i},j):x_{S_{i}}^{j}\in X\cap S\\}$. Note that
$|H_{S}|\leq|S|\leq k$; we show that $H_{S}$ is a hitting set for
$\mathcal{H}$. To see this, suppose that a set $S_{i}$ for some $i\in[m]$ is
not hit by $H_{S}$, that is, $S_{i}\cap H_{S}=\emptyset$. Then by definition,
$S_{i}\cup\\{x_{S_{i}}^{j}:j\in[|S_{i}|]\\}$ is disjoint from $S$. We show
that the sub-instance of $\mathcal{I}-S$ consisting of these $2|S_{i}|$
vertices cannot be consistent with the master list $\prec^{\textup{ml}}$: if
there exists some $\ell\in[|S_{i}|-1]$ for which
$x_{S_{i}}^{\ell}\not\prec^{\textup{ml}}x_{S_{i}}^{\ell+1}$, then this
contradicts $x_{S_{i}}^{\ell}\prec_{u(S_{i},\ell)}x_{S_{i}}^{\ell+1}$;
otherwise we know
$x_{S_{i}}^{1}\prec^{\textup{ml}}x_{S_{i}}^{2}\prec^{\textup{ml}}\dots\prec^{\textup{ml}}x_{S_{i}}^{|S_{i}|}$
which contradicts $x_{S_{i}}^{|S_{i}|}\prec_{u(S_{i},|S_{i}|)}x_{S_{i}}^{1}$.
This proves that $H_{S}$ is indeed a hitting set for $\mathcal{H}$.

Suppose now that $H$ is a hitting set for $\mathcal{H}$; we will show that $H$
itself is a solution for our instance $\mathcal{I}$ of MLVD by defining a
master list $\prec^{\textup{ml}}$ for $\mathcal{I}-H$. For each $i\in[m]$, let
$\ell_{i}$ be the index for which $u(S_{i},\ell_{i})\in H$; such an index
$\ell_{i}$ exists by the definition of a hitting set. Then we set

$x_{S_{i}}^{\ell_{i}+1}\prec^{\textup{ml}}x_{S_{i}}^{\ell+2}\prec^{\textup{ml}}\dots\prec^{\textup{ml}}x_{S_{i}}^{|S_{i}|}\prec^{\textup{ml}}x_{S_{i}}^{1}\prec^{\textup{ml}}\dots\prec^{\textup{ml}}x_{S_{i}}^{\ell_{i}}.$

Furthermore, we set
$x_{|S_{i}|}^{\ell_{i}}\prec^{\textup{ml}}x_{S_{i+1}}^{\ell_{i+1}+1}$ for each
$i\in[m-1]$, so that $\prec^{\textup{ml}}$ is now a strict linear order over
$X$. It is clear that the preferences of each agent $u\in U\setminus H$ in
$\mathcal{I}-H$ are consistent with $\prec^{\textup{ml}}$. Finally, we let
$\prec^{\textup{ml}}$ order $U$ according to $\prec^{U}$; then preferences of
agents in $U$ are consistent with $\prec^{\textup{ml}}$ as well, proving that
$\mathcal{I}-H\in\mathcal{F}_{\textup{ML}}$, which in turn proves the
correctness of the reduction.

Observe that the above reduction is a polynomial-time reduction as well as an
FPT-reduction, if the parameter is $k$ both in the instance $\mathcal{H}$ of
Hitting Set and in MLVD. Since Hitting Set is $\mathsf{NP}$-hard and
$\mathsf{W}[2]$-complete with parameter $k$ (see [30],[15]), this shows that
MLVD is $\mathsf{NP}$-hard and $\mathsf{W}[2]$-hard with parameter $k$. To
show our inapproximability result, let $f(\mathcal{H})$ denote the instance
$\mathcal{I}$ created in the above reduction. The above arguments prove that
the size of an optimal solution for $f(\mathcal{H})=\mathcal{I}$ equals the
size of a hitting set for $\mathcal{H}$ of minimum size. Moreover, for any set
$S$ of vertices in $G$ that is a solution for our MLVD instance $\mathcal{I}$,
the set $H_{S}$ is a hitting set in $\mathcal{H}$ with $|H_{S}|\leq|S|$, so
setting $g(S)=H_{S}$ yields that the pair $(f,g)$ is an approximation
preserving reduction from Hitting Set to MLVD. By the results of Karthik et
al. [31], we know that no FPT algorithm with parameter $k$ can obtain an
$f(k)$-approximation for Hitting Set for any computable function $f$, unless
$\mathsf{FPT}=\mathsf{W}[1]$.222In fact, Karthik et al. [31] deal with the
Dominating Set problem, which is a subset of the Set Cover problem, which is
in turn well known to be equivalent with Hitting Set. Thus, the results in
[31] carry over for Hitting Set. Hence, our reduction implies the
inapproximability statement of the theorem.

###  4.2 Weakly ordered preferences

Let us now consider preference systems that are not necessarily strict. The
hardness results of Section 4.1 trivially hold for weakly ordered preferences,
so we will focus on extending the algorithmic results of the previous section.
We start by showing that Lemma 1 can be generalized for instances with weakly
ordered preferences.

######  Lemma 2.

For any preference system $\mathcal{I}=(G,\preceq)$,
$\Delta^{\textup{swap}}(\mathcal{I})\leq k$ if and only if there exists a set
of at most $k$ arcs in the preference digraph $D_{\mathcal{I}}$ of
$\mathcal{I}$ that hits every strict cycle of $D_{\mathcal{I}}$.

###### Proof.

Suppose first that $\Delta^{\textup{swap}}(\mathcal{I})\leq k$. This means
that there exists a preference system
$\mathcal{I}^{\prime}=(G,\preceq^{\prime})\in\mathcal{F}_{\textup{ML}}$ such
that $\Delta(\mathcal{I},\mathcal{I}^{\prime})\leq k$. Let $V$ denote the
vertex set of $G$, and let

$S_{v}=\\{\\{a,b\\}:a\prec_{v}b\textrm{ but }b\preceq^{\prime}_{v}a,\textrm{
or }a\sim_{v}b\textrm{ but }a\not\sim^{\prime}_{v}b\\}.$

By definition,

$\Delta(\mathcal{I},\mathcal{I}^{\prime})=\sum_{v\in
V}\Delta(\preceq_{v},\preceq^{\prime}_{v})=\sum_{v\in V}|S_{v}|\leq k.$

We construct an arc set $F$ in $D_{\mathcal{I}}$ by adding an arc to $F$ for
each $\\{a,b\\}\in S_{v}$ for some $v$ as follows:

  * (i)

if $a\prec_{v}b$ but $b\preceq^{\prime}_{v}a$, then we add the strict arc
$(a,b)$ with label $v$ to $F$;

  * (ii)

if $a\sim_{v}b$ but $a\prec^{\prime}_{v}b$, then we add the tied arc $(b,a)$
with label $v$ to $F$.

Note that $|F|\leq\sum_{v\in V}|S_{v}|\leq k$.

We claim that deleting $F$ from $D_{\mathcal{I}}$ yields a subgraph of
$D_{\mathcal{I}^{\prime}}$, and additionally, all arcs that are strict in
$D_{\mathcal{I}}$ and are not in $F$ are also strict in
$D_{\mathcal{I}^{\prime}}$. To see this, let us compare $D_{\mathcal{I}}$ and
$D_{\mathcal{I}^{\prime}}$. Note that both $\mathcal{I}$ and
$\mathcal{I}^{\prime}$ have $G$ as their underlying graph. Therefore, it
suffices to consider the changes in the preference digraph when preferences
change from $\preceq$ to $\preceq^{\prime}$, which amounts to considering each
pair $\\{a,b\\}\in\bigcup_{v\in V}S_{v}$. Let us fix some $v$, and consider
$\\{a,b\\}\in S_{v}$. First, if $a\prec_{v}b$, then $D_{\mathcal{I}}$ contains
a strict arc $(a,b)$ with label $v$, but this arc has been added to $F$ in
case (i), and hence there is no arc with label $v$ with endpoints $a$ and $b$
in $D_{\mathcal{I}}-F$. Second, if $a\sim_{v}b$ but $a\prec^{\prime}_{v}b$,
then $D_{\mathcal{I}}$ contains a pair of tied arcs with label $v$ between $a$
and $b$, but the one pointing from $b$ to $a$ has been added to $F$ in case
(ii), and hence only the arc $(a,b)$ with label $v$ remains in
$D_{\mathcal{I}}-F$; by $a\prec^{\prime}b$, such an arc is also present in
$D_{\mathcal{I}^{\prime}}$ as a strict arc. This proves our claim.

As a consequence, any cycle $C$ in $D_{\mathcal{I}}$ that contains a strict
arc and is not hit by $F$ (i.e., $A(C)\cap F=\emptyset$) is also present in
$D_{\mathcal{I}^{\prime}}$, and contains an arc that is strict in
$D_{\mathcal{I}^{\prime}}$. In other words, any strict cycle in
$D_{\mathcal{I}}$ corresponds to a strict cycle in $S_{\mathcal{I}^{\prime}}$.
However, by Lemma 3.2 no strict cycle can be present in
$D_{\mathcal{I}^{\prime}}$, as
$\mathcal{I}^{\prime}\in\mathcal{F}_{\textup{ML}}$. This shows that $F$ hits
all strict cycles in $D_{\mathcal{I}}$.

To prove the other direction of our statement, suppose now that $F$ is a set
of at most $k$ arcs in $D_{\mathcal{I}}$ that hits all strict cycles. Let us
call a path in $D_{\mathcal{I}}$ a _strict path_ if it contains a strict arc.
We proceed with the following iteration on $D_{\mathcal{I}}-F$: as long as
there exist distinct vertices $a$ and $b$ such that there is no strict path
either from $a$ to $b$ or from $b$ to $a$, add a pair of tied arcs between $a$
and $b$. Let $D^{\prime}$ be the digraph obtained at the end of this
iteration. Observe that $D^{\prime}$ still has the property that it contains
no cycle passing through a strict arc.

Let us now define a master list $\prec^{\textup{ml}}$ by setting
$a\prec^{\textup{ml}}b$ whenever there is a strict path from $a$ to $b$.
Observe that the relation $\prec^{\textup{ml}}$ is irreflexive (as a strict
path from $a$ to $a$ would yield a strict cycle), asymmetric (as a strict path
from $a$ to $b$ and from $b$ to $a$ implies the existence of a strict cycle),
and transitive as well (as a strict path from $a$ to $b$ together with one
from $b$ to $c$ yields a strict path from $a$ to $c$, due to the absence of
strict cycles). Thus, $\prec^{\textup{ml}}$ is a partial order, and it remains
to show that indifference w.r.t. $\prec^{\textup{ml}}$, that is,
$\sim^{\textup{ml}}$ is transitive. And indeed, if $a\sim^{\textup{ml}}b$ and
$b\sim^{\textup{ml}}c$ for vertices $a,b,c\in V$, then as a results of our
iterative process there must exist a pair of tied arcs between $a$ and $b$,
and also between $b$ and $c$. Therefore, $a\prec^{\textup{ml}}c$ is not
possible, as a strict path from $a$ to $c$ together with the arcs $(c,b)$ and
$(b,a)$ would imply the existence of a strict cycle in $D^{\prime}$, a
contradiction.

Let $\mathcal{I}^{\prime}$ be the preference system whose underlying graph is
$G$ and preferences are derived from $\preceq^{\textup{ml}}$; then
$\mathcal{I}^{\prime}\in\mathcal{F}_{\textup{ML}}$. We claim
$\Delta(\mathcal{I},\mathcal{I}^{\prime})\leq|F|\leq k$, which would imply
$\Delta^{\textup{swap}}(\mathcal{I})\leq k$, and hence would finish the proof.
For each $v\in V$ let us define

$S_{v}=\\{\\{a,b\\}:a\prec_{v}b\textrm{ but }b\preceq^{\textup{ml}}a,\textrm{
or }a\sim_{v}b\textrm{ but }a\not\sim^{\textup{ml}}b\\}.$

Consider any pair $\\{a,b\\}\in S_{v}$ for some $v\in V$. First, if
$a\prec_{v}b$ but $a\not\prec^{\textup{ml}}b$, then the strict arc $(a,b)$
with label $v$ must be contained in $F$, as otherwise it would imply a strict
path from $a$ to $b$ in $D^{\prime}$, contradicting
$a\not\prec^{\textup{ml}}b$. Second, if $a\sim_{v}b$ but
$a\prec^{\textup{ml}}b$, then the arc $(b,a)$ (part of a pair of tied arcs in
$D_{\mathcal{I}}$) must be contained in $F$, as otherwise together with the
strict path from $a$ to $b$ (whose existence follows from
$a\prec^{\textup{ml}}b$) it would yield a cycle passing through a strict arc
in $D^{\prime}$. Therefore we know $\sum_{v\in V}|S_{v}|\leq|F|\leq k$,
proving our claim.

Thanks to Lemma 2, we can reduce MLS to a generalization of the Feedback Arc
Set problem where, instead of searching for a feedback arc set, the task is to
seek an arc set that only hits certain _relevant_ cycles. In the Subset
Feedback Arc Set (or SFAS) problem the input is a directed graph $D$, a vertex
set $W\subseteq V(D)$ and an integer $k$, and the task is to find a set of at
most $k$ _arcs_ in $D$ that hits all _relevant_ cycles in $D$, where a cycle
is relevant if it goes through some vertex of $W$.

To solve SFAS, we apply an FPT algorithm by Chitnis et al. [12] for the vertex
variant of SFAS, the Directed Subset Feedback Vertex Set (or DSFVS) problem
that, given a directed graph $D$, a set $W\subseteq V(D)$ and a parameter
$k\in\mathbb{N}$, asks for a set of at most $k$ _vertices_ that hits all
relevant cycles in $D$. Applying a simple, well-known reduction from SFAS to
DSFVS, we can use the algorithm by Chitnis et al. [12] to obtain an FPT
algorithm for MLS with parameter $k$.

######  Theorem 4.6.

MLS is fixed-parameter tractable with parameter $k$, even if preferences are
weak orders.

###### Proof.

Due to Lemma 2, we know that we can reduce MLS to an instance of the Subset
Feedback Arc Set problem. To reduce SFAS to DSFVS (that is, Directed Subset
Feedback Vertex Set), we will apply a well-known reduction that is often used
to reduce arc-deletion problems to vertex-deletion problems: given our input
instance $(D,W,k)$ for SFAS we first subdivide each arc $e\in A(D)$ by a new
vertex $a_{e}$, and then replace each vertex $v\in V(D)$ by a set
$X_{v}=\\{v^{1},\dots,v^{k+1}\\}$ of vertices containing $k+1$ copies of $v$,
with each $v^{i}$ having the same in- and out-neighbors as $v$ (after the
subdivisions). Let $D^{\prime}$ denote the directed graph we obtain. It is not
hard to see that $(D,W,k)$ is a ‘yes’-instance of SFAS if and only if
$(D^{\prime},W^{\prime},k)$ is a ‘yes’-instance of DSFVS where
$W^{\prime}=\bigcup\\{X_{v}:v\in W\\}$, as it makes no sense to delete any
vertex in $X_{v}$ for some $v\in V(D)$ (since at least one of the $k+1$ copies
of $v$ in $X_{v}$ will survive), and deleting a vertex $a_{e}$ in $D^{\prime}$
is equivalent with deleting the arc $e$ in $D$. Thus, by the FPT algorithm of
Chitnis et al. [12] for DSFVS, we know that SFAS is also FPT with parameter
$k$.

Next we extend Theorem 4.4 for weak orders, by reducing MLED to SFAS.

######  Theorem 4.7.

There exists an algorithm that achieves a 2-approximation for MLED, and runs
in FPT time with parameter $k$.

2-approximation FPT algorithm for MLED. Let the preference system
$\mathcal{I}$ with underlying graph $G=(V,E)$ and $k\in\mathbb{N}$ be our
input for MLED. For each vertex $v\in V$, let $T_{v}$ be the set family
containing every tie that appears in the preferences of $v$. See Algorithm 2
for a formal description.

First, we construct a directed graph $H_{\mathcal{I}}$ with
$V(H_{\mathcal{I}})=V\cup T\cup U\cup Z$ where

$\displaystyle T$ $\displaystyle=$ $\displaystyle\\{t:v\in V,t\in T_{v}\\},$
$\displaystyle U$ $\displaystyle=$
$\displaystyle\\{a_{v}^{-},a_{v}^{+}:\\{a,v\\}\in E\\},$ $\displaystyle Z$
$\displaystyle=$ $\displaystyle\\{z_{(a,b,v)}:a\prec_{v}b\textrm{ for some
$a,b,v\in V$}\\},$

and with arc set $A(H_{\mathcal{I}})=A_{T}\cup A_{U}\cup A_{Z}$ where

$\displaystyle A_{T}$ $\displaystyle=$
$\displaystyle\\{(t,a_{v}^{-}),(a_{v}^{+},t):v\in V,t\in T_{v},a\in t\\}$
$\displaystyle A_{U}$ $\displaystyle=$
$\displaystyle\\{(a_{v}^{-},a),(a,a_{v}^{+}):v\in V,a\in N_{G}(v)\\}$
$\displaystyle A_{Z}$ $\displaystyle=$
$\displaystyle\\{(a_{v}^{+},z_{(a,b,v)}),(z_{(a,b,v)},b_{v}^{-}):z_{(a,b,v)}\in
Z\\}.$

Next, we solve the Subset Feedback Arc Set problem $(H_{\mathcal{I}},Z,k)$ by
applying the above reduction from SFAS to DSFVS and then using the algorithm
of Chitnis et al. [12]; let $F$ be the solution obtained for
$(H_{\mathcal{I}},Z,k)$. Observe that we may assume that $F$ only contains
arcs of $A_{U}$. Indeed we can replace any arc $f\in F$ in $A_{T}\cup A_{Z}$
by an appropriately chosen arc $f^{\prime}\in A_{U}$: note that $f$ either
points to some $a_{v}^{-}\in U$ or it leaves some $a_{v}^{+}\in U$; in the
former case we set $f^{\prime}=(a_{v}^{-},a)$, while in the latter case we set
$f^{\prime}=(a,a_{v}^{+})$. Then any cycle containing $f$ must also contain
$f^{\prime}$, so we can safely replace $f$ with $f^{\prime}$, as
$F\setminus\\{f\\}\cup\\{f^{\prime}\\}$ still hits all relevant cycles. Hence,
we will assume $F\subseteq A_{U}$.

Finally, we return the set $S_{F}=\\{\\{a,v\\}\in E:(a,a_{v}^{+})\in F\textrm{
or }(a,a_{v}^{+})\in F\\}$.

Algorithm 2 Obtaining a 2-approximation for MLED on input $(\mathcal{I},k)$

1:Construct the graph $H_{\mathcal{I}}$.

2:Let $F$ be a solution for Subset Feedback Arc Set on input
$(H_{\mathcal{I}},Z,k)$.

3:Ensure $F\subseteq A_{U}$ by replacing all arcs pointing to some
$a_{v}^{-}\in U$ with $(a_{v}^{-},a)$ and all arcs leaving some $a_{v}^{+}\in
U$ with $(a,a_{v}^{+})$.

4:Return $S_{F}=\\{\\{a,v\\}\in E:(a,a_{v}^{+})\in F\textrm{ or
}(a_{v}^{-},a)\in F\\}$.

###### of Theorem 4.7.

It is clear that Algorithm 2 runs in FPT time with parameter $k$, so it
suffices to show that it yields a 2-approximation. Let us show that if there
exists a set $S$ of at most $k$ edges in $G$ such that $\mathcal{I}-S$ admits
a master list $\prec^{\textup{ml}}$, then Algorithm 2 returns a solution for
$\mathcal{I}$ of size at most $2|S|\leq 2k$.

Take any vertex $a\in V$ incident to some edge in $S$; let
$\\{a,b_{1}\\},\dots,\\{a,b_{t}\\}$ be the edges of $S$ incident to $a$.
Instead of deleting these edges, it is also possible to “move” the vertices in
$B=\\{b_{1},\dots,b_{t}\\}$ within the preferences of $a$ to obtain an
instance $\mathcal{I}^{\prime}$ whose preferences are consistent with
$\prec^{\textup{ml}}$: when representing $a$’s preferences as a list possibly
containing ties, each $b\in B$ needs to be moved either to the left (becoming
more preferred by $a$) or to the right (becoming less preferred by $a$). In
the former case we mark the arc $(b,b_{a}^{+})$, and in the latter case we
mark $(b_{a}^{-},b)$. Clearly, we have marked at most $2|S|\leq 2k$ arcs in
$H_{\mathcal{I}}$, since for each edge $\\{a,b\\}\in S$ we may need to move
$a$ in $b$’s preferences, and also to move $b$ in $a$’s preferences, and each
such move results in marking one arc.

We claim that the set $M$ of marked arcs hits every relevant cycle in
$H_{\mathcal{I}}$, that is, $H_{\mathcal{I}}-M$ contains no cycle passing
through a vertex of $Z$. Suppose for contradiction that there is a cycle $C$
in $D_{\mathcal{I}}-M$ going through a vertex of $Z$. Let us consider the
decomposition of $C$ into paths $P_{1},\dots,P_{r}$ such that $V\cap V(P_{i})$
contains exactly the endpoints of $P_{i}$ for each $i\in[r]$. Let $P_{i}$ be
such a path from $a$ to $b$. Observe that there are two possible forms $P_{i}$
can take: either

  * (i)

$P_{i}=(a,a^{+}_{v},t,b^{-}_{v},b)$ for some $v\in V$ and $t\in T_{v}$, or

  * (ii)

$P_{i}=(a,a^{+}_{v},z_{(a,b,v)},b^{-}_{v},b)$.

In both cases it follows that $a\preceq^{\textup{ml}}b$ holds: first,
$a\preceq_{v}b$ holds in $G$ by construction (since $a\sim_{v}b$ in case (i)
and $a\prec_{v}b$ in case (ii)), and we have not moved $a$ up in $v$’s
preferences (because $(a,a_{v}^{+})\notin M$), nor have we moved $b$ down in
$v$’s preferences (because $(b_{v}^{-},b)\notin M$), so $v$ still weakly
prefers $b$ to $a$ in the instance $\mathcal{I}^{\prime}$ whose preferences
are consistent with $\prec^{\textup{ml}}$. Furthermore, in case (ii) we know
$a\prec_{v}b$, and using the same reasoning we obtain $a\prec^{\textup{ml}}b$
as well. Therefore, the cycle $C$ implies a cycle in the preference digraph
$D_{\mathcal{I}^{\prime}}$ of $\mathcal{I}^{\prime}$, and since $C$ contains a
vertex of $Z$, at least one arc of this cycle is a strict arc (namely, if
$z_{(a,b,v)}\in V(C)$, then the arc $(a,b)$ with label $v$ is a strict arc in
$D_{\mathcal{I}^{\prime}}$), which contradicts
$\mathcal{I}^{\prime}\in\mathcal{F}_{\textup{ML}}$ by Lemma 3.2. Thus, $M$
hits every relevant cycle in $H_{\mathcal{I}}$, and has size at most $2k$.

This implies that Algorithm 2 will produce an arc set $F$ for
$H_{\mathcal{I}}$ of size at most $2k$ on line 2. It remains to show that the
set $S_{F}$ is indeed a solution for our instance $\mathcal{I}$ of MLED. For
this, we will need the observation that, due to the construction of
$H_{\mathcal{I}}$, we can obtain the preference digraph $D_{\mathcal{I}}$ from
$H_{\mathcal{I}}$ by applying the following operations:

  1. 1.

For each $v\in V$, contract all arcs running between $v$ and $U$. Note that
each such arc is either the unique outgoing or the unique incoming arc of some
vertex of $U$. We will keep referring to the node resulting from these
contractions as $v$, corresponding directly to the vertex $v$ in
$D_{\mathcal{I}}$.

  2. 2.

For each $t\in T_{v}$ for some $v\in V$, replace $t$ and its neighborhood in
$H_{\mathcal{I}}$ (which induces a bidirected star with center $t$) with a
bidirected clique on $N_{H_{\mathcal{I}}}(t)$, i.e., for each
$\\{a,b\\}\subseteq t$, add the pair $(a,b)$ and $(b,a)$ of arcs with label
$v$. These arcs correspond to a pair of tied arcs in $D_{\mathcal{I}}$.

  3. 3.

Lift each $z_{(a,b,v)}\in Z$, i.e., delete $z_{(a,b,v)}$ and add an arc
$(a,b)$ with label $v$. These arcs correspond to strict arcs in
$D_{\mathcal{I}}$.

It follows that there is a bijection between the cycles in $H_{\mathcal{I}}$
passing through some vertex of $Z$ and the cycles in $D_{\mathcal{I}}$ passing
through a strict arc.

Now, consider how the digraph $H_{\mathcal{I}}$ changes as a result of
deleting the edges of $S_{F}$ from $\mathcal{I}$. Note that the deletion of
$S_{F}$ ensures the removal of all arcs in $F$ (since deleting an edge
$\\{a,b\\}$ from $G$ results in the removal of vertices
$a_{b}^{+},a_{b}^{-},b_{a}^{+},$ and $b_{a}^{-}$ and all arcs incident to them
from $H_{\mathcal{I}}$), so the resulting digraph $H_{\mathcal{I}-S_{F}}$
contains no cycles passing through a vertex of $Z$. As we proved in the
previous paragraph, $H_{\mathcal{I}-S_{F}}$ contains no cycles passing through
a vertex of $Z$ if and only if the preference digraph of $\mathcal{I}-S_{F}$
contains no cycles passing through a strict arc. Therefore by Lemma 3.2 we get
$\mathcal{I}-S_{F}\in\mathcal{F}_{\textup{ML}}$.

##  5 Applications

In this section we consider two examples related to stable and popular
matchings where we can efficiently solve computationally hard optimization
problems on preference systems that are close to admitting a master list.

###  5.1 Optimization over stable matchings

One of the most appealing property of the distances defined in Section 3 is
that whenever the distance of a _strict_ (but not necessarily bipartite)
preference system from admitting a master list is small, we obtain an upper
bound on the number of stable matchings contained in the given preference
system. Therefore, strict preference systems that are close to admitting a
master list are easy to handle, as we can efficiently enumerate their stable
matchings, as Lemmas 5.1 and 5.3 show. We omit presenting a proof for these
lemmas, because we will prove more generals versions of them in Section 5.2,
namely, Lemmas 5.6 and 5.7.

######  Lemma 5.1.

Given a strict preference system $\mathcal{I}=(G,\prec)$ with $G=(V,E)$ and a
set $S\subseteq E$ of edges such that
$\mathcal{I}-S\in\mathcal{F}_{\textup{ML}}$, the number of stable matchings in
$\mathcal{I}$ is at most $2^{|S|}$, and it is possible to enumerate all of
them in time $2^{|S|}\cdot O(|E|)$.

Observe that Corollary 5.2 follows immediately from Lemma 5.1 and the fact
that
$\Delta^{\textup{edge}}(\mathcal{I})\leq\Delta^{\textup{swap}}(\mathcal{I})$
for any preference system $\mathcal{I}$ (as we know by Lemma 3.3).

######  Corollary 5.2.

In a strict preference system $\mathcal{I}$, the number of stable matchings is
at most $2^{\Delta^{\textup{swap}}(\mathcal{I})}$.

Notice that although the number of stable matchings may grow exponentially as
a function of the distance $\Delta^{\textup{edge}}$ or
$\Delta^{\textup{swap}}$, this growth does not depend on the size of the
instance. By contrast, this is not the case for the distance
$\Delta^{\textup{vert}}$, as stated by Lemma 5.3 below.

######  Lemma 5.3.

Given a strict preference system $\mathcal{I}=(G,\prec)$ with $G=(V,E)$ and a
set $S\subseteq V$ of vertices such that
$\mathcal{I}-S\in\mathcal{F}_{\textup{ML}}$, the number of stable matchings in
$\mathcal{I}$ is at most $|V|^{|S|}$, and it is possible to enumerate all
stable matchings of $\mathcal{I}$ in time $|V|^{|S|}\cdot O(|E|)$.

There exists an algorithm by Gusfield and Irving [25, 26] that outputs the set
$\mathcal{S}(\mathcal{I})$ of stable matchings in a preference system
$\mathcal{I}$ over a graph $G=(V,E)$ in
${O(|\mathcal{S}(\mathcal{I})|\\!\cdot\\!|E|)}$ time after
$O(|V|\cdot|E|\log|V|)$ preprocessing time. As a consequence, the bounds of
Lemma 5.1, Corollary 5.2, and Lemma 5.3 on $|\mathcal{S}(\mathcal{I})|$
directly yield a way to handle computationally hard problems on any preference
system $\mathcal{I}$ where $\Delta^{\textup{swap}}(\mathcal{I})$,
$\Delta^{\textup{edge}}(\mathcal{I})$, or
$\Delta^{\textup{vert}}(\mathcal{I})$ has small value, even without the need
to determine a set $S$ of edges or vertices for which
$\mathcal{I}-S\in\mathcal{F}_{\textup{ML}}$ or a set $S$ of swaps for which
$I\lhd S\in\mathcal{F}_{\textup{ML}}$. Thus, we immediately have the following
result, even without having to use our results in Section 4. For the
definitions of the $\mathsf{NP}$-hard problems mentioned as an example in
Theorem 5.4, see the book [37].

######  Theorem 5.4.

Let $\mathcal{I}$ be a strict (but not necessarily bipartite) preference
system, and $Q$ any optimization problem where the task is to maximize or
minimize some function $f$ over $\mathcal{S}(\mathcal{I})$ such that $f(M)$
can be computed in polynomial time for any matching
$M\in\mathcal{S}(\mathcal{I})$. Then $Q$ can be solved

  * (i)

in FPT time with parameter $\Delta^{\textup{edge}}(\mathcal{I})$ or
$\Delta^{\textup{swap}}(\mathcal{I})$;

  * (ii)

in polynomial time if $\Delta^{\textup{vert}}(\mathcal{I})$ is constant.

In particular, these results hold for Sex-Equal Stable Matching, Balanced
Stable Matching, (Generalized) Median Stable Matching333Although the problem
of finding a (generalized) median matching is not an optimization problem over
$\mathcal{S}(\mathcal{I})$, it is clear that it can be solved in
$|\mathcal{S}(\mathcal{I})|\cdot O(|\mathcal{I}|)$ time. , Egalitarian Stable
Roommates, and Maximum-Weight Stable Roommates.

####  5.1.1 Tightness of our bounds on the number of stable matchings.

The bounds stated in Lemmas 5.1 and 5.3 are tight in the following sense.
First, the tightness of Lemma 5.1 is shown by the existence of a strict
preference system $\mathcal{I}_{k}$ for any $k\in\mathbb{N}$ such that
$\Delta^{\textup{edge}}(\mathcal{I}_{k})=k$ and $\mathcal{I}_{k}$ admits
$2^{k}$ stable matchings. A simple example for such an instance
$\mathcal{I}_{k}$ is obtained by taking $k$ disjoint copies of a preference
system whose underlying graph is a cycle of length four, with cyclic
preferences.

Second, to show the asymptotic tightness of Lemma 5.3, one can construct a
strict preference system $\mathcal{J}_{k,n}$ for any $k,n\in\mathbb{N}$ with
$n\geq k$ such that the following properties are satisfied:
${\Delta^{\textup{vert}}(\mathcal{J}_{k,n})=k}$, the number of vertices in
$\mathcal{J}_{k,n}$ is $2n$, and $\mathcal{J}_{k,n}$ admits $\binom{n}{k}$
stable matchings. Such a family of preference systems is presented in Example
1.

######  Example 1.

Let the vertex set of $\mathcal{J}_{k,n}$ be $V=A\cup B\cup S$ where
$A=\\{a_{1},\dots,a_{n}\\}$, $B=\\{b_{1},\dots,b_{n-k}\\}$, and
$S=\\{s_{1},\dots,s_{k}\\}$; note $|V|=2n$. Let $a_{i}\in A$ be adjacent to
all vertices of $S$, and let it be adjacent to some $b_{j}\in B$ exactly if
$i-k\leq j\leq i$; we denote by $E$ the set of edges thus defined, and we let
$G=(V,E)$ be the graph underlying $\mathcal{J}_{k,n}$. See Figure 1 for an
illustration. The preferences of the vertices are as follows:

  * •

any vertex $b\in B$ prefers $a_{j}$ to $a_{i}$ for some $a_{j},a_{i}\in
N_{G}(b)$ exactly if $j>i$;

  * •

any vertex $s\in S$ prefers $a_{j}$ to $a_{i}$ for some $a_{j},a_{i}\in
N_{G}(s)$ exactly if $j<i$;

  * •

the preference list of some $a_{i}\in A$ is
$b_{i},s_{1},b_{i-1},s_{2},\dots,b_{i-k+1},s_{k},b_{i-k}$; if some of these
vertices are not defined, they are omitted from the list.

Observe that deleting the vertices of $S$ from $\mathcal{J}_{k,n}$ yields an
instance that admits a master list, and moreover, deleting less than $k$
vertices cannot result in an instance in $\mathcal{F}_{\textup{ML}}$, since
any vertex of $S$ and any vertex of $B$ disagree on the order of vertices in
$A$. Hence, $\Delta^{\textup{vert}}(\mathcal{J}_{k,n})=k$.

Figure 1: Illustration of the preference system $\mathcal{J}_{k,n}$ for $k=3$.
Edges of the underlying graph are shown in grey, while edges of a stable
matching are shown in black (and bold). Preferences are depicted either by
numbers determining the rank of the given edge, or by an arrow, pointing from
less-preferred edges towards more-preferred ones.

We claim that $\mathcal{J}_{k,n}$ admits $\binom{n}{k}$ stable matchings. Let
$A^{\prime}=\\{a_{i_{1}},\dots,a_{i_{k}}\\}$ be any subset of $k$ vertices
from $A$. We define a matching $M_{A^{\prime}}$ as follows. First, let
$M_{A^{\prime}}$ contain the edges $s_{j}a_{i_{j}}$ for each $j\in[k]$.
Second, let $M_{A^{\prime}}$ match some $b_{j}$ with $a_{j+\ell}$ if $\ell$ is
the number of indices in $\\{i_{1},\dots,i_{k}\\}$ smaller or equal to $j$. It
is straightforward to verify that $M_{A^{\prime}}$ is stable, since no vertex
of $A$ can be part of a blocking edge. Since stable matchings in
$\mathcal{J}_{k,n}$ are complete, any stable matching $M$ must be of the form
$M_{A^{\prime}}$ for some $A^{\prime}\subseteq A$ (namely, for
${A^{\prime}=\\{M(s):s\in S\\}}$), so the number of stable matchings in
$\mathcal{J}_{k,n}$ is exactly $\binom{n}{k}$.

We remark that we were not able to construct a preference system that, for a
given $k$, is at $\Delta^{\textup{swap}}$-distance $k$ from admitting a master
list, and contains $2^{k}$ stable matchings. Recall the preference system
$\mathcal{I}_{k}$ that served as an example to prove the tightness of Lemma
5.1 for the $\Delta^{\textup{edge}}$-distance, containing $k$ copies of a
four-cycle with cyclic preferences. It is not hard to see that
$\Delta^{\textup{swap}}(\mathcal{I}_{k})=2k$, implying that the number of
stable matchings in a strict preference system $\mathcal{I}$ can be as large
as $2^{\Delta^{\textup{swap}}(\mathcal{I})/2}$. We leave it as an open
question to determine the exact bound on the maximum number of stable
matchings in a strict preference system $\mathcal{I}$ as a function of
$\Delta^{\textup{swap}}(\mathcal{I})$.

###  5.2 Maximum-utility popular matchings with instability costs

We now turn our attention to the Max-Utility Popular Matching with Instability
Costs problem, studied in [40]: given a strict preference system
$\mathcal{I}=(G,\prec)$, a utility function
$\omega:E(G)\rightarrow\mathbb{N}$, a cost function
$c:E(G)\rightarrow\mathbb{N}$, an objective value $t\in\mathbb{N}$ and a
budget $\beta\in\mathbb{N}$, the task is to find a popular matching in
$\mathcal{I}$ whose utility is at least $t$ and whose blocking edges have
total cost at most $\beta$. Our aim is to investigate whether we can solve
this problem efficiently for instances that are close to admitting a master
list.

Note that in general this problem is computationally hard even if the given
preference system is strict, bipartite, admits a master list, and the cost and
utility functions are very simple. Namely, given a strict, bipartite
preference system $(G,\prec)\in\mathcal{F}_{\textup{ML}}$ for which a stable
matching has size $|V(G)|/2-1$, it is $\mathsf{NP}$-hard and
$\mathsf{W}[1]$-hard with parameter $\beta$ to find a complete popular
matching (i.e., one that is larger than a stable matching) that admits at most
$\beta$ blocking edges [40]. Nevertheless, if the total cost $\beta$ of the
blocking edges that we allow is a constant and each edge has cost at least 1,
then Max-Utility Popular Matching with Instability Costs can be solved in
polynomial time for bipartite, strict preference systems that admit a master
list (in fact, it suffices to assume that the preferences of all vertices on
one side of the bipartite input graph are consistent with a master list),
representing an island of tractability for this otherwise extremely hard
problem [40]. Therefore, it is natural to ask whether we can extend this
result for strict preferences systems that are close to admitting a master
list. Theorem 5.5 answers this question affirmatively.

######  Theorem 5.5.

Let $\mathcal{I}$ be a strict (but not necessarily bipartite) preference
system with $G=(V,E)$. Then an instance $(\mathcal{I},\omega,c,t,\beta)$ of
Max-Utility Popular Matching with Instability Costs where $c(e)\geq 1$ for all
edges $e\in E$, and $\beta$ is constant can be solved

  * (i)

in FPT time with parameter $\Delta^{\textup{edge}}(\mathcal{I})$ or
$\Delta^{\textup{swap}}(\mathcal{I})$;

  * (ii)

in polynomial time if $\Delta^{\textup{vert}}(\mathcal{I})$ is constant.

We apply the same approach as in Section 5.1, with a crucial difference: for
the algorithms proving Theorem 5.5 we will need to determine a set of edges or
vertices whose deletion yields an instance in $\mathcal{F}_{\textup{ML}}$.
Using such a set, we then apply Lemma 5.6 or 5.7 below; these are
generalizations of Lemmas 5.1 and 5.3 for the case when we allow a fixed set
of edges to block the desired matching.

######  Lemma 5.6.

Given a strict preference system $\mathcal{I}=(G,\prec)$ with $G=(V,E)$ and
edge sets $B\subseteq E$ and $S\subseteq E$ such that
$\mathcal{I}-S\in\mathcal{F}_{\textup{ML}}$, the number of matchings $M$ for
which $B=\textup{bp}(M)$ is at most $2^{|S|}$, and it is possible to enumerate
them in time $2^{|S|}\cdot O(|E|)$.

###### Proof.

We propose an algorithm that enumerates all matchings $M$ of the input
instance $\mathcal{I}$ for which $\textup{bp}(M)=B$ by using a bounded search
tree approach. Let $M$ be a hypothetical stable matching in $\mathcal{I}$. The
algorithm tries all possible ways to find $M$, thus enumerating all stable
matchings, as follows. See Algorithm 3 for a pseudocode.

First, the algorithm “guesses” the set $M_{S}=M\cap S$. Then it creates a
preference system $\mathcal{I}^{\prime}$ by deleting the edges of $B\cup S$
and also the vertices in $V(M_{S})$ from $\mathcal{I}$; note that
$\mathcal{I}^{\prime}$ admits a master list. Therefore, there exists a unique
stable matching $M^{\prime}$ in $\mathcal{I}^{\prime}$ which can be found in
time $O(|E|)$ [28]444In fact, Irving et al. [28] only considered the bipartite
case, but it is easy to see that the straightforward algorithm where vertices
pick their partners one-by-one according to their order on the master list,
each choosing their favorite among those still available, results in the
unique stable matching, regardless of whether the underlying graph is
bipartite or not. . The algorithm then checks if $\textup{bp}(M_{S}\cup
M^{\prime})=B$ holds in $\mathcal{I}$ (this can be performed in $O(|E|)$ time
as well), and if so, outputs it. Observe that the algorithm outputs at most
$2^{|S|}$ matchings, and has running time $2^{|S|}\cdot O(|E|)$, because there
are $2^{|S|}$ possible ways to choose $M_{S}$.

Algorithm 3 Enumerating all matchings in a preference system $\mathcal{I}$
that admit a fixed set $B$ of blocking edges, given a set $S$ of edges in
$\mathcal{I}$ such that $\mathcal{I}-S\in\mathcal{F}_{\textup{ML}}$.

1:for all $M_{S}\subseteq S$ do

2: Let $\mathcal{I}^{\prime}=\mathcal{I}-(S\cup B)-V(M_{S})$. $\triangleright$
Note $\mathcal{I}^{\prime}\in\mathcal{F}_{\textup{ML}}$.

3: Compute the unique stable matching $M^{\prime}$ in $\mathcal{I}^{\prime}$.

4: Let $M=M_{S}\cup M^{\prime}$.

5: if $\textup{bp}(M)=B$ in $\mathcal{I}$ then output $M$.

It is clear that any matching output by the algorithm satisfies
$\textup{bp}(M)=B$ in $\mathcal{I}$. It remains to prove that it enumerates
all such matchings in $\mathcal{I}$. So let $M$ be any matching of
$\mathcal{I}$ for which $\textup{bp}(M)=B$. Consider the iteration
corresponding to choosing $M_{S}=M\cap S$ on line 1 of Algorithm 3. Note that
$M\setminus M_{S}$ is a matching that is present in
$\mathcal{I}^{\prime}=\mathcal{I}-(S\cup B)-V(M_{S})$, and we show that it is
stable in $\mathcal{I}^{\prime}$ as well. Note that by definition, $M$ is
stable in $\mathcal{I}-B$, and also in $\mathcal{I}-(B\cup(S\setminus M))$.
Furthermore, deleting the edges of $M_{S}\subseteq M$ together with their
endpoints yields a stable matching in the remaining instance, and so
$M\setminus M_{S}$ is also stable in $\mathcal{I}-(B\cup(S\setminus
M))-V(M_{S})=\mathcal{I}^{\prime}$. Since there is only one stable matching in
$\mathcal{I}^{\prime}$, we obtain that $M\setminus M_{S}$ must be the matching
$M^{\prime}$ found at line 3 (within the iteration corresponding to choosing
$M_{S}$ on line 1). Hence, the algorithm creates the matching
$M_{S}\cup(M\setminus M_{S})=M$ on the next line, and since $\textup{bp}(M)=B$
holds in $\mathcal{I}$, the algorithm outputs it on line 5.

######  Lemma 5.7.

Given a strict preference system $\mathcal{I}=(G,\prec)$ with $G=(V,E)$, an
edge set $B\subseteq E$, and a vertex set $S\subseteq V$ such that
$\mathcal{I}-S\in\mathcal{F}_{\textup{ML}}$, the number of matchings $M$ for
which $B=\textup{bp}(M)$ is at most $|V|^{|S|}$, and it is possible to
enumerate them in time $|V|^{|S|}\cdot O(|E|)$.

###### Proof.

We propose an algorithm that enumerates all matchings $M$ of the input
instance $\mathcal{I}$ for which $\textup{bp}(M)=B$ by using a bounded search
tree approach. Let $M$ be a hypothetical stable matching in $\mathcal{I}$. The
algorithm tries all possible ways to find $M$, thus enumerating all stable
matchings, as follows. See Algorithm 4 for a pseudocode.

First, the algorithm “guesses” the set $M_{S}\subseteq E$ of those edges in
$M$ that have at least one endpoint in $S$. Then it creates a preference
system $\mathcal{I}^{\prime}$ by deleting the edges of $B$ and the vertices in
$V(M_{S})\cup S$ from $\mathcal{I}$; note that $\mathcal{I}^{\prime}$ admits a
master list. Therefore, there exists a unique stable matching $M^{\prime}$ in
$\mathcal{I}^{\prime}$ which can be found in time $O(|E|)$ [28]. The algorithm
then checks if $\textup{bp}(M_{S}\cup M^{\prime})=B$ holds in $\mathcal{I}$
(this can be performed in $O(|E|)$ time as well), and if so, outputs it.
Observe that the algorithm outputs at most $|V|^{|S|}$ matchings, and has
running time $|V|^{|S|}\cdot O(|E|)$, because there are at most $|V|^{|S|}$
possible ways to choose $M_{S}$.

Algorithm 4 Enumerating all matchings in a preference system $\mathcal{I}$
that admit a fixed set $B$ of blocking edges, given a set $S$ of vertices in
$\mathcal{I}$ such that $\mathcal{I}-S\in\mathcal{F}_{\textup{ML}}$.

1:for all matching $M_{S}$ in $\mathcal{I}$ with each edge of $M_{S}$ having
an endpoint in $S$ do

2: Let $\mathcal{I}^{\prime}=\mathcal{I}-B-(S\cup V(M_{S}))$. $\triangleright$
Note $\mathcal{I}^{\prime}\in\mathcal{F}_{\textup{ML}}$.

3: Compute the unique stable matching $M^{\prime}$ in $\mathcal{I}^{\prime}$.

4: Let $M=M_{S}\cup M^{\prime}$.

5: if $\textup{bp}(M)=B$ in $\mathcal{I}$ then output $M$.

It is clear that any matching output by the algorithm satisfies
$\textup{bp}(M)=B$ in $\mathcal{I}$. It remains to prove that it enumerates
all such matchings in $\mathcal{I}$. So let $M$ be any matching of
$\mathcal{I}$ for which $\textup{bp}(M)=B$. Consider the iteration
corresponding to choosing $M_{S}=\\{e:e\in M,e\textrm{ has an endpoint in
}S\\}$ on line 1 of Algorithm 4. Note that $M\setminus M_{S}$ is a matching
that is present in $\mathcal{I}^{\prime}=\mathcal{I}-B-S-V(M_{S})$, and we
show that it is stable in $\mathcal{I}^{\prime}$ as well. Note that $M$ is
stable in $\mathcal{I}-B$ by definition. Furthermore, deleting the edges of
$M_{S}\subseteq M$ together with their endpoints and the vertices of
$S\setminus V(M_{S})$, left unmatched by $M$, yields a stable matching in the
remaining instance, and so $M\setminus M_{S}$ is stable in
$\mathcal{I}-B-(V(M_{S})\cup S)=\mathcal{I}^{\prime}$. Since there is only one
stable matching in $\mathcal{I}^{\prime}$, we obtain that $M\setminus M_{S}$
must be the matching $M^{\prime}$ found at line 3 (within the iteration
corresponding to choosing $M_{S}$ on line 1). Hence, the algorithm creates the
matching $M_{S}\cup(M\setminus M_{S})=M$ on the next line, and since
$\textup{bp}(M)=B$ holds in $\mathcal{I}$, the algorithm outputs it on line 5.

We now present our key lemma that, combined with Theorem 4.4, is the basis for
Theorem 5.5.

######  Lemma 5.8.

An instance $(\mathcal{I},\omega,c,t,\beta)$ of Max-Utility Popular Matching
with Instability Costs where $\mathcal{I}=(G,\prec)$ is a strict preference
system with underlying graph $G=(V,E)$ and $c(e)\geq 1$ for all edges $e\in
E$, can be solved

  * (i)

in $2^{|S|}\cdot O(|E|^{\beta+1}\sqrt{|V|}\log|V|)$ time, assuming that a set
$S\subseteq E$ of edges such that $\mathcal{I}-S\in\mathcal{F}_{\textup{ML}}$
is provided as part of the input;

  * (ii)

in $|V|^{|S|}\cdot O(|E|^{\beta+1}\sqrt{|V|}\log|V|)$ time, assuming that a
set $S\subseteq V$ of vertices such that
$\mathcal{I}-S\in\mathcal{F}_{\textup{ML}}$ is provided as part of the input.

###### Proof.

Since all edges have cost at least $1$, we know that the desired matching may
admit at most $\beta$ blocking edges. For each possible edge set $B\subseteq
E$ of size at most $\beta$ whose cost does not exceed the budget $\beta$, the
algorithm of Lemma 5.6 can in $2^{|S|}\cdot O(|E|)$ time enumerate all
matchings $M$ with $\textup{bp}(M)=B$ in case (i), and the algorithm of Lemma
5.7 can in $|V|^{|S|}\cdot O(|E|)$ time enumerate all matchings $M$ with
$\textup{bp}(M)=B$ in case (ii). For each such matching, we can check in
linear time whether it has total utility at least $t$, and we can test in
$O(|E|\sqrt{|V|}\log|V|)$ time whether it is popular [5, 16].

We are now ready to prove Theorem 5.5.

###### of Theorem 5.5.

Let our input instance of Max-Utility Popular Matching with Instability Costs
be $\mathcal{J}=(\mathcal{I},\omega,c,t,\beta)$ where $\mathcal{I}=(G,\prec)$
is a strict preference system with $G=(V,E)$ and $c(e)\geq 1$ for all edges
$e\in E$.

First, suppose that $\Delta^{\textup{vert}}(\mathcal{I})$ is a constant. Then
we find a set $S\subseteq V$ of vertices with
$|S|=\Delta^{\textup{vert}}(\mathcal{I})$ whose deletion yields a preference
system admitting a master list; this can be performed in
$|V|^{\Delta^{\textup{vert}}(\mathcal{I})}=|V|^{O(1)}$ time by trying all
possible vertex sets of size at most $\Delta^{\textup{vert}}(\mathcal{I})$.
Then we apply Lemma 5.8 to solve our instance $\mathcal{J}$, using the set
$S$. Note that the total running time is indeed polynomial, assuming that
$\Delta^{\textup{vert}}(\mathcal{I})$ as well as our budget $\beta$ is
constant.

Second, assume that our parameter is $\Delta^{\textup{edge}}(\mathcal{I})$. To
obtain an FPT algorithm with respect to $\Delta^{\textup{edge}}(\mathcal{I})$,
we first use the 2-approximation of Theorem 4.4 to determine a set $S\subseteq
E$ of edges with $|S|\leq 2\Delta^{\textup{edge}}(\mathcal{I})$ whose deletion
yields a preference system admitting a master list. Given the set $S$, we
again apply Lemma 5.8 to solve our instance $\mathcal{J}$. Observe that the
total running time now is indeed FPT with parameter
$\Delta^{\textup{edge}}(\mathcal{I})$, assuming that $\beta$ is constant.

Since
$\Delta^{\textup{swap}}(\mathcal{I})\geq\Delta^{\textup{edge}}(\mathcal{I})$,
an FPT algorithm with parameter $\Delta^{\textup{edge}}(\mathcal{I})$
immediately yields an FPT algorithm with parameter
$\Delta^{\textup{swap}}(\mathcal{I})$. A more direct approach is to use
Corollary 4.2 to directly determine a set $S$ of swaps of minimum cardinality
for which $I\lhd S\in\mathcal{F}_{\textup{ML}}$, transform $S$ into a set
$S^{\prime}$ of edges with size $|S^{\prime}|\leq|S|$ such that
$\mathcal{I}-S\in\mathcal{F}_{\textup{ML}}$, and then apply Lemma 5.8 to solve
$\mathcal{J}$ using the edge set $S^{\prime}$.

##  6 Summary and further research

We summarize our main results on MLS, MLED, and MLVD in Table 1.
Interestingly, all our hardness results hold for strict preference systems,
and we were able to extend all our positive results for preference systems
with weak orders.

Table 1: Summary of our results on MLS, MLED, and MLVD. Results marked by the sign $\dagger$ assume the Unique Games Conjecture. problem | parameterized complexity | approximation
---|---|---
MLS | FPT wrt $k$ (Cor. 4.2, Thm. 4.6) | constant-factor approx. is $\mathsf{NP}$-hard (Thm. 4.1)†
MLED |  $\mathsf{W}[1]$-hard wrt $k$ (Thm. 4.3) | constant-factor approx. is $\mathsf{NP}$-hard (Thm. 4.1)†
|  | 2-approx. FPT alg wrt $k$ (Thms. 4.4, 4.7)
MLVD |  $\mathsf{W}[2]$-hard wrt $k$ (Thm. 4.5) |  $f(k)$-approx. is $\mathsf{W}[1]$-hard wrt $k$ (Thm. 4.5)

There are a few questions left open in the paper. We gave asymptotically tight
bounds on the maximum number of stable matchings in a strict preference system
$\mathcal{I}$ as a function of $\Delta^{\textup{edge}}(\mathcal{I})$ and
$\Delta^{\textup{vert}}(\mathcal{I})$, but we were not able to do the same for
$\Delta^{\textup{swap}}(\mathcal{I})$. Another question is whether the
approximation factor of our 2-approximation FPT algorithm for MLED can be
improved.

Apart from answering these specific questions, there are several possibilities
for future research. One direction would be to identify further problems that
can be solved efficiently on preference systems that are close to admitting a
master list. Also, it would be interesting to see how these measures vary in
different real-world scenarios, and to find those practical applications where
preference profiles are usually close to admitting a master list.

####  6.0.1 Acknowledgments.

We would like to thank the reviewers of WALCOM 2023 for their helpful
comments. This research was supported by the Hungarian Academy of Sciences
under its Momentum Programme (LP2021-2) and the Hungarian Scientific Research
Fund (OTKA grants K128611 and K124171).

## References

  * [1] D. J. Abraham, A. Levavi, D. F. Manlove, and G. O’Malley.  The stable roommates problem with globally-ranked pairs.  Internet Math., 5:493–515, 2008.
  * [2] J. J. Bartholdi III, C. A. Tovey, and M. A. Trick.  Voting schemes for which it can be difficult to tell who won the election.  Soc Choice Welfare, 6:157–165, 1989.
  * [3] N. Betzler, M. R. Fellows, J. Guo, R. Niedermeier, and F. A. Rosamond.  Fixed-parameter algorithms for Kemeny rankings.  Theoretical Computer Science, 410(45):4554–4570, 2009.
  * [4] N. Bhatnagar, S. Greenberg, and D. Randall.  Sampling stable marriages: Why spouse-swapping won’t work.  In SODA ’08: Proc. of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1223–1232. SIAM, 2008.
  * [5] P. Biró, R. W. Irving, and D. F. Manlove.  Popular matchings in the marriage and roommates problems.  In CIAC ’10: Proc. of the 7th International Conference on Algorithms and Complexity, pages 97–108, 2010.
  * [6] N. Boehmer, P. Faliszewski, R. Niedermeier, S. Szufa, and T. Wąs.  Understanding distance measures among elections.  In IJCAI-22: Proc. of the 31st International Joint Conference on Artificial Intelligence, pages 102–108, 2022.
  * [7] R. Bredereck, J. Chen, D. Knop, J. Luo, and R. Niedermeier.  Adapting stable matchings to evolving preferences.  In AAAI ’20: Proc. of the 34th AAAI Conference on Artificial Intelligence, pages 1830–1837, 2020.
  * [8] R. Bredereck, K. Heeger, D. Knop, and R. Niedermeier.  Multidimensional stable roommates with master list.  In WINE ’20: Proc. of the 16th International Conference on Web and Internet Economics, pages 59–73. Springer, 2020.
  * [9] J. Chen, Y. Liu, S. Lu, B. O’Sullivan, and I. Razgon.  A fixed-parameter algorithm for the directed feedback vertex set problem.  J. ACM, 55(5):21:1–21:19, 2008.
  * [10] J. Chen, P. Skowron, and M. Sorge.  Matchings under preferences: Strength of stability and tradeoffs.  ACM Trans. Econ. Comput., 9(4):20:1–20:55, 2021.
  * [11] C. T. Cheng and W. Rosenbaum.  Stable matchings with restricted preferences: Structure and complexity.  In EC ’21: Proc. of the 22nd ACM Conference on Economics and Computation, pages 319–339, 2021.
  * [12] R. Chitnis, M. Cygan, M. Hajiaghayi, and D. Marx.  Directed subset feedback vertex set is fixed-parameter tractable.  ACM Trans. Algorithms, 11(4):28:1–28:28, 2015.
  * [13] R. Chowdhury.  A simple matching domain with indifferences and a master list.  Rev. Econ. Des., 2022.
  * [14] M. Cygan, F. V. Fomin, Ł. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh.  Parameterized algorithms.  Springer, Cham, 2015.
  * [15] R. G. Downey and M. R. Fellows.  Fundamentals of Parameterized Complexity.  Texts in Computer Science. Springer, London, 2013.
  * [16] R. Duan, S. Pettie, and H.-H. Su.  Scaling algorithms for weighted matching in general graphs.  ACM Trans. Algorithms, 14(1):8:1–8:35, 2018.
  * [17] E. Elkind, M. Lackner, and D. Peters.  Structured preferences.  In U. Endriss, editor, Trends in computational social choice, chapter 10, pages 187–207. AI Access, 2017.
  * [18] M. R. Fellows, D. Hermelin, F. A. Rosamond, and S. Vialette.  On the parameterized complexity of multiple-interval graph problems.  Theor. Comput. Sci., 410:53–61, 2009.
  * [19] Z. Fitzsimmons and E. Hemaspaandra.  Kemeny consensus complexity.  In IJCAI-21: Proc. of the 30th International Joint Conference on Artificial Intelligence, pages 196–202, 2021.
  * [20] A.-T. Gai, D. Lebedev, F. Mathieu, F. de Montgolfier, J. Reynier, and L. Viennot.  Acyclic preference systems in P2P networks.  In Euro-Par ’07: Proc. of the 13th International Euro-Par Conference on Parallel Processing, volume 4641 of LNCS, pages 825–834. Springer, 2007.
  * [21] D. Gale and L. S. Shapley.  College admissions and the stability of marriage.  Amer. Math. Monthly, 69(1):9–15, 1962.
  * [22] M. R. Garey and D. S. Johnson.  Computers and Intractability: A Guide to the Theory of NP-Completeness.  W. H. Freeman & Co., New York, 1979.
  * [23] S. Gupta, P. Jain, and S. Saurabh.  Well-structured committees.  In IJCAI-20: Proc. of the 29th International Joint Conference on Artificial Intelligence, pages 189–195, 2020.
  * [24] V. Guruswami, R. Manokaran, and P. Raghavendra.  Beating the random ordering is hard: Inapproximability of maximum acyclic subgraph.  In FOCS 2008: Proc. of the 49th Annual IEEE Symposium on Foundations of Computer Science, pages 573–582, USA, 2008. IEEE Computer Society.
  * [25] D. Gusfield.  The structure of the stable roommate problem: Efficient representation and enumeration of all stable assignments.  SIAM J. Comput., 17(4):742–769, 1988.
  * [26] D. Gusfield and R. W. Irving.  The stable marriage problem: structure and algorithms.  Foundations of Computing Series. MIT Press, Cambridge, MA, 1989.
  * [27] E. Hemaspaandra, H. Spakowski, and J. Vogel.  The complexity of Kemeny elections.  Theoretical Computer Science, 349:382–391, 2005.
  * [28] R. W. Irving, D. F. Manlove, and S. Scott.  The stable marriage problem with master preference lists.  Discret. Appl. Math., 156(15):2959–2977, 2008.
  * [29] N. Kamiyama.  Many-to-many stable matchings with ties, master preference lists, and matroid constraints.  In AAMAS ’19: Proc. of the 18th International Conference on Autonomous Agents and MultiAgent Systems, pages 583–591, 2019.
  * [30] R. M. Karp.  Reducibility among combinatorial problems.  In R. E. Miller and J. W. Thatcher, editors, Complexity of Computer Computations, pages 85–103. Plenum Press, 1972.
  * [31] C. S. Karthik, B. Laekhanukit, and P. Manurangsi.  On the parameterized complexity of approximating dominating set.  J. ACM, 66(5):33:1–33:38, 2019.
  * [32] J. Kemeny.  Mathematics without numbers.  Daedalus, 88:577–591, 1959.
  * [33] P. Khanchandani and R. Wattenhofer.  Distributed stable matching with similar preference lists.  In OPODIS 2016: Proc. of the 20th International Conference on Principles of Distributed Systems, volume 70 of LIPIcs, pages 12:1–12:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016.
  * [34] S. Khot.  On the power of unique 2-prover 1-round games.  In STOC 2002: Proc. of the 34th Annual ACM Symposium on Theory of Computing, pages 767–775, New York, NY, USA, 2002. Association for Computing Machinery.
  * [35] D. Lebedev, F. Mathieu, L. Viennot, A.-T. Gai, J. Reynier, and F. de Montgolfier.  On using matching theory to understand P2P network design.  In INOC ’07: Proc. of the 3rd International Network Optimization Conference, 2007.
  * [36] D. Lokshtanov, M. S. Ramanujan, and S. Saurabh.  When recursion is better than iteration: A linear-time algorithm for acyclicity with few error vertices.  In SODA ’18: Proc. of the ACM-SIAM Symposium on Discrete Algorithms, pages 1916–1933, 2018.
  * [37] D. F. Manlove.  Algorithmics of matching under preferences, volume 2 of Series on Theoretical Computer Science.  World Scientific, Singapore, 2013.
  * [38] K. Meeks and B. Rastegari.  Solving hard stable matching problems involving groups of similar agents.  Theor. Comput. Sci., 844:171–194, 2020.
  * [39] N. Perach, J. Polak, and U. G. Rothblum.  A stable matching model with an entrance criterion applied to the assignment of students to dormitories at the Technion.  Int. J. Game Theory, 36:519–535, 2008.
  * [40] I. Schlotter and Á. Cseh.  Maximum-utility popular matchings with bounded instability.  CoRR, abs/2205.02189, 2022.  arXiv:2205.02189 [cs.DM].
  * [41] V. V. Vazirani.  Approximation algorithms.  Springer, 2001.