An FPT Algorithm for Matching Cut and d-Cut

Aravind, N. R. and Saxena, R. (2021) An FPT Algorithm for Matching Cut and d-Cut. In: 32nd International Workshop on Combinatorial Algorithms, IWOCA 2021, 5 July 2021 through 7 July 2021, Virtual, Online.

Full text not available from this repository. (Request a copy)

Abstract

For a positive integer d, the d-CUT is the problem of deciding if an undirected graph G= (V, E) has a nontrivial bipartition (A, B) of V such that every vertex in A (resp. B) has at most d neighbors in B (resp. A). When d= 1, this is the MATCHING CUT problem. Gomes and Sau [9] gave the first fixed-parameter tractable algorithm for d-CUT parameterized by the maximum number of the crossing edges in the cut (i.e., the size of edge cut). However, their paper does not provide an explicit bound on the running time, as it indirectly relies on an MSOL formulation and Courcelle’s Theorem [5]. Motivated by this, we design and present an FPT algorithm for the MATCHING CUT (and more generally for d-CUT) for general graphs with running time 2O ( k log k )nO ( 1 ) where k is the maximum size of the edge cut. This is the first FPT algorithm for the MATCHING CUT (and d-CUT) with an explicit dependence on this parameter. We also observe that MATCHING CUT cannot be solved in 2o ( k )nO ( 1 ) unless ETH fails.

[error in script]

IITH Creators: