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)


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:
IITH CreatorsORCiD
Aravind, N R
Item Type: Conference or Workshop Item (Paper)
Additional Information: Series Title: Lecture Notes in Computer Science
Uncontrolled Keywords: Algorithms, Fixed-parameter tractable, Matching cut
Subjects: Computer science
Divisions: Department of Computer Science & Engineering
Depositing User: Mrs Haseena VKKM
Date Deposited: 10 Nov 2021 10:46
Last Modified: 07 Mar 2022 06:12
Publisher URL:
OA policy:
Related URLs:

Actions (login required)

View Item View Item
Statistics for RAIITH ePrint 8959 Statistics for this ePrint Item