{'fraction_non_alphanumeric': 0.05812125492697819, 'fraction_numerical': 0.010696953817411314, 'mean_word_length': 3.5363547103508863, 'pattern_counts': {'":': 0, '<': 21, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 23, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Parameterized Complexity of Stable Roommates with Ties and Incomplete Lists Through the Lens of Graph Parameters

We continue and extend previous work on the parameterized complexity analysis of the NP-hard Stable Roommates with Ties and Incomplete Lists problem, thereby strengthening earlier results both on the side of parameterized hardness as well as on the side of fixed-parameter tractability. Other than for its famous sister problem Stable Marriage which focuses on a bipartite scenario, Stable Roommates with Incomplete Lists allows for arbitrary acceptability graphs whose edges specify the possible matchings of each two agents (agents are represented by graph vertices). Herein, incomplete lists and ties reflect the fact that in realistic application scenarios the agents cannot bring all other agents into a linear order. Among our main contributions is to show that it is W[1]-hard to compute a maximum-cardinality stable matching for acceptability graphs of bounded treedepth, bounded tree-cut width, and bounded feedback vertex number (these are each time the respective parameters). However, if we `only' ask for perfect stable matchings or the mere existence of a stable matching, then we obtain fixed-parameter tractability with respect to tree-cut width but not with respect to treedepth. On the positive side, we also provide fixed-parameter tractability results for the parameter feedback edge set number.


Introduction
The computation of stable matchings is a core topic in the intersection of algorithm design and theory, algorithmic game theory, and computational social choice. It has numerous applications-the research goes back to the 1960s. The classic (and most prominent from introductory textbooks) problem Stable Marriage, which is known to be solvable in linear time, relies on complete bipartite graphs for the modeling with the two sides representing the same number of "men" and "women". Herein, each side expresses preferences (linear orderings aka rankings) over the opposite sex. Informally, stability then means that no two matched agents have reason to break up. Stable Roommates, however, is not restricted to a bipartite setting: given is a set V of agents together with a preference list P v for every agent v ∈ V , where a preference list P v is a strict (linear) order on V \ {v}. The task is to find a stable matching, that is, a set of pairs of agents such that each agent is contained in at most one pair and there is no blocking edge (i.e., a pair of agents who strictly prefer their mates in this pair to their partners in the matching; naturally, we assume that agents prefer to be matched over being unmatched). Such a matching can be computed in polynomial time [22]. We refer the reader to the monographs [20,29] for a general discussion on Stable Roommates. Recent practical applications of Stable Roommates and its variations also to be studied here range from kidney exchange to connections in peer-to-peer networks [14,37,38].
If the preference lists P v for all agents v are complete, then the graph-theoretic model behind is trivial-a complete graph reflects that every agent ranks all other agents. In the more realistic scenario that an agent may only rank part of all other agents, the corresponding graph, referred to as acceptability graph, is no longer a complete graph but can have an arbitrary structure. We assume that the acceptability is symmetric, that is, if an agent v finds an agent u acceptable, then also agent u finds v acceptable. Moreover, to make the modeling of real-world scenarios more flexible and realistic, one also allows ties in the preference lists (rankings) of the agents, meaning that tied agents are considered equally good. Unfortunately, once allowing ties in the preferences, Stable Roommates already becomes NP-hard [28,36], indeed this is true even if each agent finds at most three other agents acceptable [10]. Hence, in recent works specific (parameterized) complexity aspects of Stable Roommates with Ties and Incomplete Lists (SRTI) have been investigated [1,4,8]. In particular, while Bredereck et al. [4] studied restrictions on the structure of the preference lists, Adil et al. [1] initiated the study of structural restrictions of the underlying acceptability graph, including the parameter treewidth of the acceptability graph. We continue Adil et al.'s line of research by systematically studying three variants ('maximum', 'perfect', 'existence') and by extending significantly the range of graph parameters under study, thus gaining a fairly comprehensive picture of the parameterized complexity landscape of SRTI.
Notably, while previous work [1,19] argued for the (also practical) relevance for studying the structural parameters treewidth and vertex cover number, our work extends this to further structural parameters that are either stronger than vertex cover number or yield more positive algorithmic results than possible for treewidth. We study the arguably most natural optimization version of Stable Roommates with ties and incomplete lists, referred to as Max-SRTI:

Input:
A set V of agents and a profile P = (Pv)v∈V .

Task:
Find a maximum-cardinality stable matching or decide that none exists.

Max-SRTI
In addition to Max-SRTI, we also study two NP-hard variants. The input is the same, but the task either changes to finding a perfect stable matching-this is Perfect-SRTI-or to finding just any stable matching-this is SRTI-Existence. 1

Input:
A set of agents V and a profile P = (Pv)v∈V .

Task:
Find a perfect stable matching or decide that none exists.

Input:
A set of agents V and a profile P = (Pv)v∈V .

Task:
Find a stable matching or decide that none exists.

SRTI-Existence
Related Work. On bipartite acceptability graphs, where Stable Roomates is called Stable Marriage, Max-SRTI admits a polynomial-time factor-2 3 -approximation [33]. However, even on bipartite graphs it is NP-hard to approximate Max-SRTI by a factor of 29 33 , and Max-SRTI cannot be approximated by a factor of 3 4 + for any > 0 unless Vertex Cover can be approximated by a factor strictly smaller than two [40]. Note that, as we will show in our work, SRTI-Existence is computationally hard in many cases, so good polynomial-time or even fixed-parameter approximation algorithms for Max-SRTI seem out of reach.
Perfect-SRTI was shown to be NP-hard even on bipartite graphs [23]. This holds also for the more restrictive case when ties occur only on one side of the bipartition, and any preference list is either strictly ordered or a tie of length two [28]. As SRTI-Existence is NP-hard for complete graphs, all three problems considered in this paper are NP-hard on complete graphs (as every stable matching is a maximal matching). This implies paraNPhardness for all parameters which are constant on cliques, including distance to clique, cliquewidth, neighborhood diversity, the number of uncovered vertices, and modular width.
Following up on work by Bartholdi III and Trick [3], Bredereck et al. [4] showed NPhardness and polynomial-time solvability results for SRTI-Existence under several restrictions constraining the agents' preference lists.
On a fairly general level, there is quite some work on employing methods of parameterized algorithmics in the search for potential islands of tractability for in general NP-hard stable matching problems [1,8,9,30,32]. More specifically, Marx and Schlotter [30] showed that Max-SRTI is W[1]-hard when parameterized by the number of ties. They observed that it is NP-hard even if the maximum length of a tie is constant but showed that Max-SRTI is fixed-parameter tractable when parameterized by the combined parameter 'number of ties and maximum length of a tie'. Meeks and Rastegari [34] considered a setting where the agents are partitioned into different types having the same preferences. They show that the problem is FPT in the number of types. Mnich and Schlotter [35] defined Stable Marriage with Covering Constraints, where the task is to find a matching which matches a given set of agents, and minimizes the number of blocking pairs among all these matchings. They 1 In the following, we consider a slightly different formulation of these problems: We assume that the input consists of the acceptability graph and rank functions. This is no restriction, as one can transform a set of agents and a profile to an acceptability graph and rank functions and vice versa in linear time.
showed the NP-hardness of this problem and investigated several parameters such as the number of blocking pairs or the maximum degree of the acceptability graph. Most importantly for our work, however, Adil et al. [1] started the research on structural restrictions of the acceptability graph, which we continue and extend. Their result is an XP-algorithm for the parameter treewidth; indeed, they did not show W [1]-hardness for this parameter, leaving this as an open question. This open question was solved (also for the bipartite case) by Gupta et al. [19], who further considered various variants (such as sex-equal or balanced) of stable marriage with respect to two variants of treewidth. 2 Moreover, Adil et al. [1] showed that Max-SRTI is fixed-parameter tractable when parameterized by the size of the solution (that is, the cardinality of the set of edges in the stable matching) and that Max-SRTI restricted to planar acceptability graphs then is fixed-parameter tractable even with subexponential running time. 3 Our Contributions. We continue the study of algorithms for Max-SRTI and its variants based on structural limitations of the acceptability graph. In particular, we extend the results of Adil et al. [1] in several ways. For an overview on our results we refer to Figure 1. We highlight a few results in what follows. We observe that Adil et al.'s dynamic programmingbased XP-algorithm designed for the parameter treewidth 4 indeed yields fixed-parameter tractability for the combined parameter treewidth and maximum degree. We complement their XP result and the above mentioned results by showing that Max-SRTI is W[1]-hard for the graph parameters treedepth, tree-cut width, and feedback vertex set. Notably, all these graph parameters are 'weaker' [26] than treewidth and these mutually independent results imply W[1]-hardness with respect to treewidth; the latter was also shown in the independent work of Gupta et al. [19].
For the two related problems Perfect-SRTI and SRTI-Existence, on the contrary we show fixed-parameter tractability with respect to the parameter tree-cut width. These results confirm the intuition that tree-cut width, a recently introduced [39] and since then already well researched graph parameter [15,16,17,24,31] 'lying between' treewidth and the combined parameter 'treewidth and maximum vertex degree', is a better suited structural parameter for edge-oriented problems than treewidth is. Moreover, we extend our W[1]hardness results to Perfect-SRTI and SRTI-Existence parameterized by treedepth and to Perfect-SRTI parameterized by the feedback vertex number.
In summary, we provide a fairly complete picture of the (graph-)parameterized computational complexity landscape for the three studied problems-see Figure 1 for an overview of our results. Among other things Figure 1 for the parameter tree-cut width depicts a surprising complexity gap between Max-SRTI on the one side (W[1]-hardness) and Perfect-SRTI and SRTI-Existence (fixed-parameter tractability) on the other side. Finally, Figure 1 leaves as an open question the parameterized complexity of SRTI-Existence with respect to the parameter feedback vertex set number which we conjecture to be answered with W  Results for graph-structural parameterizations of Stable Roommates with Ties and Incomplete Lists. Max means Max-SRTI, Perfect means Perfect-SRTI, and ∃ means SRTI-Existence. The symbol ♦ indicates the existence of an FPT factor-1 2 -approximation algorithm (see Corollary 16). The arrows indicate dependencies between the different parameters. An arrow from a parameter p1 to a parameter p2 means that there is a computable function f : N → N such that for any graph G we have p1(G) ≤ f (p2(G)). Consequently, fixed-parameter tractability for p1 then implies fixed-parameter tractability for p2, and W[1]-hardness for p2 then implies W[1]-hardness for p1.

Preliminaries
For a positive integer n let [n] := {1, 2, 3, . . . , n} = {x ∈ N : x ≤ n}. We write vectors h in boldface, and access their entries (coordinates) via h(e). For a graph G and a vertex v ∈ V (G), let δ G (v) be the set of edges incident to v. If the graph G is clear from the context, then we may just write δ(v). For a subset of edges M ⊆ E(G) and a vertex v ∈ V (G), we define δ M (v) := δ G (v) ∩ M . We denote the maximum degree in G by ∆(G), i.e., ∆(G) := max v∈V (G) |δ G (v)|. For a tree T rooted at a vertex r and a vertex v ∈ V (T ), we denote by T v the subtree rooted at v. For a graph G and a subset of vertices X (a subset of edges F ), we define G − X (G − F ) to be the graph arising from G by deleting all vertices in X and all edges incident to a vertex from X (deleting all edges in F ). For a graph G and a set of vertices X ⊆ V (G), the graph arising by contracting X is denoted by G /X ; it is defined by replacing the vertices in X by a single vertex. Thus, Unless stated otherwise, n := |V (G)|, and m := |E(G)|.
We define the directed graph ← → G by replacing each edge {v, w} ∈ E(G) by two directed ones in opposite directions, i.e. (v, w) and (w, v).
Note that the acceptability graph for a set of agents V and a profile P is always simple, while a graph arising from a simple graph through the contraction of vertices does not need to be simple.
A parameterized problem consists of the problem instance I (in our setting the Stable Roommate instance) and a parameter value k (in our case always a number measuring some aspect in acceptability graph). An FPT-algorithm for a parameterized problem is an algorithm that runs in time f (k)|I| O (1) , where f is some computable function. That is, an FPT algorithm can run in exponential time, provided that the exponential part of the running time depends on the parameter value only. If such an algorithm exists, the parameterized problem is called fixed-parameter tractable for the corresponding parameter. There is also a theory of hardness of parameterized problems that includes the notion of W[1]-hardness. If a problem is W[1]-hard for a given parameter, then it is widely believed not to be fixed-parameter tractable for the same parameter.
The typical approach to showing that a certain parameterized problem is W[1]-hard is to reduce to it a known W[1]-hard problem, using the notion of a parameterized reduction. In our case, instead of using the full power of parameterized reductions, we use standard many-one reductions that ensure that the value of the parameter in the output instance is bounded by a function of the parameter of the input instance.
The Exponential-Time Hypothesis (ETH) of Impagliazzo and Paturi [21] asserts that there is a constant c > 1 such that there is no c o(n) time algorithm solving the Satisfiability problem, where n is the number of variables. Chen et al. [6] showed that assuming ETH, there is no f (k) · n o(k) time algorithm solving k-(Multicolored) Clique, where f is any computable function and k is the size of the clique we are looking for. For further notions related to parameterized complexity and ETH refer to [11].

Profiles and preferences
Let V be a set of agents. A preference list P v for an agent v is a subset P v ⊆ V \ {v} together with an ordered partition ( The size of a tie P i v is its cardinality, i.e., |P i v |. For an agent v ∈ V , the rank function is then v ties x and y. For a set V of agents, a set P = (P v ) v∈V of preference lists is called a profile. The corresponding acceptability graph G consists of vertex set V (G) := V and edge set A subset M ⊆ E(G) of pairwise non-intersecting edges is called a matching. If {x, y} ∈ M , then we denote the corresponding partner y of x by M (x) and set M ( Note that the literature contains several different stability notions for a matching in the presence of ties. Our stability definition is frequently called weak stability. 5

Structural graph parameters
We consider the (graph-theoretic) parameters treewidth, tree-cut width, treedepth, feedback vertex number, feedback edge number, vertex cover number, and the combined parameter 'treewidth + maximum vertex degree' (also called degree-treewidth in the literature).
A set of vertices S ⊆ V (G) is a feedback vertex set if G − S is a forest and the feedback edge set is a subset F ⊆ E(G) of edges such that G − F is a forest. We define the feedback vertex (edge) number fvs(G) (fes(G)) to be the cardinality of a minimum feedback vertex (edge) set of G. A vertex cover is a set of vertices intersecting with every edge of G, and the vertex cover number vc(G) is the size of a minimum vertex cover. The treedepth td(G) is the smallest height of a rooted tree T with vertex set V (G) such that for each {v, w} ∈ V (G) we have that either v is a descendant of w in T or w is a descendant of v in T .
Treewidth intuitively measures the tree-likeness of a graph. It can be defined via structural decompositions of a graph into pieces of bounded size, which are connected in a tree-like fashion, called tree decompositions.
Tree-Cut Width. Tree-cut width has been introduced by Wollan [39] as tree-likeness measure between treewidth and treewidth combined with maximum degree. A family of subsets Note that X i = ∅ is possible (even for several distinct i). A tree-cut decomposition of a graph G is a pair (T, X ) which consists of a tree T and a near-partition . A set in the family X is called a bag of the tree-cut decomposition. Given a tree node t, let T t be the subtree of T rooted at t. For a node t ∈ V (T ), we denote by Y t the set of vertices induced by T t , i.e., Y t := v∈V (Tt) X v .
For an edge e = {u, v} ∈ E(T ), we denote by T of V (G). We denote by cut(e) ⊆ E(G) the set of edges of G with one endpoint in t∈T {u,v} u X t and the other one in t∈T {u,v} v X t . A tree-cut decomposition is called rooted if one of its nodes is called the root r. For any node t ∈ V (T ) \ {r}, we denote by e(t) the unique edge incident to t on the r-t-path in T . The adhesion adh T (t) is defined as | cut(e(t))| for each t = r, and adh T (r) := 0.
The torso of a tree-cut decomposition (T, X ) at a node t, denoted by H t , can be constructed from G as follows: If T consists of a single node, then the torso of t ∈ V (T ) is G. Else let C 1 t , . . . , C t be the connected components of T − t. Let Z i := v∈V (C i t ) X v . Then, the torso arises from G by contracting each The operation of suppressing a vertex v of degree at most two consists of deleting v and, if v has degree exactly two, then adding an edge between the two neighbors of v. The torso-size tor(t) is defined as the number of vertices of the graph arising from the torso H t by exhaustively suppressing all vertices of degree at most two.
The width of a tree-cut decomposition (T, X ) is defined as max t∈V (T ) {adh(t), tor(t)}. The tree-cut width tcw(G) of a graph G is the minimum width of a tree-cut decomposition of G.
Nice tree-cut decompositions. Similarly to nice tree decompositions [25], each tree-cut decomposition can be transformed into a nice tree-cut decomposition. Nice tree-cut decompositions have additional properties which help simplifying algorithm design. Besides the definition of nice tree-cut decompositions, in the following we provide some of its properties. 6 Definition 1 ([15]). Let (T, X ) be a tree-cut decomposition. A node t ∈ V (T ) is called light if adh(t) ≤ 2 and all outgoing edges from Y t end in X p , where p is the parent of t, and heavy otherwise (see Figure 2 for an example).
Theorem 2 ([15, Theorem 2]). Let G be a graph with tcw(G) = k. Given a tree-cut decomposition of G of width k, one can compute a nice tree-cut decomposition (T, X ) of G of width k with at most 2|V (G)| nodes in cubic time. Lemma 2]). Each node t in a nice tree-cut decomposition of width k has at most 2k + 1 heavy children.
In what follows, we will assume that a nice tree-cut decomposition of the input graph is given. Computing the tree-cut width of a graph is NP-hard [24], but there exists an algorithm, given a graph G and an integer k, either finds a tree-cut decomposition of width at most 2k or decides that tcw(G) > k in time 2 O(k 2 log k) n 2 . Furthermore, Giannopoulou et al. [18] gave a constructive proof of the existence of an algorithm deciding whether the tree-cut width of a given graph G is at most k in f (k)n time, where f is a computable recursive function. Very recently, Ganian et al. [17] performed experiments on computing optimal tree-cut decompositions using SAT-solvers. the reduction of Gupta et al. [19] can, with some additional changes and work, yield hardness for these parameters as well or not. On the other hand, we use some consistency gadget which is essentially a triangle (while the graph resulting from the reduction of Gupta et al. [19] is bipartite). Furthermore, in our reduction all of the vertices have either strictly ordered preferences or a tie between (the only) two agents they find acceptable. See Appendix A for details and further comments. Note that such a maximum stable matching corresponding to a clique of size k leaves only 2k(k − 1) vertices uncovered. Thus, by adding 2k(k − 1) vertices connected to all other vertices, we also get the W[1]-hardness for Perfect-SRTI:

Corollary 8 ( ). Perfect-SRTI parameterized by treedepth and feedback vertex set is W[1]-hard.
From this, we get the W[1]-hardness of SRTI-Existence for treedepth by adding for each vertex a 3-cycle, ensuring that this vertex is matched (similarly to the 3-cycles c ij , c ij , c ij for the vertex c ij in the consistency gadgets).

Corollary 9 ( ). SRTI-Existence parameterized by treedepth is W[1]-hard.
A different reduction partially using similar ideas and techniques yields the W[1]-hardness of Max-SRTI for the parameter tree-cut width:

Tractability Results
We present an FPT-algorithm for Perfect-SRTI and SRTI-Existence. Given a tree-cut decomposition of the acceptability graph, we use dynamic programming to decide whether a solution exists or not. In the dynamic programming table for a node t we store information whether there exists a matching M for the set Y t of vertices from the bags of the subtree of the tree-cut decomposition rooted in t. We allow that M is not stable in G but require that the blocking pairs are incident to vertices outside Y t , and for some of the edges {v, w} in cut(t), we require the endpoint v in Y t to be matched at least as good as he ranks w.
DP Tables. Before we describe the idea behind the table entries we store in our dynamic programming procedure, we introduce the following relaxation of matching stability.
Definition 11. Let (T, X ) be a nice tree-cut decomposition of G. For a node t ∈ V (T ), the closure of t (clos(t)) is the set of vertices in Y t together with their neighbors, that is, We say that a matching M on clos(t) for some t ∈ V (T ) complies with a vector h ∈ {−1, 0, 1} cut(t) if the following conditions hold: for each edge e ∈ cut(t), we have e ∈ M if and only if h e = 0; for each e = {v, w} ∈ cut(t) with v ∈ Y t and h e = 1, we have rk v (M (v)) ≤ rk v (w), i.e., v ranks its partner (not being w by the previous condition) in M at least as good as w; and every blocking pair contains a vertex from V (G) \ Y t not matched in M .
Intuitively, if we set h t (e) = 1 for an edge e = {v, x} in cut(t) with x ∈ X t , then we are searching for a matching M (in G[clos(t)]) for which we can guarantee that rk x (M (x)) ≤

Figure 2
An example of a graph G (left part of the picture) and its nice tree-cut decomposition (T, X ) (not of minimal width). The vertices of G are the circles, while the nodes of T are the rectangles. For a node t ∈ V (T ), the bag Xt contains exactly those vertices inside the rectangle. In the right picture, the solid edges are the edges of T , while the dotted edges are from G. The nodes t1 and t4 are light, while t2 (because there is an edge connecting a vertex in t2 to a vertex in r) and t3 (because adh(t3) = 3) are heavy. rk x (v). Consequently, we know that e will not be blocking in an extension of such a matching. Contrary, if we set h t (e) = −1, then we allow x to prefer v over its partner (in particular, x may remain unmatched). Thus, for an extension of such a matching in order to maintain stability we have to secure that rk v (M (v)) ≤ rk v (x), since otherwise e will be blocking. Observe that if a matching complies with h for a vector h ∈ {−1, 0, 1} cut(t) with h(e) = 1 for some edge e ∈ cut(t), then it complies withĥ ∈ {−1, 0, 1} cut(t) which is the same as h but for e is set to −1 (formally,ĥ(f ) = h(f ) for f = e andĥ(e) = −1). Clearly, any matching complying with h complies withĥ, since the latter is more permissive.
For a node t ∈ T its dynamic programming table is τ t and it contains an entry for every  Proof Sketch. Let (T, X ) be a nice tree-cut decomposition of G of width k. We will first explain the algorithm for SRTI-Existence, and in the end we highlight how this algorithm can be adapted to Perfect-SRTI. We compute the values τ t [h] by bottom-up induction over the tree T .
For a leaf t ∈ V (T ) and a vector h, we enumerate all matchings M t on G[X t ∪ N (Y t )]. We check whether M t complies with h. If we find such a matching, then we store one of these matchings in τ t [h], and else set τ t [h] = . As |X t ∪ N (Y t )| ≤ 2k, and G is simple, the number of matchings is bounded by 2 O(k log k) .
The induction step, that is, computing the table entries for the inner nodes of the tree-cut decomposition is the most-involved part and sketched below.
For the root r ∈ V (T ), we have Y r = V (G) and cut(r) = ∅. Thus, a matching on Y r = V (G) complying with h r ∈ {−1, 0, 1} ∅ is just a stable matching (note that h r is unique). Hence, G contains a stable matching if and only if τ r [h r ] = .
The induction step is executed for each t ∈ V (T ) and each h ∈ {−1, 0, 1} cut(t) , and therefore at most n3 k times. As each execution takes 2 O(k log k) n O(1) time (Corollary 59), the total running time of the algorithm is bounded by 2 O(k log k) n O (1) .
To solve Perfect-SRTI, we store in any dynamic programming table τ t only matchings such that every vertex inside Y t is matched.

Induction
Step. In what follows we sketch how to solve the induction step.

Induction
Step Before we give the proof idea we first give the definition of light children classes. Intuitively, two light children of a note t are in the same class if, with respect to t, they behave in a similar way, that is, their neighborhood in X t is the same and their table entries are compatible. In order to properly define the later notion we first need to introduce few auxiliary definitions. To simplify the notation, we assume that the edges of G are enumerated, that is, we have E(G) = {e 1 , e 2 , . . . , e m }. For a vector h ∈ {−1, 0, 1} cut(t) , the i-th coordinate will always be the coordinate of the edge with the i-th lowest index in cut(t). It follows immediately that ♦ is an equivalence relation on light children of t. Furthermore, since each class of ♦ is identified by its signature and neighborhood in X t , there are O(k 2 ) classes of ♦. Let C(c) denote the equivalence class of the light child c of t and let N (C) ⊆ X t be the set of neighbors of the class C of ♦ (i.e., N (C) is the set of neighbors N (Y c ) ⊆ X t for c ∈ C). Furthermore, let sig(C) denote the signature of the class C and similarly let sig x (C) denote the signature of C with respect to its neighbor x ∈ N (C).

Observation 15.
If C is a class with |C| ≥ 3 and (−1, −1) / ∈ sig(C), then there is no stable matching in G.

Proof Idea (Induction Step).
For proof details, see Appendix C.1. First, we will guess which edges incident to heavy children are in the matching M to be computed and which are not. Note that there are at most k(2k + 1) edges incident to heavy children of t, since their adhesion is at most k. Thus, we fix a matching between vertices in X t and heavy children and what remains is to combine the guessed matching with matchings in their graphs; note that we can also guess these, however, this results in (3 k ) O(k) guesses. Instead of trying all of the possibilities we prove (Lemma 38) that it is possible to reduce the number of heavy children matchings we try to extend to k O(k) . It is worth noting that these choices will result in some further constraints the matching in the light children must fulfill.
Then for every class of the equivalence ♦ we guess whether its neighbor(s) in X t are matched to it (i.e., matched to a vertex in a child or two in this class) or not. Let N denote the guessed matching. Note that there are k O(k) such choices, since each vertex v ∈ X t is "adjacent" to at most k + 1 classes of ♦ (i.e., there are at most k classes such that v is adjacent to a vertex in all of the children contained in this class) and choosing a class (or deciding not to be adjacent to any light child) for every vertex in X t yields the claimed bound. We show that if a class of ♦ with N (C) = {x} is selected to be matched with its neighbor x, then it is possible to match x to the best child in this class (the one containing the top choice for x among these children); provided there exists a solution which is compatible with such a choice. We do this by showing a rather simple exchange argument (Lemma 39).
Having resolved heavy children and light children with only one neighbor in X t it remains to deal with children with two neighbors. We generalise the exchange argument we provide for classes with one neighbor (Lemma 41). Then, we prove that many combinations of N and a signature of a class C allows us to reduce the number of children in C in which we have to search for a partner of a vertex in N (C) to a constant (in fact, four). We call such classes the good classes. However, there are classes where this is not possible (call these the bad classes). Consequently, there are only 4 k possibilities how to match vertices in X t to good classes of children. We give a characterization of the bad classes (see Definition 51, Appendix C.1.2). Finally, using this characterisation we show how to reduce the question of existence of a (perfect) matching complying with h and obeying all the constraints of heavy children to an instance of 2-SAT (similarly to Feder [13]).
Using standard techniques and the polynomial-time algorithm for graphs of bounded treewidth by Adil et al. [1], we obtain an FPT-algorithm for Max-SRTI (and therefore also Perfect-SRTI and SRTI-Existence) parameterized by feedback edge number:

Conclusion
Taking the viewpoint of parameterized graph algorithmics, we investigated the line between fixed-parameter tractability and W[1]-hardness of Stable Roommates with Ties and Incomplete Lists. Studying parameterizations mostly relating to the 'tree-likeness' of the underlying acceptability graph, we arrived at a fairly complete picture (refer to Figure 1) of the corresponding parameterized complexity landscape. There is a number of future research issues stimulated by our work. First, we did not touch on questions about polynomial kernelizability of the fixed-parameter tractable cases. Indeed, for the parameter feedback edge number we believe that a polynomial kernel should be possible. Another issue is how tight the running time for our fixed-parameter algorithm for the parameter tree-cut width k is; more specifically, can we show that our exponential factor k O(k) is basically optimal or can it be improved to say 2 O(k) ? Also the case of SRTI-Existence parameterized by feedback vertex number remained open (see Figure 1). Based on preliminary considerations, we conjecture it to be W

A Additional Material for Section 3
In this section, we show that Max-SRTI and Perfect-SRTI are W[1]-hard for the parameters treedepth and feedback vertex set. Furthermore, SRTI-Existence is W[1]-hard for the parameter treedepth. These results also imply W[1]-hardness with respect to pathand treewidth. We will reduce from Clique which is well-known [12] to be W[1]-hard for the parameter solution size. Given an undirected graph G and an integer k, Clique asks whether G contains a clique (i.e. a complete subgraph) of size k.
Let (G, k) be a Clique-instance. The reduction contains k vertex selection gadgets, indicating the k vertices of the clique, k(k −1) incidence checking gadgets, and mk(k −1) edge gadgets. We first describe these gadgets and the reduction, and then prove the correctness of our reduction. In this section, we assume that V (G) = [n].

A.1 The gadgets
The vertex selection gadget. Fix some i ∈ [k]. Each vertex selection gadget consists of two vertices c i and c i , and for each v ∈ V (G), a path P v i of length three between them. The inner vertices s v i and s v i of such a path P v i rank both their neighbors at position 1. Vertex c i ranks s v i at position v (remember that vertices from G are also natural numbers), while c i ranks s v i at position n + 1 − v (see Figure 3 in the Appendix).
The edge gadget. The edge gadget is depicted in Figure 4. An edge gadget E e ij for an edge ji , e 2 ji , e 1 ji of length seven. Furthermore, it contains two paths P e ij and P e ji of length three, where we denote the vertices of P q by p 1 q , p 2 q , p 3 q , p 4 q (arising in this order on the path), where {i, j} = { , q}. Furthermore, there is an edge {e 3 q , p 3 q } for all { , q} = {i, j}. All these vertices rank all their neighbors tied at the first position except for e 3 q and p 3 q (e 1 q also ranks neighbors outside the edge gadget not at its top position; this will be described later). For e 3 q , we have rk e 3 q (e 4 q ) = 1, rk e 3 q (p 3 q ) = 2, and rk e 3 q (e 2 q ) = 3. For p 3 q , we have rk p 3 q (p 2 q ) = 1, rk p 3 q (e 3 q ) = 2, and rk p 3 The consistency gadget. The consistency gadget inc(i, j) for 1 ≤ i = j ≤ k consists of a 3-cycle c ij , c ij , c ij (see Figure 4, vertices c ij , c ij , and c ij ), where only c ij is connected to vertices outside the consistency gadget (these vertices are all of the form e 1 ij for an edge e ∈ E( ← → G )). We have rk cij (c i j ) = 2, rk cij (c i j ) = 3, rk cij (c i j) = 2, rk cij (c i j ) = 1, rk cij (c i j) = 1, and rk cij (c i j ) = 2, ensuring that a matching can only be stable if c ij is matched to an edge gadget (see Lemma 18).

A.2 The reduction
The Max-SRTI-instance arises from a Clique-instance (G, k) as follows: We take k vertex selection gadgets. Each pair (i, j) with i < j of two vertex selection gadgets is connected by 2m edge gadgets (for each edge e of ← → G , an edge gadget E e ij ), and two consistency gadgets inc(i, j) and inc(j, i) (making sure that the selected edge is incident to the selected vertex). Vertex c ij is connected to vertex e 1 ij for all edges e ∈ E(G). Vertex c ij ranks vertex e 1 ij at position 1, vertex c ij at position 2, and c ij at position 3, while the vertices e 1 ij rank c ij at their last position (4). Furthermore, for each e = (v, w) ∈ E( ← → G ), the vertices c i and c i are connected to the vertices e 1 ij for i < j, ranking them at position v respectively n + 1 − v, and e 1 ji for j < i, ranking them at position w respectively n + 1 − w, while e 1 ij for i < j and e 1 ji for j < i rank c i at position 2 and c i at position 3. This is depicted in Figure 4. The intuition behind the vertex selection gadgets is as follows: If c i and c i are matched to different 3-paths P v i and P w i , then this leaves two unmatched vertices in the vertex selection gadget, and thus the matching is not large enough. If now c i and c i are matched to the same path P v i , then this corresponds to selecting v to be a vertex of the clique (e.g. the green edges in Figure 3 correspond to selecting vertex 1 to be part of the clique).
The consistency gadgets now ensure that the selected vertices are indeed connected in G. Each consistency gadget inc(i, j) has to match c ij to some e 1 ij . The connection between the consistency, vertex and edge gadgets ensure that e then is indeed adjacent to the vertex selected by c i . The edge gadgets are constructed in such a way that matching c ij and c ji to the same edge gadget results in a larger matching, and thereby ensuring that all vertices selected by the vertex selection gadgets are adjacent.
Let H be the graph constructed from G as above. Before proving the correctness of our reduction, we analyze the structure of stable matchings in H. First, we show that any stable matching has to match the vertices c ij from the consistency gadgets to edge gadgets.
. In this case, at least one of the vertices c ij , c ij , and c ij is not covered by M . It is easy to see that the unmatched vertex constitutes to a blocking pair together with one of the other two vertices.
ji } (the green edges in Figure 4)  ij , e 4 ji }, it follows that M contains at most five edges inside this gadget. As this is matching is indeed stable, M contains exactly five edges from the edge gadget.
This now allows us to get an upper bound on the size of any stable matching, and gives us sufficient and necessary conditions for a stable matching to match the upper bound.

Lemma 20. Any stable matching in H contains at most
Proof of Lemma 20. We know, by Lemma  ij , e 2 ij } / ∈ M for these edge gadgets, and therefore at least + k(k − 1) edges of the form {e 1 ij , e 2 ij } are not contained in M . Therefore, the number of edges in the subgraph spanned by the consistency and edge gadgets is at most Together with the edges of the form {c i , e 1 ij } ∈ M or {c i , e 1 ij } ∈ M , there are at most (k − 2 )(n + 1) + 2 n + = k(n + 1) + 2 edges incident to vertex selection gadgets.
Thus, the total number of edges is at most Therefore, has to be zero, i.e. we know that M contains no edge of the form ij }, and all inequalities have to be equalities. Thus, M contains exactly n + 1 edges inside each vertex selection gadget. One easily sees that all matchings of size n + 1 inside the vertex selection gadgets are of the form We are now ready to prove the correctness of our reduction, the proof consisting of Propositions 21 and 22.
Proposition 21. If G is a contains a clique of size at least k, then H contains a stable matching of size k(n + 1) + 8mk(k − 1) + k 2 . Proof. We construct a stable matching M of the desired size. At the beginning, let M = ∅. Let It is not hard to check that the matching M is stable.

Proposition 22.
If H contains a stable matching of size at least k(n+1)+8mk(k −1)+ k 2 , then there is a clique of size k in G.

Proof of Proposition 22.
Let M be a maximum stable matching of size at least k(n + 1) + 8mk(k − 1) + k 2 . By Lemma 20, we know that for each i ∈ Let e ∈ E( ← → G ) such that {c i , e 1 ij } ∈ M (such an edge exists by Lemma 18). By Lemma 20, this implies that also {c j , e 1 ji } ∈ M . We claim that e is incident to x i . Assume that e is not incident to x i . Let v be the vertex such that e 1 ij is ranked at position v by c i . As v = x i , this implies that α := rk ci (e 1 ij ) − v = 0. As rk ci (e 1 ij ) − (n + 1 − v) = −α, this implies that either {c i , e 1 ij } or {c i , e 1 ij } is a blocking pair, a contradiction. Thus, e is incident to x i , and-by symmetry-also to x j , and the lemma follows.  However, this can easily be seen: After removing c ij and c ji , the resulting graph is a forest, whose components are egde gadgets and single edges ({c ij , c ij }). We can now construct a tree of height five on each edge gadget as follows: e 4 ij is the root, and has children p 3 ij and p 3 ij . For { , q} = {i, j}, the vertex p 3 q has children p 2 q , e 2 q , and p 4 q . The vertex p 2 q has the leaf p 1 q as its only child. The vertex e 2 q has the children e 3 q and e 1 q . Finally, the vertex e 3 ji has the child e 4 ji . This shows that the treedepth of an edge gadget is most five (see Figure 5). As after removing the vertices c ij and c ji from C ij all connected components are edge gadgets or just a single edge, this shows that C ij has treedepth at most seven.
Thus, H has treedepth at most 2k + 7. As shown by Chen et al. [7], Clique does not admit an f (k)·n o(k) -algorithm unless ETH fails. Since the treedepth of our constructed graph depends linearly on the clique size, Max-SRTI cannot admit an f (k) · n o(td(G)) -algorithm unless ETH fails.
We will now strengthen this result: First, we show that we the W[1]-hardness holds even if each preference list is either strictly ordered or a tie of length 2. Then we will show that also Perfect-SRTI and -only for the parameter treedepth -SRTI-Existence are W[1]-hard.
To show W[1]-hardness if all preference lists are strictly ordered or contain ties, we modify the reduction to get rid of all ties longer than 2 by replacing the tie by an arbitrary strict order.

Definition 23.
Let v be an agent, and let X i be a tie. Let σ : [|X i |] → X i be an bijection. The preference list (Y 1 , . . . , Y ) obtained by breaking the tie X i by σ is defined as follows: We say that a tie is broken arbitrarily if σ is chosen arbitrarily.
Lemma 24. Let (G, (rk v ) v∈V (G) ) be a Max-SRTI-instance. Let v be a vertex such that the preference list of v contains a tie X i , and σ : [|X i |] → X i be an bijection. Let (G, (rk x ) x∈V (G) ) be the preference list arising by breaking the tie X i by σ.
Then any stable matching M with respect to (rk x ) x∈V (G) is also stable with respect to (rk x ) x∈V (G) .
Proof. Assume that M is not stable with respect to (rk x ) x∈V (G) . Then there must exists a blocking pair {x, y}. Clearly, this blocking pair must contain v, so assume x = v, and y ∈ X i , as all other preferences did not change. Furthermore, M must contain an edge {v, z} with z ∈ X i by the same argument.
However, rk v (y) = rk v (z), as both y ∈ X i and z ∈ X i . Thus, {x, y} is not a blocking pair with respect to (rk x ) x∈V (G) , a contradiction. Claim 26. If one breaks the ties occurring at c ij arbitrary, the reduction still works.
Proof. The matching constructed in the proof of Proposition 21 is still stable. To see this, consider a vertex c ij which is matched to a vertex e 1 ij for some e ∈ E( Then for all ij is matched to f 2 ij and thus prefers its partner over c ij . By Lemma 24, Lemma 20 still holds, and thus, Proposition 22 still holds.
Then G has a perfect stable matching if and only if G has a stable matching of size n−k 2 .
Proof. (⇒) Let M be a perfect stable matching in G , and let M be its restriction to G. Assume that M contains a blocking pair {v, w}. Then {v, w} is also a blocking pair in M , as both v and w can only be unmatched or matched to a vertex in X in M , but prefer being matched to each other to both of these options.
As |M | + k ≥ |M |, M can leave at most k vertices uncovered. By assumption, this implies that M leaves exactly k vertices uncovered, implying that |M | = n−k 2 .
Then M clearly is a perfect matching, so it remains to show that M is stable.
Assume that there exists a blocking pair {x a , v j } containing a vertex x a ∈ X. The vertex v j cannot be matched in M , as otherwise it prefers M (v j ) over x a . Thus, v j = v i for some 1 ≤ = a ≤ k. As x a prefers v j over v ia , we have < a. As v j prefers x a over x , we have a < , a contradiction.
Thus, any blocking pair for M is contained in G and thus also a blocking pair for M .
Proof of Corollary 9. By the Corollary 8, we know that Perfect-SRTI parameterized by treedepth is W[1]-hard, even if each preference list is either strictly ordered or a tie of length 2.
Let G be an Perfect-SRTI-instance. We define an SRTI-Existence instance as follows: We call the resulting instance G .
Claim 29. If G has a perfect stable matching, then G has a stable matching.
Proof. Simply add all edges {v , v }. It is easy to see that this adds no blocking pairs. Claim 30. If G contains a stable matching M , then G contains a perfect stable matching.
Proof. If there is some v ∈ V (G) which is not matched to a vertex in V (G), then there has to be an unmatched vertex in {v, v , v }. It is easy to see that this vertex forms a blocking pair together with another vertex of {v, v , v }.
So each v ∈ V (G) is matched to a vertex in V (G). Let M be the restriction of M to V (G). Then M is a perfect matching, so it remains to show that M is stable.
Assume that there is a blocking pair {v, w}. However, v and w are ranked the same in M , and thus, this implies a blocking pair for M , contradiction.
It remains to show that the treedepth of is bounded by k := td(G). So consider a sequence S 1 , S 2 , . . . , S k of subsets of vertices such that deleting the sets S i in the i-th recursion shows that td(G) ≤ k. When deleting the same vertices from G , we end up with n triangles, each of which has treedepth 2. Noting that no two vertices from the same connected component are deleted in any iteration, and thus td(G ) ≤ k + 2.

B W[1]-hardness of Max-SRTI for the parameter tree-cut width
In this section, we show the W[1]-hardness of Max-SRTI for the parameter tree-cut width. As in the previous chapter, we will reduce from Clique. Thus, let (G, k) be an instance of Clique. Again, the reduction contains several gadgets. We will describe these gadgets first, then the reduction and finally prove its correctness.

B.1 The gadgets
As in the W[1]-hardness proof for treedepth and feedback vertex number, the reduction contains vertex selection gadgets and edge gadgets. However, they work in a different way than those for treedepth and feedback vertex number. Consistency gadgets are not required, but there will be "incidence vertices" and a "parallel-edges gadget". We start describing the reduction by describing the gadgets, starting with the parallel-edges gadget.

B.1.1 The parallel-edges gadget
Our reduction will use parallel edges; however, parallel edges are not allowed in the Max-SRTI-problem. We will use a result from Cechlárová and Fleiner [5], showing that parallel edges can modelled in an Max-SRTI-instance:

Lemma 31. One can model parallel edges in a (Max)-SR(T)I-instance by 6-cycles with two outgoing edges (see Theorem 2.1 from [5]).
The gadget one can use to replace such an edge is depicted in Figure 6; we call it a parallel-edges gadget.
By Lemma 31, we can use parallel edges, and we will do so from now on.

B.1.2 The vertex selection gadget
We now describe the vertex-selection gadget. The gadget has a special vertex c i , which is the only vertex which has connections outside the vertex-selection gadget. The vertex-selection gadget also contains a vertex-gadget for each vertex u ∈ V (G). In any stable matching, c i has to be connected to one of the vertex-gadgets. The worse c i is matched, the more edges will be contained in the vertex-gadget. We first describe the vertex-gadget.

Furthermore, the gadget can be constructed in time O(j) and has tree-cut width at most 4.
We call such a gadget a (j, c i , )-vertex gadget. Proof. The gadget can be seen in Figure 7. It contains a 3-cycle containing w and two other vertices w and w , and a vertex c connected to w. The vertex c again is connected to the vertex p q2 of the 3-path p q1 , p q2 , p q3 , p q4 for q ∈ [j]. The preferences are shown in Figure 7.
Let M be a maximum stable matching. First, note that avoiding a blocking pair in the 3-cycle forces vertex w to be matched to c or c i , and that the vertices w and w have to be matched together, i.e. {w , w } ∈ M .
(i) By the above observation, the matching must contain the edge {w, c}. As this is one of w's top choices, {c i , w} is not a blocking pair. To avoid a blocking pair {c, p i2 } for 1 ≤ i ≤ j, we have to take edge {p i2 , p i3 } for all 1 ≤ i ≤ j, yielding in total j + 2 edges (the yellow and violet edges in Figure 8). As this matching is maximal, no stable matching not containing {c i , w} can contain more edges.  Figure 7). One easily checks that this results in a stable matching leaving only p 11 uncovered, and thus, no matching can contain more edges. Therefore, M contains 2j + 2 edges.
The size of the gadget is obviously linear in j. It remains to show that the tree-cut width is at most 4. To see this, we give a tree-cut decomposition. The tree is a star with j leaves, where the center contains {w, w , w , c}, while the j-th leaf contains the vertices {p q1 , p q2 , p q3 , p q4 } for q ∈ [j]. Thus, we have adh(t) ≤ 1 for all t ∈ V (T ). Furthermore, the 3-center of each torso is just the bag itself. Thus, the tree-cut width is at most 4.
From this, we construct a vertex-selection gadget as follows. For each j ∈ [n], we add a (2j − 1, c i , C + j(k − 1))-vertex gadget for a sufficiently large C, depending polynomially in n, ensuring that c i has to match to one of those vertex gadgets. More precisely, we define C := (14 + 6n)mk(k − 1) + 8k(k − 1)(n − 1).
It is easy to see that the tree-cut width of a vertex-selection gadget is at most four, since one can construct an according tree-cut decomposition by taking a bag {c i } as the root, and adding for each vertex-gadget a tree-cut decomposition of width four, where the root of this tree-cut decomposition is a child of {c i }.
Now we turn to the edge gadgets:

B.1.3 The edge gadget
The idea behind the edge gadgets is that if the vertex c i of a vertex-selection gadget is ranked "bad", then there are so-called incidence vertices c ij which have to be ranked "good" in order to avoid a blocking pair {c i , c ij }, and thus, a stable matching contains "few" edges inside this edge gadget, compensating the fact that the matching contains "many" edges inside the vertex-selection gadget. Finally, if c ij and c ji do not match to the same edge gadget, then this matching contains one edge less than if they would match to the same gadget. We now proof that the edge gadget has the desired properties.

Furthermore, the gadget can be constructed in O(k 1 + k 2 ), and {v i , w i } is not a blocking pair in any of the three cases, even if v i is unmatched.
We call such a gadget a (v 1 , j 1 , k 1 , v 2 , j 2 , k 2 )-edge gadget. The vertex v 1 (which is not part of the gadget) is called left neighbor, while vertex v 2 (which is also not part of the gadget) is called right neighbor.
Proof. An example of the gadget is depicted in Figure 8. Generally, a (k 1 , k 2 )-gadget consists of a path w 1 , x 1 , y 1 , y 2 , x 2 , w 2 of length 5, where the end vertices w 1 and w 2 of the path are connected to the outgoing edges e 1 and e 2 . For each w i , there exists also two vertices w i and w i which form a triangle together with w i . The vertex x i is connected to k i paths p i j1 , p i j2 , p i j3 , p i j4 of length 3. More precisely, x i is connected to p i j2 for 1 ≤ j ≤ k i . The preferences can be seen in Figure 8.
Obviously, the gadget can be constructed in time linear in k 1 + k 2 . Let M * be a maximum stable matching. If M * (w i ) / ∈ {v i , x i }, then one of the vertices w i , w i and w i is unmatched in M * . It is easy to see that this unmatched vertex forms a blocking pair with another vertex of this triangle, so we may assume that w i is matched to We define a matching for each of the three cases as follows: We assume without loss of generality that e 1 is contained in a maximum stable matching.
Thus, M cannot contain more than 6 + 2k 1 + 2k 2 edges with at least one endpoint in the gadget in case (i), 5 + 2k i + k 3−i edges with at least one endpoint in the gadget in case (ii), and 5 + k 1 + k 2 edges with at least one endpoint in the gadget in case (iii).
As the sizes of M 1 , M 2 and M 3 match these upper bounds, the upper bounds are tight. It remains to show that the resulting graph has bounded tree-cut width. This can be seen by considering the following tree-cut decomposition (see Figure 8): T is a star, and the center corresponds to {w i , w i , w i , x i , y i }, while each 3-path is a leaf, showing that the tree-cut width is at most 10. The connection between a vertex xi and the incidence vertex xij.

B.2 The reduction
We are now ready to describe our reduction from Clique. Let (G, k) be a Clique-instance.
To simplify notation, we assume that V (G) = [n]. The Max-SRTI-instance contains k vertices c 1 , . . . , c k , each of whom is connected to k − 1 incidence vertices c ij for i = j. Each vertex c i is connected to an incidence vertex c ij by n − 1 parallel edges (see Figure 9). They are ranked at position 2l at c i and at position 2(n − l) at c ij for 1 ≤ l ≤ n − 1.
Two incidence vertices c ij and c ji with i < j are connected by 2m edge gadgets (for each . This means that for any edge e = (v, w) ∈ E( ← → G ) and each 1 ≤ i < j ≤ k, we add an edge gadget, where c ij ranks the edge gadget at position 2(n − v) + 1, and c ji ranks the edge gadget at position 2(n − w) + 1.
For each i ∈ [k] and j ∈ [n], we add a (2j − 1, c i , C + j(k − 1))-vertex gadget for a sufficiently large C, depending polynomially in n, ensuring that c i has to match to one of those vertex gadgets. More precisely, we define C := (14 + 6n)mk(k − 1) + 8k(k − 1)(n − 1), as this is an upper bound on the number of edges not contained in vertex gadgets (the first summand arises from the edge gadgets, and the second summand from the parallel-edges gadgets).
We call the resulting graph H. The intuition behind the reduction is the following: As C is sufficiently large, each c i matches to a vertex gadget, corresponding to a vertex x i . This corresponds to selecting x i to be part of the clique. The incidence vertices c ij then have to match to edge gadgets. By Lemma 33, it is better to match c ij and c ji to the same edge gadget than to different ones, so the matching is only large enough if c ij and c ji match to the same edge gadget. The parallel edges between c i and c ij ensure that c ij is matched at rank at most 2(n + 1 − x i ). Thus, c ij must match to an edge gadget corresponding to an edge e = {v, w} with v ≤ x (remember that V (G) = [n], and thus there is a natural order on V (G)). If v < x, then the edge gadget contains less edges, and therefore in any stable matching which is large enough, To keep the calculations simpler, we define κ to be the sum over all edge, parallel-edges and vertex gadgets of the minimum number of edges any maximum stable matching contains inside them, assuming that at least one stable matching exists (i.e., for any j-vertex gadget, we add 2j + 2 to κ, for each parallel-edges gadget, we add 3, and for each (k 1 , k 2 )-edge gadget, we add 5 + k 1 + k 2 ). Thus, if we define κ (k1,k2) to be the number of (v 1 , j 1 , k 1 , v 2 , j 2 , k 2 )-edge gadgets contained in H, then we have κ := k n(C + 2) + (k − 1) n(n + 1) 2 + 3k(n − 1) + (k1,k2)∈N 2 where the first summand arises from the vertex gadgets, the second from the parallel-edges gadgets (a stable matching in such a gadget contains at least 3 edges) and the third from the edge gadgets. If a gadget contains more edges than the minimum number of edges any stable matching must contain inside the gadget, then we say that the gadget has additional edges.

Proof.
The edge ranked at position 2l − 2 by i is preferred by c i , and ranked at position 2(n − ) + 2 by c ij . However, as c i is not matched to c ij , the rank at c ij is not 2(n − ) + 2, and thus is at most 2(n − ) + 1 Proof. Let M be a stable matching of size at least κ + k(k − 1)(n + 0.5) + kC.
As C is lower bounded by the number of edges not contained in vertex gadgets, there are less than C additional edges outside vertex gadgets. Thus, any stable matching containing at least kC additional edges must match any vertex c i to a vertex gadget. Thus, we can assume that c i is matched to the vertex gadget corresponding to some vertex x i . This yields C + x i (k − 1) additional edges for vertex c i .
Consider any (c ij , 2k 1 +1, k 1 , c ji , 2k 2 +1, k 2 )-edge gadget between two incidence vertices c ij and c ji with i < j. If the edge {c ij , w 1 } ∈ M , then we charge k 1 edges to c i , and if {c ji , w 2 } ∈ M , we charge k 2 edges to c j . If both {c ij , w 1 } and {c ji , w 2 } are contained in M , then we additionally charge half an edge to c ij and c ji .
Then clearly the sum over all additional edges in edge gadgets equals the sum of charged edges.
We know that c i is matched at rank 2x i −1, and yields C +x i (k−1) additional edges. Thus, by Lemma 34, we know that any incidence vertex c ij is matched at rank at most 2(n − x i ) + 1. Thus, the incidence vertex c ij is matched to a (c ij , 2k 1 + 1, k 1 , c ji , 2k 2 + 1, k 2 )-edge gadget with k 1 ≤ (n − x i ) and k 2 ≤ n − x j . Therefore, there are at most n − x i edges charged to any c ij , and n − x j edges charged to c ji . Thus, for any fixed i, the sum of edges charged to c i and c ij for j = i is at most Proof of Theorem 10. The reduction is already described above.
Claim 36. If G has a clique of size k, then H has a stable matching of size at least Proof. Assume that G contains a clique {x 1 , . . . , x k }. We match c i to vertex gadget corresponding to x i , and the incidence vertices c ij to the edge gadgets corresponding to the edge (x i , x j ) ∈ E( ← → G ) between c ij and c ji . Inside each gadget, we apply Lemma 33 (i) and (iii) and take the maximum number of edges of a stable matching inside the gadget, assuming that the outgoing edges are contained if and only if they have already been added to the matching.
By Lemma 35, the matching has size κ + k(k − 1)n + k(k−1) 2 + kC if it is stable, so it remains to show that M is stable.
Note that the vertex and edge gadgets are constructed in such a way that none of their vertices is part of a blocking pair.
Thus, the blocking pair must contain a vertex from a parallel-edges gadget. We picked the edges inside the parallel-edges gadgets in a way such that no blocking pair contains two vertices inside a parallel-edges gadget. Thus, an parallel-edge gadget for an edge e = {c i , c ij } contains a blocking pair if and only if both c i and c ij prefer e over their partner. But this is not blocking as we connected c ij to an edge gadget corresponding to an edge ending in the vertex selected by c i .
Claim 37. If H contains a stable matching of size κ + k(k − 1)n + k(k−1) 2 + kC, then G contains a clique of size k.
Proof. By Lemma 35, we know that each c i is matched to a vertex gadget, each incidence vertex is matched to an edge gadget whose endpoint corresponds to the vertex selected by the vertex selection gadget, and the incidence vertices c ij and c ji are matched to the same edge gadget.
Let x i be the vertex selected by c i . Thus, for each i = j, the incidence vertex c ij matches to an edge gadget corresponding to an edge adjacent to x i , and the vertex c ji matches to an edge gadget corresponding to an edge adjacent to x j , and these edge gadgets are the same, implying that G contains the edge {x i , x j }. Thus, {x 1 , . . . , x k } forms a clique.
It remains to show that the graph has bounded tree-cut width. So consider the following tree-cut decomposition: Let T be a star containing a leaf for each gadget. The bag corresponding to the center consists of {c 1 , . . . , c k } ∪ {c ij : i = j}. Replace all leaves by the tree-cut decompositions of the gadgets. The center shall be the root of this tree-cut decomposition.
We claim that the resulting tree-cut decomposition has width at most k := max{k 2 , 10}. Obviously each bag contains at most k vertices. For the center, the torso size is k 2 . For each other node, it is at most 10 (the maximum tree-cut width of a gadget), as the component containing the center gets contracted or suppressed. The adhesion of the center is 0, and for all other nodes, the adhesion is bounded by 10. Thus, we have tcw(H) ≤ k .

C
Missing Parts from Proof of Theorem 13

C.1 The induction step
In this section, we show how to solve the induction step.

C.1.1 The heavy children
Lemma 38. Let t ∈ V (T ) be a non-leaf node, let H be the set of its heavy children, and let h ∈ {−1, 0, 1} cut(t) be given.

There exists a family H of vectors of the form g c,cut(c)
c∈H of size k O(k) , where k = tcw(G) such that the following holds. If there exists a matchingM ⊆ E(Y t )∪cut(t) complying with h, then there exists a matching M complying with h for which there exists g ∈ H such that τ c [g c ] = M ∩ (Y c ∪ cut(c)) holds for every c ∈ H.
Proof. By Lemma 3 node t has at most 2k + 1 heavy children. Thus, for each vertex v ∈ X t , there are O(k 2 ) possibilities (as adh(c) ≤ k for each c ∈ V (T )) to match this vertex to a vertex w contained Y c for a heavy child c, resulting in O(k 2 ) k = 2 O(k log k) possibilities for all x ∈ X together.
We generate the family H in two phases. In the first phase we fix the edges matching a vertex x ∈ X t to a vertex in a heavy child (we have already observed there are 2 O(k log k) possibilities for this). Note that with this we fix the zeroes of the vector g. Furthermore, since we know the x-rank of the partner of x, there is a unique way of assigning −1 or 1 to other edges between x and other vertices in heavy children. Thus, in the second phase we have to pad the so far constructed vector with −1's and 1's for the unmatched vertices in X t . Let x ∈ X t be a vertex that is not matched in the first phase and consider the set of x-ranks of neighbors of x in X c for all c ∈ H, that is, the set r Observe that if for an edge {x, y} we decide that y must be matched to a better partner than x as otherwise the edge {x, y} will be blocking the stability of the target matching, then we have to decide the same for all other possible partners of x that are ranked above y by x (since if x is willing to switch to y, it is clearly willing to switch to any better possible partner). Thus, we have to split the neighbors of x into two groups such that x is (eventually) matched to a partner which it ranks strictly below (any vertex in) the first group and at least as good as (any vertex in) the second group. We stress here that we split the set in the way that if y, y are neighbors of x in heavy children and y is the first group and rk x (y ) ≤ rk x (y), then y is in the first group. Clearly, for an edge e = {x, y} with y ∈ Y c in the first group we set g c (e) = −1, while for an edge e = {x, y} with y ∈ Y c in the second group we set g c (e) = 1. As we ha already seen that |r x | ≤ k 2 , this gives at most k 2 choices of the padding per vertex in X t , that is, k O(k) in total. Thus, there are k O(k) choices in the first stage and k O(k) choices for padding in the second phase which yields a family H of size k O(k) . The claimed properties then follow from the discussion above.

C.1.2 The light children
We start with the formal description on the node-to-children matching N .
Auxiliary node graph. For a node t we define an auxiliary node graph H t to be a bipartite graph with one side of the bipartition X t and the other side contains a vertex z C for each class C and each z ∈ X t with z ∈ N (C). There is an edge z, z C whenever z ∈ N (C). Now, let N be a matching in H t and let us slightly abuse the notation and write N (z) = C if z, z C ∈ N . Furthermore, if a vertex x ∈ X t is unmatched in N , we write N (x) = ⊥.
As described in the proof idea, we enumerate all k O(k) matchings N in H t . We will therefore from now on fix such a matching N , and try to find a matching obeying N (and of course complying with h). Formally, we are looking for an embedding of N in the graph G complying with h. We say that a matching M is an h-embedding of N if M complies with h and there is an edge z, z C ∈ N if and only if {z, z c } ∈ M for some z c ∈ V (Y c ) for some c ∈ C.
Let us denote by E(C) the set of edges c∈C (E(Y c ) ∪ cut(c)), and by V (C) the vertex set c∈C V (Y c ). Similarly, we denote by cut(C) the set of edges c∈C cut(c). Let x ∈ X t and C be a class with x ∈ N (C). We define best(C, x) ⊆ V (C) to be the set of vertices v minimizing rk x (v) among all v ∈ V (C). Singleton Children. We will first show how to deal with a class C of light children which have only one neighbor in X t . More precisely, we will show that there exists a children c ∈ C such that from any matching M complying with a vector h and containing an edge from cut(C), we can performing a "local" exchange and get a matching M containing an edge from cut(c) and also complying with h. That the exchange is "local" here means that we exchange only edges from E(C). This locality allows us to apply similar lemmata (Lemma 43 to Corollary 50) for other kinds of classes, getting the properties from these lemmata simultaneously. Proof. For each edge e = {v, x} ∈ cut(C) and each child d ∈ C, we define  (M (x)). Let c be the child such that M (x) ∈ Y c . We define It remains to show that M ∆F complies with h. The second and third condition obviously follow from M complying with F , as M and M ∆F only differ on V (C)∪{x}, and rk x (M (x)) ≥ rk x ((M ∆F )(x)). Since M and M ∆F coincide on Y t \ V (C) ∪ {x} , any blocking pair must contain a vertex from V (C) ∪ {x}.
Since rk x ((M ∆F )(x)) ≤ rk x (M (x)) and M complies with h, any blocking pair must be contained in V (C) ∪ {x}. Since (M ∆F ) ∩ E(Y d ) complies with h d,e for each d ∈ C, there is no blocking pair contained inside Y d for all d ∈ C. Thus, any blocking pair contains the vertex x, and an edge {x, But from the definition of h d,e it follows that {x, x d } is not a blocking pair.

Good classes.
We are now left with classes of light children C for which we know |N (C)| = 2 (of course, for the fixed node t). In the rest of this section we will have N (C) = {x, y} and we assume that for a light child c ∈ C we have cut(c) = {{x, x c }, {y, y c }}, that is x c ∈ Y c is the end vertex of the edge in cut(c) whose other end is the vertex x ∈ X t . Since we are going to reduce the number of children in each class to at most four, we may assume (by Observation 15) that (−1, −1) ∈ sig(C) in the following.
Exchange Lemma. We start by proving a technical lemma which gives a sufficient condition to perform certain exchanges of matching edges. This then allows us to simplify some further reasoning. Before we do so we formally define the notion of a (feasible) exchange. Denote by cut(C) = c∈C cut(c) the set of edges with one endpoint in N (C) and the other endpoint in Y c for some c ∈ C.
Definition 40. Let C be a class of light children, and let M * be a matching complying with some vector h ∈ {−1, 0, 1} cut(t) . Assume that F = M * ∩ cut(C). Let F ⊆ cut(C) such that F contains an edge incident to an x ∈ N (C) if and only if F contains an edge incident to x.
For each e = {v, x} ∈ cut(c) ∩ δ(x) for some c ∈ C and x ∈ N (C), we define The matching M arising from M * by exchanging the edges F and F is defined as follows: Delete all edges with one endpoint in Y c for some c ∈ C, and add for each c ∈ C, the matching The The following definition of signature with respect to a neighbor of a child will help us when distinguishing good and bad children. The idea is to capture when it is possible to require that one of the edges between a node and a child is not preferred by it end contained in the child. That is, it gives the information what can we do for one edge given that the other edge cannot be blocking even if it is preferred by its endpoint in the node (i.e., it gives the weakest condition on a possible extension). We will now show for most of the classes, that we can restrict the classes to contain at most four children.
We define the vector h M,c associated with a child c and a matching M by (for z = x and z = y) We distinguish six cases for a class C and a vertex x ∈ N (C), depending on the signature: Note that the cases sig x (C) = {1} and sig x (C) = {0, 1} are not possible, as any matching complying with h(e) = 1 also complies with h(e) = −1 (we stress here that the conditions we impose on a matching by setting h(e) = 1 are stronger than those imposed by h(e) = −1).
Assume that for each x ∈ X, we knew to which class M (x) belongs, but not which vertex M (x) is exactly. That is, N (x) is known, whereas M (x) is yet to be computed. We will now show that in many cases, we can then choose at most three vertices, such that there exists a solution matching x to one of the three vertices if there exists such a matching for N complying with h. Thus, these classes will be called "good classes", while the other classes will be called "bad classes". We now first show how to deal with the good classes, and afterwards show how to deal with the bad classes.
For Lemma 41-53, we assume that the considered class C contains at least three nodes, as otherwise the statement of these lemmata is trivial. Furthermore, for any vector h, the first coordinate will always denote an edge incident to x, and the second coordinate an edge incident to y.
Let C be a class of children with N (C) = {x, y}. For a child c ∈ C we define rk x (c) = rk x (x c ); similarly we define rk y (c). We say that a matching M is valid in the node t for the We claim that the matchingM arising from M by exchanging the edges {x, x d } and {x, x c } is also an h-embedding of N . Note that if this is true, then we are done, since we have found the child c we were looking for. By Lemma 41, it is enough to show that the exchange is feasible. By the existence of M , we have that τ g [(0, −1)] = for all g ∈ C. If now |C| > 1, we also have τ g [(−1, −1)] = for all g ∈ C (if |C| = 1, we are done immediately).
Note thatM (y) = M (y), and thus for all g ∈ C, we have rk y (g) < rk y (M (y)) if and only if rk y (g) < rk y (M (y)). Thus, for each g ∈ C and the vector hM ,g associated withM , we have hM ,g ({y, y g }) = h M,g ({y, y g }) for g ∈ C.
Clearly Doubly matched children. The last sets of good children classes we are going to characterise and deal with is a bit different from the previous, namely, we will assume that N (x) = N (y) = C hold for these classes. Note that this result in the fact that we have to take whole signature into consideration.
We first consider the case that (0, −1) ∈ sig(C) and (−1, 0) ∈ sig(C). We start the reduction of C by setting C = C and we successively delete elements from C until C fulfills the first condition of the lemma. As long as this is not true, there exist two children c = d ∈ C with rk x (x c ) ≤ rk x (x d ) and rk y (y c ) ≤ rk y (y d ). Such children c and d can clearly be found in polynomial time if they exist and if we find such a pair of children, we delete d from C . Now, let d ∈ C \ C and let c be the node because of which we have deleted d in the above procedure. Let M be an h-embedding of N containing the edges {x, x d } and {y, y d }. We claim that if we exchange edges {x, x d } and {y, y d } with {x, x c } and {y, y c }, then the resulting matching M also is an h-embedding of N . Clearly, such an exchange is possible, since F : gives us the sought local exchange. Note that the two table entries used are nonempty. Now, observe that the x-ranking (y-ranking) of their partner in M ∆F is not worse than the ranking of their partner in M . Since there is no other change for the other children in C, we are done. Proof. Let M be the assumed matching and suppose for a contradiction that y c / ∈ best(C, y). Let d ∈ C be a child with y d ∈ best(C, y). Proof. We assume without loss of generality that −1 / ∈ sig y (C). By Lemma 48, we may assume that there is a single child c ∈ best(C, y). Now, by Lemma 49, we get that any matching complying with h must contain the edge {y, y c }. Furthermore, we have already observed that this implies that the edge {x, x c } is contained in such a matching as well.
From now on we distinguish three types of classes: All other classes C with N (x) = C for some x ∈ X t are called good. Finally, the remaining classes are called unmatched.
Before we move further and discuss how to proceed from this point on we first give some more intuition behind the bad classes, since their description is somewhat technical. In the first case we take the advantage from Lemma 48 for such a class C; by this lemma we have that for every two distinct children c, d ∈ C we have rk x (x c ) < rk x (x d ) if and only if rk y (y c ) < rk y (y d ) and the vertex x can be matched to x c for c ∈ C if and only if the vertex y is matched to a partner they find at least as good as y c (as otherwise the edge {y, y c } would be blocking).
Thus, we observe that children in C form implication in the form "if we want to have a better partner for x, we have to secure a better partner for y". This intuition allows us to formulate the decision for the class C in a 2-CNF formula. Somewhat similar source of difficulty arises from the other case, as we shall see (Lemma 53) that for these children we have to match both x and y to the same child in this class and for every two distinct c, d ∈ C if we have rk x (x c ) < rk x (x d ), then rk y (y c ) > rk y (y d ).
Again, we are facing a contradictory needs, since if x is about to receive a better partner, then y has to receive a partner from the same child which is in turn worse for y.
We have shown how to deal with the good classes; the following corollary ensures that this does not leave too many candidates: Note that if we know for a good class C with N (x) = C edges from cut(C) are contained in a stable matching M , then we can already determine a set of edges F such that (M \ E(C)) ∪ F is a stable matching. This is due to the fact that we know h M,c ({x, x c }) for all c ∈ C. If we also have N (y) = C for some y = x, then we know h M,c for each c ∈ C. Otherwise, we take the matching stored in τ c [(h M,c ({x, x c }), 1) Therefore, we will from now on assume that we fixed a matching N between X t and the classes, and an embedding M * ∈ M of N into the good classes.
Bad classes By Lemmata 39 to 46, we have at most 4 candidates to match a vertex from x to a vertex contained in Y c for some c ∈ C for a good class C. Thus, by Corollary 52, we can enumerate all such embeddings of edges between good classes. Therefore, we enumerate all these possibilities, and show how to decide whether such a matching can be extended to a matching complying with h by reducing the remaining problem to a 2-SAT instance.
However, before doing so, we need to get some structure on the bad classes. For bad classes of the second type, we got this structure in Lemma 48; for bad classes of the first type, we will do this in Lemma 53: Proof. We start with C = C and successively delete elements from C until C fulfills the first condition. If C does not fulfill the first condition, then there exists some  We now reduce the remaining cases to a 2-SAT instance (where 2-SAT is the problem of deciding whether a boolean formula in 2-conjunctive normal form is satisfiable): The reduction to 2-SAT In this paragraph, we assume that we fixed a matching N from X t to the classes, i.e. that each vertex x from X t may only be matched to a vertex from a class C if {x, x C } ∈ N . Furthermore, we assume that we have selected an element (g c ) from the set H from Lemma 38, and for each good class C with N (x) = C for some x ∈ X t , we have selected a matching M C ⊆ E(C). Since there are at most 2 O(k log k) matchings inside E(G[X t ]), we can also enumerate all these matchings, and fix such a matching M Xt . Each of the vectors g c for a heavy children c induces a matching M c . Denote byM the union of the matchings M c for heavy classes, the matching M Xt , and the matchings M C for all good classes C such that there exists an x ∈ X t with N (x) = C. We will reduce the problem of deciding whetherM can be extended to a matching M complying with h and valid for N to a 2-SAT instance.
First, we give a formal definition of a partial embedding and the problem we are going to solve.
for some c contained in a class C ∈ C good ∪ C heavy if and only if N (x) = C, where C good is the set of good children, and C heavy is the set of heavy children of t.

Input:
The graph G and preference lists P . A nice tree-cut decomposition (T, X ) of G and a node t ∈ V (T ). The matching N . A partial embeddingM of N . A vector h ∈ {−1, 0, 1} cut(t) . The DP tables τc for all children c of t. Task: Decide whether there exists a matching

Partial Embedding Extension
Lemma 55. Partial Embedding Extension can be solved in polynomial time.
Proof. We will reduce Partial Embedding Extension to 2-SAT. The correctness of the reduction will be proven in Lemma 56 and 57. As 2-SAT can be solved in polynomial time [2], the lemma follows.
So let I be a Partial Embedding Extension instance. We construct a 2-CNF formula ϕ similarly to the 2-SAT formulation of the Stable Roommates Problem in [13]). An example of our construction is given in Figure 10.
The Construction. First, we apply Lemma 48 and 53. This ensures that for each bad class C and each z ∈ {x, y} = N (C), the vertex z does not tie z c and z d for each c = d ∈ C, and that if x prefers x c over x d , then also y prefers y c over y d if N (x) = C = N (y), and y prefers y d over y c if N (x) = C = N (y).
We assume that for each x ∈ X t with N (x) = C for some class C and x / ∈ e for every edge e ∈M we have that C is a bad class and x ranks the vertices from C at position 1, 2, . . . , |C|.
To see this observe the following. Since we applied Lemma 48 and 53, x does not tie two vertices x c and x d for c, d ∈ C. Furthermore, x ranks all incident edges at a position from {1, 2, . . . , |C|}. Let us write C = {c 1 , . . . , c } with rk x (c 1 ) < · · · < rk x (c ). Assume there exists a vertex v / ∈ V (C) which is a neighbour of x such that rk x (c i ) < rk x (v) < rk x (c i+1 ) for some i ∈ [ − 1]. Recall that the edge {x, v} cannot be in M (nor it is inM ). Consequently, we may "promote" v in its x-ranking to rk x (v) = rk x (c i ), since this yields an equivalent instance.
For each x ∈ X t let us denote by max rk x the maximum x-rank of a neighbour of x, that is, max rk x = max v∈N (x) rk x (v). We introduce variables x j for every j with 1 ≤ j ≤ max rk x , which will be true if and only if x ranks its partner worse than j. Thus, we construct a subformula ϕ x as follows Observe that in order to satisfy ϕ x we have that if x j is set to true, then x j is set to true for all j ≤ j (and, by symmetry, if x j is set to false, then so is x j for all j ≥ j). Note that given a satisfying assignment, we are going to match the vertex x ∈ X t to x c satisfying c ∈ N (x) and rk x (x c ) = p, where p = min{j ∈ N : x j = false}. If no variable x j with x j = false exists, then x remains unmatched. Now, we create a sentence ϕ fixed based on constraints from N , h,M as follows.
If there is a edge e ∈M with x ∈ e, then we add to ϕ fixed the clauses x p−1 and ¬x p , where p = rk x (M (x)) (see clauses x 1 1 and = x 1 2 in Figure 10 for an example). If N (x) = ⊥ (recall that this means that x is unmatched by N ), then we add clauses of the form x j to ϕ fixed for all 1 ≤ j ≤ max v∈N G (x)∩Yt rk x (v) to ensure that x is not matched in M . If N (x) = ⊥, then we add the clause of the form ¬x p to ϕ fixed for p = max v∈N G (x)∩Yt rk x (v) to ensure that x is matched in M (see clauses ¬x 2 2 , ¬x 3 2 and ¬x 4 2 in Figure 10 for an example). For each edge {v, x} ∈ cut(t) with h({v, x}) = 1, we add the clause ¬x rkx(v) to ϕ fixed . For each edge {x, y} ∈ E(G[X t ]), we add the clause ¬x rkx(y) ∨ ¬y rky(x) to ϕ fixed (see clause ¬x 2 2 ∨ ¬x 3 2 in Figure 10 for an example).
Observe that with this setting we indeed have the intended meaning of the variables x j . Next, we consider the heavy and the good children belonging to a class C. The matching inside E(C) is already fixed by the partial embeddingM . For each child c ∈ C and each x ∈ N (C) with rk x c (x) < rk x c (M (x c )), we add the clause ϕ c = ¬x r with r = rk x (x c ). See clause ¬x 2 2 in Figure 10 for an example. We call the conjunction of the formulas over all heavy and all good children ϕ good .
Next, we consider the unmatched children and for each such child c create its formula ϕ c . We distinguish few cases based on the first case applicable to sig(c): 1. If (1, 1) ∈ sig(c) or (1) ∈ sig(c), then c does not yield any further conditions on the rank of the partner of its neighbors. Thus, we set ϕ c to an empty formula (e.g., to true). 2. If (1, −1) ∈ sig(c) and (−1, 1) / ∈ sig(c), then we set ϕ c = ¬y s , where s = rk y (y c ) (see clause ¬x 2 2 for d 1 in Figure 10 for an example). Note that this imposes the constraint that y must be matched to an agent they find at least as good as y c . The symmetric case (−1, 1) ∈ sig(c) and (1, −1) / ∈ sig(c) is handled similarly. 3. If both (1, −1), (−1, 1) ∈ sig(c), then we set ϕ c = ¬x r ∨ ¬y s , where r = rk x (x c ) and s = rk y (y c ) (see clause ¬x 2 2 ∨ ¬x 3 1 in Figure 10 for an example). Similarly to the previous case this demands x or y to be matched to a partner they find at least as good as their possible partners in Y c . 4. If (−1, −1) ∈ sig(c), then we set ϕ c = ¬x r ∧ ¬y s , where r = rk x (x c ) and s = rk y (y c ) (see clauses ¬x 3 1 and ¬x 4 2 for f 1 in Figure 10 for an example). Note that this setting requires both x and y to be matched to a partner they find at least as good as their possible partners in Y c . 5. If (−1) ∈ sig(c), then we set ϕ c = ¬x r , where N (V (Y c )) = {x} and r = rk x (x c ). Note that this setting requires x to be matched to a partner it finds at least as good as x c .
Let ϕ unmatched be the conjunction of the formulas ϕ c for all unmatched children. So far we have constructed formulas that ensure that the sought matching obeys the obvious conditions given by the choices for unmatched, good, and heavy children and by the vector h. Thus, we are left with the bad children. Recall, that if C is a bad class with N (x) = C, then we have altered the ranking function so that we have rk x (v) ∈ {1, . . . , |C|} for all v ∈ N (x).
1. Let C be a bad class with N (x) = C and N (y) = C for some x = y. Recall that in this case we have to match both x and y to the same child in C and that if rk x (x c ) = p, then rk y (y c ) = |C| − p + 1 (by Lemma 48 and since x ranks the vertices from C at position 1, 2, . . . , |C|). Thus we set ϕ C = |C|−1 p=1 x p ∨ y |C|−p (see clause x 2 1 ∨ x 3 1 in Figure 10 for an example).
x 1 we have that x p−1 and y |C|−p are set to true for p = rk x (x c ). But now, since if x p−1 is true, then x p is true for all p ≤ p − 1. By the same argument, y p is true for all p ≤ |C| − p, and the formula ϕ C is satisfied by the constructed assignment.
Finally, let C be a bad class with N (C) = {x, y} and N (x) = C = N (y). Let M (x) = x c for some c ∈ C (cf. Lemma 53); thus, we have that x p−1 is set to true, x p is set to false, andy p is set to true for p = rk x (x c ). Again, since if x p−1 is true, then x p is true for all p ≤ p − 1 and if y p is false, then y p is false for all p ≥ p, the formula ϕ C is satisfied by the constructed assignment.
We conclude that our assignment satisfies ϕ and the lemma follows.
Lemma 57. If there exists a satisfying assignment for ϕ, then there exists an h-embedding of N of the form M ∪M .

Proof.
Assume that there is a satisfying truth assignment f : {x j : x ∈ X t } → {true, false}. Since f satisfies ϕ x , we know that for each x ∈ X t there exists some j x such that x j is set to false if and only if j ≥ j x . We first compute the matching M and then argue that M ∪M is an h-embedding of N .
We start with a claim for one kind of bad children.
Claim 58. Let C be a class of bad children with N (x) = N (y) = C and let f be an assignment satisfying ϕ. Then there exists an assignment f : {x j : x ∈ X t } → {true, false} satisfying ϕ for which there exists q such that both x q−1 and y |C|−q are set to true in f .

Proof.
Assume that in f no such q exists for C and recall that ϕ C = |C|−1 p=2 x p ∨ y |C|−p . Let q := min ({j ∈ N : x j = false} ∪ {max rk(x)}). Let f be the same assignment as f with the only exception that we set y p to false for p ≥ |C| − q + 1. Clearly, f satisfies ϕ; indeed we have only selected a more permissive assignment for y (any clause outside C does not contain the literal y p for any p).
It follows that we can select an initial matching M between vertices in X t and their possible partners in bad children as follows. For a bad class C and an x ∈ X t with N (x) = C, we add the edge {x, x c } to M for the c ∈ C such that rk x (x c ) = p, where p = min{j ∈ N : x j = false}. Now, we extend M to a matching M on clos(t) by adding for each bad or unmatched child c the matching stored in τ c [h M ,c ]. We claim that all such entries exist and that the resulting matching M ∪M is an h-embedding of N . The first claim follows trivially for bad children.
Observe that ϕ fixed assures that for each {v, x} ∈ cut(t) with h({v, x}) = 1 we have that rk x (M (x)) ≤ rk x (v). Furthermore, it assures that no edge {x, y} ∈ E(G[X t ]) is blocking. By ϕ good , no edge {z, z c } for a heavy or a good child c of t is blocking. By ϕ unmatched no edge {z, z c } for an unmatched child c of t is blocking. The lemma follows.
If Proof. By Lemma 38, we have to consider 2 O(k log k) matchings from X t to the heavy children of t.
As there are O(k 2 ) classes of light children, there are 2 O(k log k) matchings between X t and the classes.
By Corollary 52, we get 2 O(k) matchings inside the light children.
Since there are 2 O(k log k) matchings inside G[X t ], this results in 2 O(k log k) partial embeddings for each of these matchings.
Each of these partial embeddings defines a Partial Embedding Extension instance, which can be solved in polynomial time by Lemma 55. Clearly, a matching complying with h exists if and only if one of the Partial Embedding Extension instances is a YES-instance. Therefore, the total running time is 2 O(k log k) n O(1) .

Proof of Corollary 16.
Any stable matching is a maximal matching, and thus any stable matching is a 1 2 -approximation of a maximum stable matching. Therefore, any algorithm finding an arbitrary stable matching, if one exists, is a 1 2approximation algorithm, and such an algorithm with the claimed running time exists by Theorem 13.

D An FPT-algorithm with respect to feedback edge number
In this section, we give an FPT-algorithm for Max-SRTI parameterized by the feedback edge number. This will be achieved by reducing an Max-SRTI-instance to 2 fes(G) Max-SRTI-instances of treewidth at most 2. These instances can be solved in polynomial time, as Max-SRTI parameterized by treewidth is contained in XP.
Proof of Theorem 17. Let F be a minimum feedback edge set. We enumerate all matchings F ⊆ F . Let X be the vertices matched by F , i.e. X = {v ∈ V (G) : ∃{v, w} ∈ F }. Denote by G F := G − X the subgraph of G induced by the vertices unmatched in F . Furthermore, we enumerate all functions f : F \F → V (G) with f (e) ∈ e for all e ∈ F \F . The vertex f (e) for an edge e = {v, w} ∈ F \ F , corresponds to the endpoint of e which prefers the matching over the other endpoint of e.
We try to extend F to a maximum stable matching. If there exists a blocking pair {v, w} consisting of two matched vertices, then we directly discard F , as it cannot be part of any solution: We do not change the matching of v or w, and thus they will stay a blocking pair.
We design a Max-SRTI instance H with tw(H) ≤ 2 which contains a stable matching of size t if and only if G contains a stable matching containing F of size t − + |F | for some to be defined later. Let