Qiong Liu
email: qiong.liu@insa-rennes.fr

Jean-Yves Baudais

Philippe Mary

Queue Analysis with Finite Buffer by Stochastic Geometry in Downlink Cellular Networks

Keywords: stochastic geometry, downlink cellular network, instantaneous SINR, DTMC, finite buffer

In this work, we proposed a tractable mathematical framework to analyze the coverage probability in dynamic downlink cellular networks taking into account the queue dynamics with finite buffer restriction. In particular, the developed model is based on stochastic geometry and queueing theory to handle the interaction between the coverage probability and the queueing state evolution. We also analyze the coverage probability as well as packet loss probability with discrete time Markov chain at stationary regime. We explicitly derive the influence of the packet buffer length to the coverage and packet loss probability. We show in particular that small buffer length leads to a better coverage probability but also to a larger packet loss probability, advocating for a tradeoff between these two metrics.

I. INTRODUCTION

A. Background and related works

Stochastic geometry provides a mathematical framework to analyze the performance of large scale wireless networks by capturing the spatial randomness intrinsic to the wireless systems including fading, shadowing, and power control [START_REF] Andrews | A tractable approach to coverage and rate in cellular networks[END_REF]- [START_REF] Novlan | Analytical modeling of uplink cellular networks[END_REF]. Recently, stochastic geometry has been combined with more complex network models taking into account frequency reuse, multiple antennas, multiple-tiers or load-aware protocols, to cite a few [START_REF] Elsawy | Modeling and Analysis of Cellular Networks Using Stochastic Geometry: A Tutorial[END_REF]- [START_REF] Zhong | On the stability of static poisson networks under random access[END_REF].

Since real systems are subjected to temporal traffic variations and the sources generate packets according to some stochastic processes [START_REF] Dhillon | Load-aware modeling and analysis of heterogeneous cellular networks[END_REF], the full-load hypothesis, which assumes that each cell uses the same frequency band and is always transmitting, is not enough to address the performance of practical systems. The full load hypothesis generally leads to pessimistic network performance [START_REF] Zhong | On the stability of static poisson networks under random access[END_REF].

Therefore, load-awareness is essential for practical performance assessment. The main difficulty is the complex interaction between the packet arrival process and the service rate, which depends on the coverage probability, that depends in turn on the interference distribution over the networks and the dynamic of transmitters' queues. Hence, the distribution of the interferers and the queue length at each transmitter are two interdependent processes which make the analysis of the signal to interference plus noise ratio (SINR) quite challenging [START_REF] Zhong | On the stability of static poisson networks under random access[END_REF], [START_REF] Yang | Spatio-temporal analysis for sinr coverage in small cell networks[END_REF].

This work has been funded by a China Scholarship Council (CSC) grant.

A simple way to decouple the influence of the interference and the data traffic in the SINR analysis, is to consider that the set of interfering transmitters is a Poisson point process (PPP) randomly thinned from the original PPP according to a certain activity factor [START_REF] Zhong | Heterogeneous cellular networks with spatio-temporal traffic: Delay analysis and scheduling[END_REF]- [START_REF] Dhillon | Load-aware modeling and analysis of heterogeneous cellular networks[END_REF]. In [START_REF] Dhillon | Load-aware modeling and analysis of heterogeneous cellular networks[END_REF], authors studied the impact of the activity probability on heterogeneous cellular network performance, e.g. coverage probability, average rate, conditioned on that the typical user connects to the strongest BS. Similarly, [START_REF] Zhong | Heterogeneous cellular networks with spatio-temporal traffic: Delay analysis and scheduling[END_REF], [START_REF] Zhong | On the stability of static poisson networks under random access[END_REF] integrates stochastic geometry and queueing theory to study sufficient and necessary conditions for queue stability in ad hoc networks. However, the interaction between the queues at different transmitters are either ignored or only analyzed by approximations.

To model the aforementioned interactions between the queues and the interference distribution, authors in [START_REF] Yang | Spatio-temporal analysis for sinr coverage in small cell networks[END_REF]- [START_REF] Jiang | Random access analysis for massive IoT networks under a new spatio-temporal model: A stochastic geometry approach[END_REF] introduced queueing theory in the analysis of the coverage probability. A traffic-aware spatio-temporal model for IoT devices supported by cellular uplink connectivity has been developed in [START_REF] Gharbieh | Spatiotemporal Stochastic Modeling of IoT Enabled Cellular Networks: Scalability and Stability Analysis[END_REF]. The authors studied the trade-off between the scalability of the network, i.e. its ability to support a large number of devices, and its stability, i.e. the queues are not diverging. Similarly, a novel spatio-temporal mathematical framework has been developed to analyze the transmission success probability of a cellular network [START_REF] Jiang | Random access analysis for massive IoT networks under a new spatio-temporal model: A stochastic geometry approach[END_REF], where the number of accumulated packets in the queues is approximated by a Poisson distribution. However, the theoretical findings are not validated by simulations.

To the best of our knowledge, all the works mentioned before studied the coverage probability with infinite queue lengths. However, the packet loss probability is also an important performance measure needed for the design of telecommunication networks. The quantity of interest is the probability of a new packet is dropped when the buffer has a finite size [START_REF] Alfa | Applied Discrete-Time Queues[END_REF], [START_REF] Ni | Analysis of finite buffer in two-way relay: A queueing theoretic point of view[END_REF]. The main contribution of the paper is to derive the coverage and packet loss probabilities considering the buffer restriction.

B. Approach and contributions

This work proposes a tractable mathematical model to analyze the coverage probability and packet loss probability in a downlink cellular network, in which queue dynamics are taken into consideration. We develop a comprehensive approach to handle the interaction between the coverage probability and the queueing state evolution using a discrete time Markov chain (DTMC) when a finite buffer length at each transmitter is considered. We derive a closed-form expression of the coverage probability that depends on the fraction of active base stations (BS) that depends in turn to the activity probability which is related to the buffer length. We also characterize the packet loss probability with DTMC the stationary regime.

C. Notations

Throughout the paper, P{•} denotes probability, E X {•} denotes the expectation over the random variable X. The indicator function is denoted as 1{•}, which takes values 1 when the statement {•} is true and 0 otherwise. The Euclidean norm is denoted as • .

The rest of paper is organized as follows. Section II presents the system model and the assumptions. The coverage and packet loss probabilities are established in Section III. Section IV provides the simulation results and conclusions are drawn in Section V.

II. SYSTEM MODEL

A. Spatial & physical layer parameters

We consider a single-tier downlink cellular-based network where BSs are spatially distributed in R 2 following an homogeneous PPP Φ = {x i } i∈N with intensity λ, where the x i 's are the positions of BS. We assume the user equipments (UEs) density is high enough that every BS has at least one user associated with it. Besides, each UE is served by its nearest BS. A single UE, randomly chosen, is considered as a typical UE and is located at the origin (0, 0) for the easy of analysis, with its tagged BS located at x 0 . Moreover, every BS is assumed to transmit in the same band, i.e. full frequency reuse.

B. Traffic model

We use a discrete time queueing system to model the random traffic arrival and departure processes. The time is slotted in very short equal intervals. Each time slot can be used for a single transmission attempt, which means that a single packet arrival or departure can take place per time slot.

A geometric inter-arrival packet generation, with parameter ξ ∈ [0, 1] (packet/slot) is assumed at each BS. The arrived packets at each BS are stored in a buffer with finite size until being transmitted successfully. When a packet arrives and the buffer is full, this new arrival packet is dropped. The buffer length restriction B are the same for all BS and is the maximal number of packets the buffer can contained.

Contrarily to the arrival process, the departure process cannot be fixed a priori. It is characterized according to the time-dependent SINR distribution. If the received SINR exceeds a predefined threshold θ, the receiver can decode the packet, this packet is transmitted successfully and it can be removed from the queue. If the transmission failed, the packet remains in the buffer and waits for a re-transmission in the next time slot until being successfully transmitted. In this paper, no limit on the number of retransmissions is considered. At each time slot, the transmitters with empty buffer remain silent.

Moreover, we define Φ t as the set of BS that remain active in the time slot t ∈ N.

The realization of the point process Φ is conditioned on a full time activity of the BS located at x 0 . The relevant probability measure over the PPP is then reduced to Palm probability, denoted as P x0 . Correspondingly, the expectation is taken with respect to the measure P x0 .

C. Signal-to-interference ratio

The received SINR at time slot t experienced by the typical UE is

γ t = h x0,t x 0 -α σ 2 + x∈Φ\x0 h x,t x -α 1(x ∈ Φ t ) (1)
where x is the distance between the interfering BS at x and the typical user, h x,t and h x0,t are the channel gains between the typical UE and the interfering BS at position x and its tagged BS at position x 0 at time slot t, respectively, and they are assumed to be exponentially distributed. α stands for the path loss exponent, σ 2 denotes the power of the additive white Gaussian noise and 1(x ∈ Φ t ) indicates whether a node located at x ∈ Φ is transmitting at time slot t, i.e. 1(x ∈ Φ t ) = 1 or not, i.e. 1(x ∈ Φ t ) = 0. Moreover, we note q t the quantity

q t = P 1(x∈Φt) (1(x ∈ Φ t ) = 1) (2)
which can be seen as the fraction of active interfering BS at time slot t or equivalently the probability that a randomly chosen BS is active at time slot t.

III. PERFORMANCE ANALYSIS

The main technical results of the paper are presented now. we first detail the dynamic coverage probability. Then, the traffic analysis and its relation with the coverage probability are performed thanks to a DTMC. By characterizing the stationary regime of this DTMC, we derive the distribution of stable coverage probability and packet loss probability.

A. Dynamic coverage probability

Considering that the typical UE receives data at time slot t, i.e. its associated BS in x 0 is always active, the coverage probability is defined as [START_REF] Zhong | On the stability of static poisson networks under random access[END_REF]

p t (θ, ξ, B) P x0 [γ t > θ] ( 3
)
where θ is the decoding SINR threshold.

Lemma 1. The received dynamic coverage probability experience by the typical UE at time t is

p t (θ, ξ, B) = 2πλ ∞ 0 e -σ 2 θr α e -πλr 2 (1+qtρ(α,θ)) rdr (4)
where ρ(α, θ)

= ∞ 1 [1 + u α 2 θ -1 ] -1 du.
Proof. See Appendix A.

Lemma 1 quantifies how the coverage probability behaves at a given time slot and depends on the traffic. The queue

0 1 • • • B B + 1 ξ p t ξ + pt ξ p t ξ + pt ξ p t ξ + pt ξ ξ + pt ξ ξ pt ξ pt ξ pt ξ p t ξ p t ξ p t ξ p t ξ Figure 1. DTMC model.
states are affecting the coverage probability via the parameter q t . As q t decreases, less interferers are actives in the network, and hence, the aggregate interference decreases and dynamic coverage probability increases at typical BS.

To characterize q t , a Markov chain with B + 2 states is considered where the state space is {0, 1, • • • , B, B + 1} as illustrated in Fig. 1. State 0 represents the empty buffer event.

When the buffer is in this state, the transmitter remains silent. When the queue is in state B, it means the buffer is full and hence any new generated packet is dropped, i.e. state B + 1. Since the packets arrive according to the Bernoulli process with parameter ξ and the service is then geometric with parameter p t , the number of packets at an arbitrary time instant can be modeled as the DTMC given in Fig. 1. Note that q t is the complementary probability for the queue to be in state 0 at each time slot.

B. Stable coverage probability

The network is called stable if the number of active transmitters converges regardless of the network initial condition [START_REF] Alammouri | Stability and metastability of traffic dynamics in uplink random access networks[END_REF]. Let Φ be the limit of Φ t as t → ∞, which represents the point process in the stable regime. Let q = P 1(x∈ Φ) (1(x ∈ Φ) = 1). The stable coverage probability is defined as

p(θ, ξ, B) = lim t→∞ p t (θ, ξ, B) (5)
Lemma 2. Considering q t→∞ = q, the stable coverage probability is

p(θ, ξ, B) = 2πλ ∞ 0 e -σ 2 θr α e -πλr 2 (1+qρ(α,θ)) rdr (6)
where ρ(α, θ)

= ∞ 1 [1 + u α 2 θ -1 ] -1 du. Proof. See Appendix B.
By characterizing the stationary regime of DTMC, we decouple the time dependence of the coverage probability and the queue states. Thanks to Lemmas 1 and 2, we are now ready to present our main result of this paper, i.e. the stable coverage probability with finite buffer restriction.

Theorem 1. The stable coverage probability with a finite buffer restriction B is given by the fix point equation

p(θ, ξ, B) (7) = 2πλ ∞ 0 e -σ 2 θr α e -πλr 2 1+ (R B+2 -R)ρ(α,θ) R B+2 -R+(R-1) p(θ,ξ,B)
rdr where p(θ, ξ, B) = 1 -p(θ, ξ, B), and R = ξ p(θ,ξ,B) ξp(θ,ξ,B) . Proof. See Appendix C. Corollary 1. In an interference-limited network, i.e. σ 2 → 0, we have

p(θ, ξ, B) = 1 + Υ ∞ 1 1 1 + u α 2 θ -1 du -1 (8)
where

Υ = 1 + (1 -R B+2 ) -1 (1 -R) -1 (1 -p(θ, ξ, B)).
When the path loss exponent α = 4, the stable coverage probability can be further simplified to

p(θ, ξ, B) = 1 + Υ √ θ( π 2 -arctan √ θ) -1 (9)
For the sake of simplicity, we use p instead of p(θ, ξ, B) in the rest of this paper. The fix point equation expressed in Theorem 1 can be iteratively solved using Algorithm 1.

Algorithm 1 Iteration algorithm for computation of p and q.

Initialize q 1 ∈ (ξ, 1),

q 0 = 0, i = 0, 1 while |q i+1 -q i | ≥ do i ← i + 1, q ← q i , p ← p (22) in Appendix C if |q i+1 -q i | ≥ then q i+1 ← q (21) in Appendix C break end if end while
Return q ← q i+1 and p

C. Packet loss probability

The packet loss probability is the probability that a new packet is dropped when it meets the maximum queue length situation and is given by the following lemma. Lemma 3. The packet loss probability at a randomly chosen BS with finite buffer length restriction B is given by

p loss = R B+2 -R B+1 (R -1)p + R B+2 -R ( 10
)
where p is the stable coverage probability in Theorem 1 and R = ξ p ξp . Proof. p loss is the probability to be in the state B + 1. According to (16) and Theorem 1, the result is obtained after some algebraic manipulations.

IV. NUMERICAL RESULTS AND SIMULATIONS

BS positions are generated using a PPP with density λ = 0.25. Each UE is associated to its nearest BS. The packets arrive to each BS according to the Bernoulli process with parameter ξ and the service is then geometric with parameter p t at each time slot. For each network realization, the queues are let to evolve up to the convergence, i.e. the number of active transmitters does not evolve with time, then a new network realization is drawn and the process repeats. Fig. 2 compares the analytical result obtained in Theorem 1 evaluated with Algorithm 1, with the Monte-Carlo simulations under different arrival rate ξ as well as different buffer restriction B. First, we observe that the full load model is pessimistic w.r.t. the coverage probability. When the buffer length is kept constant, e.g. B = 5, we observe that the higher the arrival rate, the lower the coverage probability, on a large range of coverage threshold θ. Indeed, when ξ increases the queues are more solicited and hence BSs often have a packet to transmit and hence they generate interference. A more surprising result, is the dependency of the coverage probability with the buffer size when the arrival rate is fixed, i.e. ξ = 0.3. We notice that when the buffer length increases, i.e. B changes from 1 to 5, the coverage probability degrades for thresholds between 2 dB and 14 dB. This is due to the fact that BS with a large B drop less packets than BS with a smaller queue size, for a given arrival rate. Hence, the activity probability is larger when B = 5 than when B = 1 that increases the interference and hence decreases the coverage probability. However, a very constraint queue size implies an important packet loss since the probability that a randomly chosen queue be full is higher when B = 1 than when B = 5. Fig. 3 plots the coverage probability and the packet loss probability in Lemma 3 w.r.t the threshold θ, and labeled on the arrival rate ξ and the queue length B. When fixing the queue length B = 5, we observe that the coverage probability improves when the arrival rate decreases, i.e. from ξ = 0.3 to ξ = 0.1 since the network generates less packets in the second case and hence the probability for a BS to be idle increases, that decreases the interference to the typical user. Moreover, since less packets are generated the packet loss probability also decreases for a given coverage threshold. When fixing the arrival rate ξ = 0.3, we observe that the packet loss decreases significantly when B increases for low to medium range of values of θ.

V. CONCLUSION

In this paper, we proposed a tractable mathematical model to analyze the stable coverage probability and packet loss probability in a dynamic traffic randomly deployed downlink cellular network with finite buffer length. The queue evolution at each transmitter has been handled with a DTMC and a Bernoulli distribution for packet arrival. The interaction between the coverage probability and the queue state evolution has been captured in closed-form. We also discussed the impact of different arrival rates and different buffer lengths to the network performance, measured with the coverage probability and the packet loss probability.

APPENDIX

A. Proof of Lemma 1

Given the typical UE received data at time slot t, its conditional SINR coverage probability is written as (to lighten the notation we remove the index t from the channel coefficients)

p t = P x0 (γ t ≥ θ) = P x0    h x0 x 0 -α σ 2 + x∈Φ\x0 h x x -α 1(x ∈ Φ t ) ≥ θ    = ∞ 0
2πλr 0 e -πλr 2 0 exp(-σ 2 θr α 0 )

× P x0    h x0 x 0 -α σ 2 + x∈Φ\x0 h x x -α 1(x ∈ Φ t ) ≥θ x 0 = r 0   dr0 = ∞ 0
2πλr 0 e -πλr 2 0 e -σ 2 θr α 0 L I (θr α 0 )dr 0 [START_REF] Alfa | Applied Discrete-Time Queues[END_REF] where the Laplace transform (LT) of a random variable X in s is denoted as L X (s). Further, the LT L X (s) in [START_REF] Alfa | Applied Discrete-Time Queues[END_REF], with s = θr α 0 , has the form:

L I (s) = E exp -s x∈Φ\x0 h x x -α 1(x ∈ Φ t ) r 0 a = E Φ   x∈Φ\x0 E hx exp -sh x x -α 1(x ∈ Φ t ) r 0   = E Φ   x∈Φ\x0 1 1 + s x -α 1(x ∈ Φ t ) r 0   = E {1(x∈Φt)}   E Φ   x∈Φ\x0 1 1+s x -α 1(x ∈ Φ t ) r 0 , 1(x ∈ Φ t )     b = E Φ   x∈Φ\x0 E 1(x∈Φt) [1(x ∈ Φ t ) = 1] 1 + s x -α × 1 + E 1(x∈Φt) [1(x ∈ Φ t ) = 0] 1 + s x -α × 0 r 0 c = E Φ   x∈Φ\x0 q t 1 + s x -α + 1 -q t r 0   (12)
where (a) follows from the i.i.d. hypothesis of h x and further independence from the point process Φ, (b) follows from the law of total expectation and using independence activity of BS [9, Assumption 2], and (c) follows from q t = P(1(x ∈ Φ t ) = 1).

According to the PGFL of PPP and with r = x , we have

L I (θr α 0 ) = exp -2πλ ∞ r0 1 - q t 1 + θr α 0 r -α + 1 -q t rdr a = exp -πλr 2 0 ∞ 1 q t 1 + u α 2 θ -1 du (13)
where (a) is obtained by the change of variable u = ( r r0 ) 2 .

B. Proof of Lemma 2

Considering q t→∞ = q, we have

p = lim t→∞ p t (θ, ξ, B) = lim t→∞ 2πλ ∞ 0 e -σ 2 θr α e -πλr (1+qtρ(α,θ)) rdr = 2πλ ∞ 0 e -σ 2 θr α e -πλr 2 (1+qlim t→∞ ρ(α,θ)) rdr = 2πλ ∞ 0 e -σ 2 θr α e -πλr 2 (1+qρ(α,θ)) rdr (14) where ρ(α, θ) = ∞ 1 [1+u α 2 θ -1 ] -1 du. (a)
follows the fact that p t is non-negative and continuous. Let A(r) = e e -σ 2 θr 2 , and g = A(r)e -πλr 2 , we have A(r)e -πλ(1+qtρ(α,θ)) ≤ g, ∀θ > 0, t ∈ N. Since g is integrable, by the dominant convergence theorem, we have p and the result follows.

C. Proof of Theorem 1

The number of packets in the queue can be characterized by the stationary distribution of DTMC in Fig. 1. When t → ∞, q = P 1(x∈ Φ) (1(x ∈ Φ) = 1), p is given in (14). The transition probability matrix writes where π = [π 0 , π 1 , π 2 , • • • , π B , π B+1 ] is the row vector that contains the stationary probabilities, in which π i (1 ≤ i ≤ B) denotes the probability of being in state with i packets, π B+1 denotes the probability of a new packet is dropped when it meets the maximum queue length situation, and e is a column vector of ones with the proper length. The solution of ( 16) is the solution of

P =         
         π 0 = π 0 ξ + π 1 ξp π 1 = x 0 ξ + π 1 ( ξ p + pξ) + x 2 ξp π i = π i-1 ξ p + x i ( ξ p + pξ) + π i+1 ξp, 2 ≤ i ≤ B π B+1 = π B ξ p + π B+1 (p + pξ) (17)
according to (17), we have

π i = π 0 p ( ξ p ξp ) i , 1 ≤ i ≤ B ( 18
)
π B+1 = ( ξ p ξp ) B ξ ξp π 0 (19)
After normalization, we obtain

π 0 = 1 + ξR B ( ξp) -1 + (p) -1 B i=1 R i -1 (20)
where R = ξ p ξp . Combine (20) and ( 14), and the condition that q = 1 -π 0 , we have 22), the interdependence between q and p shows the relationship between the queue and the stochastic geometry in the analysis. After some manipulations, we obtain the result.

q = 1 -1 + ξR B ( ξp) -1 + B i=1 R i (p)

Figure 2 .

 2 Figure 2. Coverage probability at stable state with different buffer restrictions B and arrival rates ξ.

Figure 3 .

 3 Figure 3. Packet loss probability and coverage probability at stable state (λ = 0.25, σ 2 = -10 dB, α = 4).

e

  -σ 2 θr α e -πλr 2 (1+qρ(α,θ)) rdr (22)where ā = 1 -a with a ∈ {p, ξ}, ρ(α, θ)= ∞ 1 [1 + u α 2 θ -1 ] -1 du, R = ξ p ξp .According to (21) and (


Pinar Heggernes

Pim Van 't Hof

Daniel Lokshtanov
email: dlokshtanov@cs.ucsd.edu

Christophe Paul
email: paul@lirmm.fr

Obtaining a Bipartite Graph by Contracting Few Edges *

Keywords: 2.2, F.2.2 Keywords and phrases fixed parameter tractability, graph modification problems, edge contractions, bipartite graphs

We initiate the study of the Bipartite Contraction problem from the perspective of parameterized complexity. In this problem we are given a graph G on n vertices and an integer k, and the task is to determine whether we can obtain a bipartite graph from G by a sequence of at most k edge contractions. Our main result is an f (k) n O(1) time algorithm for Bipartite Contraction. Despite a strong resemblance between Bipartite Contraction and the classical Odd Cycle Transversal (OCT) problem, the methods developed to tackle OCT do not seem to be directly applicable to Bipartite Contraction. To obtain our result, we combine several techniques and concepts that are central in parameterized complexity: iterative compression, irrelevant vertex, and important separators. To the best of our knowledge, this is the first time the irrelevant vertex technique and the concept of important separators are applied in unison. Furthermore, our algorithm may serve as a comprehensible example of the usage of the irrelevant vertex technique.

Introduction

Odd Cycle Transversal (OCT) is a central problem in parameterized complexity. The establishment of its fixed parameter tractability by Reed, Smith, and Vetta [START_REF] Reed | Finding odd cycle transversals[END_REF] in 2004, settling a long-standing open question [START_REF] Downey | Parameterized Complexity[END_REF], supplied the field with the powerful new technique of iterative compression [START_REF] Niedermeier | Invitation to Fixed-Parameter Algorithms[END_REF]. Both OCT and the closely related Edge Bipartization problem take as input a graph G and an integer k, and ask whether a bipartite graph can be obtained by deleting at most k vertices, respectively k edges, from G. These two problems can be viewed as two ways of measuring how close G is to being bipartite. Over the last few years a considerable amount of research has been devoted to studying different measures of how close a graph is to being bipartite [START_REF] Guo | Compression-based fixedparameter algorithms for feedback vertex set and edge bipartization[END_REF][START_REF] Hüffner | Algorithm engineering for optimal graph bipartization[END_REF][START_REF] Kawarabayashi | Odd cycle packing[END_REF][START_REF] Kawarabayashi | An (almost) linear time algorithm for odd cycles transversal[END_REF], and how similarity to a bipartite graph can be exploited [START_REF] Demaine | Decomposition, approximation, and coloring of odd-minor-free graphs[END_REF]. Another natural similarity measure is defined by the Bipartite Contraction problem: Given a graph G and an integer k, can we obtain a bipartite graph from G by a sequence of at most k edge contractions in G? Considering the significant amount of interest the problems OCT and Edge Bipartization have received, we find it surprising that Bipartite Contraction has not yet been studied with respect to parameterized complexity. In this area, a graph problem with input G and k is said to be fixed parameter tractable (FPT) when parameterized by k if there is an algorithm with running time f (k) n O (1) , where the function f depends only on k and not on the size of G.

The classical computational complexity of contracting at most k edges in a given graph to obtain a graph with a specific structure has been studied by Watanabe et al. [START_REF] Watanabe | On the removal of forbidden graphs by edgedeletion or edge-contraction[END_REF][START_REF] Watanabe | On the NP-hardness of edge-deletion and edgecontraction problems[END_REF] and by Asano and Hirata [START_REF] Asano | Edge-contraction problems[END_REF]. NP-completeness of Bipartite Contraction follows from an easy polynomial-time reduction from Edge Bipartization, in which every edge of the input graph is replaced by a path of sufficiently large odd length. The study of edge contractions in general is motivated from Hamiltonian graph theory and graph minor theory, and it has applications in computer graphics and cluster analysis [START_REF] Levin | The computational complexity of graph contractions I: polynomially solvable and NP-complete cases[END_REF]. Graph minors play a central role in parameterized complexity, and the edge contraction operation in turn is essential in the study of graph minors: a graph H is a minor of a graph G if H can be obtained from G by a sequence of edge contractions, edge deletions, and vertex deletions. Although deciding whether a graph H is a minor of a given graph G is FPT when parameterized by the size of H [START_REF] Robertson | Graph minors. XIII. The disjoint paths problem[END_REF], deciding whether H can be obtained from G by edge contractions is NP-complete already for some very small fixed graphs H, such as a path or a cycle on four vertices [START_REF] Brouwer | Contractibility and NP-completeness[END_REF].

In this paper we show that Bipartite Contraction is FPT when parameterized by the number k of edges to be contracted. The key ingredients of our algorithm fundamentally differ from the ones used in the above-mentioned algorithms for OCT and Edge Bipartization. In the algorithm for OCT by Reed, Smith, and Vetta [START_REF] Reed | Finding odd cycle transversals[END_REF], iterative compression is combined with maximum flow arguments. The recent nearly linear time algorithm for the two problems, due to Kawarabayashi and Reed [START_REF] Kawarabayashi | An (almost) linear time algorithm for odd cycles transversal[END_REF], uses the notion of odd minors, together with deep structural results of Robertson and Seymour [START_REF] Robertson | Graph minors. XIII. The disjoint paths problem[END_REF] about graphs of large treewidth without large clique minors. Interestingly, Bipartite Contraction does not seem to be amenable to these approaches.

Although our algorithm is based on iterative compression, it seems difficult to adapt the compression step from [START_REF] Reed | Finding odd cycle transversals[END_REF] for OCT to work for Bipartite Contraction. Instead, we perform the compression step using a variant of the irrelevant vertex technique, introduced by Robertson and Seymour [START_REF] Robertson | Graph minors. XIII. The disjoint paths problem[END_REF] (see also [START_REF] Robertson | Graph Minors. XXII. Irrelevant vertices in linkage problems[END_REF]). In particular, if the treewidth of the input graph is large, then we identify an irrelevant edge that can be deleted from the graph without affecting the outcome. The irrelevant vertex technique has played a key role in the solutions of several problems (see, e.g., [START_REF] Kawarabayashi | An improved algorithm for finding cycles through elements[END_REF][START_REF] Kawarabayashi | Odd cycle packing[END_REF][START_REF] Kawarabayashi | A simpler algorithm and shorter proof for the graph minor decomposition[END_REF]).

Our algorithm crucially deviates from previous work in the manner in which it finds the irrelevant edge. While previous work has relied on large minor models as obstructions to small treewidth, ours uses the fact that any graph of high treewidth contains a large p-connected set X [START_REF] Diestel | Highly connected sets and the excluded grid theorem[END_REF]. A vertex set X is p-connected if, for any two subsets X 1 and X 2 of X with |X 1 | = |X 2 | ≤ p, there are |X 1 | vertex-disjoint paths with one endpoint in X 1 and the other in X 2 . Using p-connected sets in order to find irrelevant edges has several advantages. First, our algorithm avoids the huge parameter-dependence which seems to be an inadvertent side effect of applying Robertson and Seymour's graph minors machinery. Second, our arguments are nearly self-contained, and rely only on results whose proofs are simple enough to be taught in a graduate class.

Using p-connected sets in order to find an irrelevant vertex or edge is non-trivial, because p-connectivity is a more "implicit" notion than that of a large minor model. We overcome this difficulty by using important sets. Important sets and the closely related notion of important separators were introduced in [START_REF] Marx | Parameterized graph separation problems[END_REF] to prove the fixed parameter tractability of multiway cut problems. The basic idea is that in many problems where terminals need to be separated in some way, it is sufficient to consider separators that are "as far as possible" from one of the terminals. Important separators turned out to be a crucial component, in some cases implicitly, in the solutions of cardinal problems in parameterized complexity [START_REF] Chen | An improved parameterized algorithm for the minimum node multiway cut problem[END_REF][START_REF] Chen | A fixed-parameter algorithm for the directed feedback vertex set problem[END_REF][START_REF] Marx | Fixed-parameter tractability of multicut parameterized by the size of the cutset[END_REF][START_REF] Razgon | Almost 2-SAT is fixed-parameter tractable[END_REF]. To the best of our knowledge, this is the first time the irrelevant vertex technique and important sets (or separators) are used together. We believe that this combination will turn out to be a useful and powerful tool.

Definitions and Notation

All graphs considered in this paper are finite, undirected, and simple, i.e., do not contain multiple edges or loops. Given a graph G, we denote its vertex set by V (G) and its edge set by E(G). We also use the ordered pair (V (G),

E(G)) to represent G. We let n = |V (G)| and m = |E(G)|. For two graphs G 1 = (V 1 , E 1 ) and G 2 = (V 2 , E 2 ), the disjoint union of G 1 and G 2 is the graph G 1 ∪ G 2 = (V 1 ∪ V 2 , E 1 ∪ E 2 )
. The deletion of an edge e ∈ E(G) yields the graph G -e = (V (G), E(G) \ e). For a set X ⊆ V (G), we write G[X] to denote the subgraph of G induced by X. A graph is connected if there is a path between each pair of its vertices. The connected components of a graph are its maximal connected subgraphs.

For any set X ⊆ V (G), we write δ G (X) to denote the set of edges in G that have exactly one endpoint in X. We define d G (X) = |δ(X)|.

The contraction of edge xy in G deletes vertices x and y from G, and replaces them by a new vertex, which is made adjacent to precisely those vertices that were adjacent to at least one of the vertices x and y. The resulting graph is denoted G/xy. Every edge contraction reduces the number of vertices in the graph by exactly one. We point out that several edges might disappear as the result of a single edge contraction. For a set S ⊆ E(G), we write G/S to denote the graph obtained from G by repeatedly contracting an edge from S until no such edges remain. Let H be a graph with V (H) = {h 1 , h 2 , . . . , h }. A graph G is H-contractible if H can be obtained from G by contracting edges. Saying that G is H-contractible is equivalent to saying that G has a so-called H-witness structure W, which is a partition of V (G) into witness sets W (h 1 ), W (h 2 ), . . . , W (h ), satisfying the following properties: each witness set induces a connected subgraph of G, and for every two h i , h j ∈ V (H), there is an edge in G between a vertex of W (h i ) and a vertex of W (h j ) if and only if h i and h j are adjacent in

H. Let G = G[W (h 1 )] ∪ • • • ∪ G[W (h )
] be the graph obtained from G by removing all the edges of G, apart from the ones that have both endpoints in the same witness set. In order to contract G to H, it is necessary and sufficient to contract all the edges of some spanning forest

F of G . Note that |E(F )| = i=1 (|W (h i )| -1) = |V (G)| -|V (H)|. A 2-coloring of a graph G is a function φ : V (G) → {1, 2}.
We point out that a 2-coloring of G is merely an assignment of colors 1 and 2 to the vertices of G, and should therefore not be confused with a proper 2-coloring of G, which is a 2-coloring with the additional property that no two adjacent vertices receive the same color. An edge uv is said to be good (with respect to φ) if φ(u) = φ(v), and uv is called bad (with respect to φ) otherwise. A good component of φ is the vertex set of a connected component of the graph (V (G), E ), where E ⊆ E is the set of all edges that are good with respect to φ. Any 2-coloring φ of G defines a partition of V (G) into two sets V 1 φ and V 2 φ , which are the sets of vertices of G colored 1 and 2 by φ, respectively. A set

X ⊆ V (G) is a monochromatic component of φ if G[X] is a connected component of G[V 1 φ ] or a connected component of G[V 2 φ ]
. We write

F S T T C S 2 0 1 1

M φ to denote the set of all monochromatic components of φ. The cost of a 2-coloring φ is defined as

X∈M φ (|X| -1). Note that the cost of a 2-coloring φ of G is 0 if and only if φ is a proper 2-coloring of G. Let G be a graph. A tree decomposition of G is a pair (T, X = {X t } t∈V (T )
), where T is a tree and X is a collection of subsets of V (G), satisfying the following three properties:

(1) ∪ t∈V (T ) X t = V ; (2) ∀uv ∈ E(G), ∃t ∈ V (T ) : {u, v} ⊆ X t ; and (3) ∀v ∈ V (G), T [{t : v ∈ X t }] is connected.
The width of a tree decomposition is max t∈V (T ) |X t | -1 and the treewidth of G, denoted tw(G), is the minimum width over all tree decompositions of G.

The syntax of monadic second order (MSO) logic of graphs includes the logical connectives ∨, ∧, ¬, variables for vertices, edges, sets of vertices and sets of edges, the quantifiers ∀, ∃ that can be applied to these variables, and the following five binary relations: Proof. Suppose G has a 2-coloring φ of cost at most k. We build an edge set S as follows.

u ∈ U ,
For each monochromatic component X ∈ M φ , find a spanning tree T X of G[X] and add the |X| -1 edges of T X to S. The total number of edges in S is exactly the cost of φ, so |S| ≤ k. It remains to argue that G = G/S is bipartite. Note that G is obtained from G by contracting each spanning tree T X to a single vertex t X . Let φ be the 2-coloring of G that assigns to each t X ∈ V (G ) the color of the corresponding monochromatic component X ∈ M φ . Since each monochromatic component has been contracted to a single vertex, G has no edge that is bad with respect to φ . Hence φ is a proper 2-coloring of G , implying that G is bipartite.

For the reverse direction, suppose there is a set S ⊆ E(G) of at most k edges such that G = G/S is bipartite. We define G * to be the graph with the same vertex set as G and edge set S, i.e., G * = (V (G), S). Let W be the G -witness structure of G whose witness sets are exactly the connected components of G * . Let φ be a proper 2-coloring of G . We construct a 2-coloring φ of G as follows. For every v ∈ V (G), we set φ(v) = φ (y), where y is the vertex in V (G ) such that v ∈ W (y). Since the monochromatic components of φ are exactly the connected components of the graph G * , and since G * contains exactly |S| edges, the cost of φ is at most |S| ≤ k.

An instance of the Cheap Coloring problem consists of a graph G and an integer k, and the task is to decide whether G has a 2-coloring of cost at most k. Lemma 1 shows that the problems Bipartite Contraction and Cheap Coloring are equivalent.

The deletion of an edge can not increase the cost of a 2-coloring, and can only decrease the cost of a 2-coloring by at most one. We state this as the following observation.

Observation 1. Let φ be a 2-coloring of G of cost k. For any edge uv ∈ E(G), the cost of φ in G -uv is k or k -1.
Observation 1 allows us to use the well-known iterative compression technique of Reed, Smith and Vetta [START_REF] Reed | Finding odd cycle transversals[END_REF] to reduce the Cheap Coloring problem to the Cheaper Coloring problem. The Cheaper Coloring problem takes as input a graph G, an integer k, and a 2-coloring φ of G of cost k + 1, and the task is to either find a 2-coloring of G of cost at most k, or to conclude that such a coloring does not exist. Lemma 2. If there is an algorithm for Cheaper Coloring that runs in time f (k) n c for some constant c, then there is an algorithm for Cheap Coloring that runs in time f (k) n c m.

Proof. Suppose there exists an algorithm for Cheaper Coloring that runs in time f (k) n c . Then we can solve an instance (G, k) of Cheap Coloring by iterating over the edges e 1 , e 2 , . . . e m of G as follows. For every i ∈ {1, . . . , m}, we define G i to be the graph with vertex set V (G) and edge set E i = {e j : j ≤ i}. The graph G 1 has a 2-coloring φ 1 of cost 0, which is at most k. For the first k iterations, we trivially maintain a 2-coloring of cost at most k. Now, in iteration i of the algorithm, assume that we have a 2-coloring φ i of cost at most k in G i . By Observation 1, the cost of φ i in G i+1 is at most k + 1. If the cost of φ i in G i+1 is at most k, then we proceed to iteration i + 1. Otherwise, we run the algorithm for Cheaper Coloring with input (G i+1 , k, φ i ). If the algorithm concludes that G i+1 has no 2-coloring of cost at most k, then, by Observation 1, neither does G. If, on the other hand, the algorithm outputs a 2-coloring φ i+1 of G i+1 of cost at most k, then we proceed to the (i + 1)th iteration. Since we call the algorithm for Cheaper Coloring at most m times, each time with parameter k, the time bound follows.

We have now almost reached the variant of the problem that will be the focus of attention in the remainder of this paper. Given a graph G and two disjoint vertex sets T 1 , T 2 ⊆ V (G), a 2-coloring φ of G is a (T 1 , T 2 )-extension if φ colors every vertex in T 1 with 1 and every vertex in T 2 with 2. In the Cheap Coloring Extension problem we are given a bipartite graph G, two integers k and t, and two disjoint vertex sets T 1 and T 2 such that |T 1 |+|T 2 | ≤ t; the sets T 1 and T 2 are not related to the sets of the bipartition of G. The objective is to find a (T 1 , T 2 )-extension φ of cost at most k, or to conclude that such a 2-coloring does not exist. We will say that a (T 1 , T 2 )-extension φ is a cheapest (T 1 , T 2 )-extension if there is no (T 1 , T 2 )-extension φ with strictly lower cost than φ. Lemma 3. If there is an algorithm for Cheap Coloring Extension that runs in time f (k, t) n c for some constant c, then there is an algorithm for Cheaper Coloring that runs in time

4 k+1 f (k, 2k + 2) n c .
Proof. Given an f (k, t) n c time algorithm for Cheap Coloring Extension, we show how to solve an instance (G, k, φ) of Cheaper Coloring. Let S be the set of all bad edges in G with respect to φ, and let X be the set of endpoints of the edges in S. Since φ has cost k + 1, we have |X| ≤ 2k + 2. We create 4 k+1 instances of Cheap Coloring Extension as follows.

For every possible partition of X into two sets X 1 and X 2 , we set k = k and t = |X|, and we build a graph G(X 1 , X 2 ) from G in the following way. As long as there is an edge uv ∈ S such that u and v are both in X 1 or both in X 2 , contract the edge uv, put the new vertex resulting from the contraction into the set X i that u and v belonged to, and decrease

F S T T C S 2 0 1 1

k by 1. Since the cost of φ is at most k + 1, we contract at most k + 1 edges in this way, and hence k ≥ -1. When there are no such edges left, then we discard this partition of X into X 1 and X 2 if k = -1; otherwise, we continue to build an instance of Cheap Coloring Extension as follows. Delete all edges uv ∈ S with u ∈ X i and v ∈ X j such that i = j. Since S contains all the edges of G that are bad with respect to φ, and each of the edges of S is either contracted or deleted, the resulting graph G(X 1 , X 2 ) has no bad edges with respect to φ and is therefore bipartite. Thus we obtain an instance (G(X 1 , X 2 ), k , t, X 1 , X 2 ) of Cheap Coloring Extension with k ≥ 0.

We now show that (G, k, φ) is a yes-instance of Cheaper Coloring if and only if there is a partition of X into X 1 and X 2 such that (G(X 1 , X 2 ), k , t, X 1 , X 2 ) with k ≥ 0 is a yes-instance of Cheap Coloring Extension.

Suppose that (G, k, φ) is a yes-instance of Cheaper Coloring. Then there exists a 2-coloring φ * of G of cost at most k. Let X 1 and X 2 be the vertices of X that are colored 1 and 2 by φ * , respectively. Consider the set S ⊆ S of edges that were contracted in order to obtain G(X 1 , X 2 ) from G in the way described earlier. Since every edge in S is bad with respect to φ * , the cost of φ * decreased by 1 with every edge contraction. Hence, φ * is an

(X 1 , X 2 )-extension of G(X 1 , X 2 ) of cost k . We conclude that (G(X 1 , X 2 ), k , t, X 1 , X 2 ) is a yes-instance of Cheap Coloring Extension.
For the reverse direction, suppose there is a partition of X into X 1 and X 2 such that (G(X 1 , X 2 ), k , t, X 1 , X 2 ) is a yes-instance of Cheap Coloring Extension with k ≥ 0, i.e., the bipartite graph G(X 1 , X 2 ) has an (X 1 , X 2 )-extension ψ of cost at most k . Let S ⊆ S be the set of edges that were contracted in

G to create the instance (G(X 1 , X 2 ), k , t, X 1 , X 2 ). Since k = k -|S | ≥ 0, we have that |S | ≤ k.
We define a 2-coloring θ of G by coloring both endpoints of every edge uv in S with the color that ψ assigned to the vertex resulting from the contraction of the edge uv, and coloring all other vertices in G with the color they received from ψ. Clearly, the cost of θ is at most k + |S | = k, and therefore (G, k, φ) is a yes-instance of Cheaper Coloring.

Since we need to run the f (k, t) n c time algorithm for Cheap Coloring Extension at most 4 k+1 times, with parameters k ≤ k and t = |X| ≤ 2k + 2 at each iteration, the time bound follows.

The next section is devoted to showing that Cheap Coloring Extension is fixed parameter tractable when parameterized by k and t. The reason we want to work with the Cheap Coloring Extension problem rather than with the Bipartite Contraction problem directly is that, as we shall see in Section 4.2, Cheap Coloring Extension is a "cut" problem, and is therefore amenable to techniques based on important separators [START_REF] Marx | Parameterized graph separation problems[END_REF].

Solving Cheap Coloring Extension in FPT Time

In this section, we present an algorithm for the Cheap Coloring Extension problem. For the remainder of this section, let (G, k, t, T 1 , T 2 ) be a given instance of Cheap Coloring Extension, where G is assumed to be connected. Recall that G is bipartite. The high level structure of our algorithm is as follows. If the treewidth of G is bounded by a function of k and t, then we can use standard dynamic programming techniques to solve the problem in time f (k, t) n. If, on the other hand, the treewidth of G is large, then we can find a large set of vertices which is "highly connected". In this case we show how to find in f (k, t) n O (1) time an edge e ∈ E(G), such that G has a (T 1 , T 2 )-extension of cost at most k if and only if G -e does. We then re-run our algorithm on G -e.

To make the distinction between the two cases in our algorithm more precise, we use the following notion, due to Diestel et al. [START_REF] Diestel | Highly connected sets and the excluded grid theorem[END_REF]. A set

X ⊆ V (G) is p-connected in G if |X| ≥ p and, for all subsets X 1 , X 2 ⊆ X with |X 1 | = |X 2 | ≤ p, there are |X 1 | vertex-disjoint paths
in G with one endpoint in X 1 and the other in X 2 . Diestel et al. [START_REF] Diestel | Highly connected sets and the excluded grid theorem[END_REF] prove the following statement in the proof of Proposition 3 (ii): if h ≥ p and G contains no p-connected set of size h, then G has treewidth < h + p -1. (In fact, they prove a stronger version of this statement using the notion of an externally p-connected set, but we do not need this stronger assertion for our purposes.) We define a set X to be well-connected if it is |X|/2-connected.

Using this definition, the result of Diestel et al. [START_REF] Diestel | Highly connected sets and the excluded grid theorem[END_REF] can be seen to imply the following.

Theorem 4 ([7]

). If tw(G) > w, then G contains a well-connected set of size at least 2w/3. The proof of Theorem 4 is constructive. In fact, given G and w, a tree decomposition of width at most w or a well-connected set of size at least 2w/3 can be computed in time c w n O (1) for some constant c [START_REF] Diestel | Highly connected sets and the excluded grid theorem[END_REF]. We use Theorem 4 to compute either a tree-decomposition of G of width at most 3(4k 2 ) t 4 4k 2 +3 or a well-connected set Y of size at least 2(4k 2 ) t 4 4k 2 +2. Section 4.1 deals with the first case, whereas the second case is covered in Section 4.2.

Small Treewidth

Suppose our algorithm has found a tree-decomposition of G of width at most 3(4k 2 ) t 4 4k 2 +3. We use the following celebrated theorem by Courcelle [START_REF] Courcelle | The monadic second-order logic of graphs. I. Recognizable sets of finite graphs[END_REF] to solve the Cheap Coloring Extension problem in this case.

Theorem 5 ([3]).

There is an algorithm that tests whether a monadic second order formula ψ holds on a graph G of treewidth w, in time f (|ψ|, w) n.

Since Cheap Coloring Extension can be expressed in monadic second order logic (we omit the details due to page restrictions), we have the following result. Lemma 6. There is an algorithm that, given an instance (G, k, t, T 1 , T 2 ) of Cheap Coloring Extension together with a tree-decomposition of G of width w, solves the instance in time f (k, t, w) n.

We would like to remark that, given an instance (G, k, t, T 1 , T 2 ) of Cheap Coloring Extension together with a tree-decomposition of G of width w, it is possible to solve that instance in time (w + 1) O(w) n using standard dynamic programming techniques, which gives a much faster algorithm than the one obtained by applying Theorem 5 on the monadic second order formula.

Large Treewidth and Irrelevant Edges

Suppose our algorithm did not find a tree-decomposition of G of small width, but instead found a well-connected set Y of size at least 2(4k 2 ) t 4 4k 2 + 2. We use Y throughout this section to refer to this specific set. An edge e ∈ E(G) is said to be irrelevant if it satisfies the following property: G has a (T 1 , T 2 )-extension of cost at most k if and only if G -e does. We will show that the presence of the large well-connected set Y guarantees the presence of an irrelevant edge e in G. Hence we find such an irrelevant edge e in G, delete it from the graph, and solve Cheap Coloring Extension on the instance (G -e, k, t, T 1 , T 2 ). Since each iteration of this process deletes an edge, we will find a tree-decomposition of the graph under consideration of small width after at most m iterations, in which case we solve the problem as described in Section 4.1.

F S T T C S 2 0 1 1

Observation 2. Let φ be a 2-coloring of G. No bad edge has both endpoints in the same good component of φ.

Proof. Suppose, for contradiction, that G has a bad edge uv such that both u and v belong to a good component C of φ. Since uv is bad, we have φ(u) = φ(v). Every good component is connected, so there is a path P in C, starting in u and ending in v, consisting only of good edges. The path P must contain an even number of edges, implying that P and uv together form an odd cycle in G. This contradicts the assumption that G, which is part of the instance (G, k, t, T 1 , T 2 ) of Cheap Coloring Extension that we are solving, is bipartite.

Observation 3. Let uv ∈ E(G). If φ is a cheapest (T 1 , T 2 )
-extension of G -uv and u and v are in the same good component of φ, then uv is irrelevant.

Proof. Suppose u and v belong to the same good component of a cheapest (T 1 , T 2 )-extension φ of G -uv. Note that φ is a 2-coloring of G, and that the edge uv in G is good with respect to φ as a result of Observation 2. Hence φ is a (T 1 , T 2 )-extension of G, and the cost of φ in G equals the cost of φ in G -uv. As a result of Observation 1, φ must be a cheapest (T 1 , T 2 )-extension of G. Since the cost of a cheapest (T 1 , T 2 )-extension of G -uv equals the cost of a cheapest (T 1 , T 2 )-extension of G, the edge uv is irrelevant by definition.

In order to use Observation 3, we need to identify two adjacent vertices u and v in G that will end up in the same good component of some cheapest (T 1 , T 2 )-extension of G -uv. The vertices in Y are good candidates, because they are so highly connected to each other. Over the next few lemmas we formalize this intuition. We start with two observations that will allow us, in the proof of Lemma 7 below, to bound the number of bad edges and the number of good components of a cheapest (T 1 , T 2 )-extension of G of cost at most k.

2 = 2k 2 -k < 2k 2 . Observation 5. Let φ be a cheapest (T 1 , T 2 )-extension of G. Every good component of φ contains a vertex from T 1 ∪ T 2 .
Proof. Suppose a good component C of φ does not contain any vertex from T 1 ∪ T 2 . We build a coloring φ from φ by changing the color of every vertex in C, leaving the color of every other vertex unchanged, i.e., φ (

v) = 3 -φ(v) if v ∈ C, and φ (v) = φ(v) if v / ∈ C. Since φ(v) = φ (v) for every v ∈ T 1 ∪ T 2 , φ is a (T 1 , T 2 )-extension of G.
Furthermore, every edge that was good with respect to φ is good with respect to φ , while every edge in δ G (C) was bad with respect to φ and is good with respect to φ . Recall that G is assumed to be connected. Hence there is some vertex v ∈ C which is incident to at least one edge that was bad with respect to φ. On the other hand, all edges incident to v are good with respect to φ . Hence {v} is a monochromatic component of φ , but {v} was not a monochromatic component of φ. This means that |M φ | < |M φ |. This, together with the observation that the number of edges that are bad with respect to φ is not higher than the number of edges that were bad with respect to φ, implies that the cost of φ is strictly less than the cost of φ. This contradicts the assumption that φ is a cheapest (T 1 , T 2 )-extension of G.

The next lemma shows that almost all the vertices of Y appear in the same good component of any cheapest (T 1 , T 2 )-extension φ of G of cost at most k. In fact, we prove that the same holds if we remove any edge of G. There are two problems with how to exploit the knowledge obtained from Lemma 7. The first is that, even though we know that almost all the vertices of Y appear in the same good component together, we do not know exactly which ones do. The second problem is that we are looking for an edge with both endpoints in the same good component, and Y could be an independent set and thus not immediately give us an edge to delete. We deal with both problems by employing the very useful notion of important sets. For two vertices x, y ∈ V (G), we say that a set X ⊆ V (G) is (x, y)-important if it satisfies the following three properties: [START_REF] Asano | Edge-contraction problems[END_REF] x ∈ X and y / ∈ X; (2) G[X] is connected; and (3) there is no X ⊃ X, y ∈ X such that d G (X ) ≤ d G (X) and G[X ] is connected. The following theorem was first proved in [START_REF] Chen | An improved parameterized algorithm for the minimum node multiway cut problem[END_REF]. We use here the formulation in [START_REF] Lokshtanov | Marx Clustering with local restrictions[END_REF], because that one best fits the purposes of this paper.

Theorem 8 ([4, 19]). Let x, y be two vertices in a graph G. For every p ≥ 0, there are at most 4 p (x, y)-important sets X such that d G (X) ≤ p. Furthermore, these important sets can be enumerated in time 4 p • n O (1) . Suppose G -uv has a cheapest (T 1 , T 2 )-extension φ of cost at most k for an edge uv ∈ E(G). We will use the important sets together with Lemma 7 to identify vertices in Y which must be in the unique good component C * of φ that contains all but at most 2k 2 vertices of Y . We first build a graph G * from G by adding a new vertex y * and making y * adjacent to all vertices in Y . We then enumerate all x ∈ T 1 ∪ T 2 and all (x, y * )-important sets X in G * such that d G * (X) ≤ 4k 2 . By Theorem 8, this can be done in time 4 4k 2 n O (1) for each choice F S T T C S 2 0 1 1

Observation 4 .

 4 Let φ be a 2-coloring of G. If φ has cost at most k, then there are less than 2k 2 bad edges. Proof. Let M φ = {X ∈ M φ : |X| ≥ 2} be the set of monochromatic components of φ containing more than one vertex, and let G be the disjoint union of the graphs induced in G by the elements of M φ , i.e., G = X∈M φ G[X]. By definition, the cost of φ is X∈M φ (|X| -1) = X∈M φ (|X| -1), which is exactly the number of edges in any spanning forest of G . Since any forest on at most k edges without isolated vertices has at most 2k vertices, we have |V (G )| ≤ 2k. Every bad edge has both endpoints in V (G ), so the number of bad edges is at most 2k

Lemma 7 .

 7 Let uv ∈ E(G) and let φ be a cheapest (T 1 , T 2 )-extension of G -uv. If φ has cost at most k, then there exists exactly one good component C * of φ satisfying |Y \C * | ≤ 2k 2 , and every other good component C of φ satisfies |Y ∩ C | ≤ 2k 2 . Proof. Suppose φ has cost at most k, and let C be a good component of φ. We first show that either |Y \ C| ≤ 2k 2 or |Y ∩ C| ≤ 2k 2 . Suppose for contradiction that |Y ∩ C| > 2k 2 and |Y \ C| > 2k 2 . We define Y 1 to be the smallest of the two sets Y ∩ C and Y \ C, and Y 2 to be any subset of the largest of the two sets such that |Y 2 | = |Y 1 |. Note that 2k 2 + 1 ≤ |Y 1 | = |Y 2 | ≤ |Y |/2. By the definition of a well-connected set, there are |Y 1 | ≥ 2k 2 + 1 vertex-disjoint paths with one endpoint in Y ∩ C and the other in Y \ C. At least 2k 2 of these paths exist in G -uv, and each of those must contain an edge in δ G-uv (C). Since each edge in δ G-uv (C) is bad, it follows that φ has at least 2k 2 bad edges, contradicting Observation 4. Now suppose for contradiction that φ does not have a good component C * with |Y \C * | ≤ 2k 2 . Then |Y ∩ C| ≤ 2k 2 for every good component C of φ, as we showed earlier. Since φ has at most t = |T 1 | + |T 2 | good components as a result of Observation 5, at most t 2k 2 vertices of Y appear in good components. The fact that the size of Y is much larger than t 2k 2 , together with the observation that every vertex of G appears in a good component by definition, yields the desired contradiction. Hence we know that φ has a good component C * with |Y \ C * | ≤ 2k 2 . The uniqueness of C * follows from the sizes of Y and C * , and the fact that the good components of φ are pairwise disjoint.

supported by the Research Council of Norway.

Obtaining a Bipartite Graph by Contracting Few Edges of x. Finally, we define the set Z to be the union of all enumerated sets X. In other words,

Observe that, given G and Y , Z can be computed in time t 4 4k 2 n O (1) . We will use the set Z in the following way. First we show that if there is an edge uv ∈ E(G) such that neither u nor v belongs to Z, then the edge uv is irrelevant. Then we show that such an edge always exists.

Proof. Let φ be a cheapest (T

We conclude that both u and v belong to the good component C * , and hence, by Observation 3, uv is irrelevant.

Lemma 10. G contains an edge uv such that u /

∈ Z and v / ∈ Z.

Proof. We first prove that d G (Z) ≤ (4k

assumption. Since all of the u i 's are in Y 1 , none of them are in Z. Thus, each v i that belongs to Z contributes one to d G (Z), as then u i v i ∈ δ G (Z). Since we bounded d G (Z) from above by (4k 2 ) t 4 4k 2 at the start of this proof, not every v i can belong to Z. Hence there is an edge u i v i with neither endpoint in Z.

We are now ready to state the main lemma of this section.

Lemma 11. Cheap Coloring Extension can be solved in time f (k, t) n O (1) .

Proof. Let (G, k, t, T 1 , T 2 ) be an instance of Cheap Coloring Extension, and let f be an appropriate function that does not depend on n. We first apply Theorem 4 and the remark immediately following it to compute, in time f (k, t) n O (1) , either a tree-decomposition of G of width at most 3(4k 2 ) t 4 4k 2 + 3 or a well-connected set Y of size at least 2(4k 2 ) t 4 4k 2 + 2.

If we get a tree-decomposition of small width, we apply Lemma 6 to solve the problem in additional time f (k, t) n. If we find a well-connected set Y , we continue to find an irrelevant edge e ∈ E(G) and delete it from G. Lemmas 9 and 10 guarantee that such an edge always exists. In order to find e, we first compute the set Z. We already argued that this can be done in time f (k, t) n O (1) if G and Y are given. We can find an irrelevant edge as explained in the proof of Lemma 10 in additional polynomial time, since this amounts to computing Z ∩ Y , choosing Y 2 to contain the whole intersection and as many more vertices as needed to obtain

and checking all edges leaving Y 1 to find one whose endpoints do not belong to Z. The total running time of this whole procedure is clearly f (k, t) n O (1) . After an irrelevant edge e is deleted from G, we run the whole procedure on (Ge, k, t, T 1 , T 2 ). This can be repeated at most |E(G)| = n O (1) times, and hence the total running time f (k, t) n O (1) follows.

Our main result immediately follows from Lemmas 1, 2, 3, and 11.

Theorem 12. Bipartite Contraction is fixed parameter tractable when parameterized by k.

We end this section with a remark on the running time. If we use Lemma 6 in the proof of Lemma 11, then the parameter dependence of the whole algorithm is dominated by a very large function in k [START_REF] Courcelle | The monadic second-order logic of graphs. I. Recognizable sets of finite graphs[END_REF]. However, as we remarked after Lemma 6, we can obtain a running time of (4

n for the small treewidth case in the proof of Lemma 11. This is because the treewidth of the instance at hand is 4

when the small treewidth case applies. This gives a total running time of of 2 2 O(k 2 ) n O (1) for our algorithm for Bipartite Contraction.

Concluding Remarks

We showed that Bipartite Contraction is fixed parameter tractable. A highly relevant question is whether this problem admits a polynomial kernel, i.e., a polynomial time algorithm that transforms an instance (G, k) into an equivalent instance (G , k ) of size g(k), where g is a polynomial in k. Very recently, Kratsch and Wahlström [START_REF] Kratsch | Compression via matroids: a randomized polynomial kernel for Odd Cycle Transversal[END_REF] announced that the problems OCT and Edge Bipartization admit randomized polynomial kernels, which can be obtained using a novel kernelization approach based on matroid theory. We conclude with the following question: Can some of the algorithms that currently use Robertson-Seymour machinery to find an irrelevant vertex, be modified in such a way that they find an irrelevant vertex using p-connected sets instead?