<oai_dc:dc xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:oai_dc="http://www.openarchives.org/OAI/2.0/oai_dc/" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.openarchives.org/OAI/2.0/oai_dc/ http://www.openarchives.org/OAI/2.0/oai_dc.xsd">
  <dc:creator>Lucke, Felicia</dc:creator>
  <dc:creator>Paulusma, Daniel</dc:creator>
  <dc:creator>Ries, Bernard</dc:creator>
  <dc:date>2023-08-21</dc:date>
  <dc:description xmlns:ns0="xml" ns0:lang="en">The (Perfect) Matching Cut problem is to decide if a graph G has a (perfect) matching cut, i.e., a (perfect) matching that is also an edge cut of G. Both Matching Cut and Perfect Matching Cut are known to be NP-complete, leading to many complexity results for both problems on special graph classes. A perfect matching cut is also a matching cut with maximum number of edges. To increase our understanding of the relationship between the two problems, we introduce the Maximum Matching Cut problem. This problem is to determine a largest matching cut in a graph. We generalize and unify known polynomial-time algorithms for Matching Cut and Perfect Matching Cut restricted to graphs of diameter at most 2 and to (P₆+sP₂)-free graphs. We also show that the complexity of Maximum Matching Cut differs from the complexities of Matching Cut and Perfect Matching Cut by proving NP-hardness of Maximum Matching Cut for 2P₃-free quadrangulated graphs of diameter 3 and radius 2 and for subcubic line graphs of triangle-free graphs. In this way, we obtain full dichotomies of Maximum Matching Cut for graphs of bounded diameter, bounded radius and H-free graphs.
</dc:description>
  <dc:format>application/pdf</dc:format>
  <dc:identifier>https://folia.unifr.ch/global/documents/325849</dc:identifier>
  <dc:identifier>https://folia.unifr.ch/documents/325849/files/matchingcuts.pdf</dc:identifier>
  <dc:language>eng</dc:language>
  <dc:relation>info:eu-repo/semantics/altIdentifier/doi/10.4230/LIPIcs.MFCS.2023.64</dc:relation>
  <dc:rights>info:eu-repo/semantics/openAccess</dc:rights>
  <dc:rights>CC BY</dc:rights>
  <dc:source>48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023) / Leroux, Jérôme ; Lombardy, Sylvain ; Peleg, David. - Schloss Dagstuhl - Leibniz-Zentrum für Informatik. - 2023, p. 64:1-64:15</dc:source>
  <dc:subject xmlns:ns1="xml" ns1:lang="en">matching cut</dc:subject>
  <dc:subject xmlns:ns2="xml" ns2:lang="en">perfect matching</dc:subject>
  <dc:subject xmlns:ns3="xml" ns3:lang="en">H-free graph</dc:subject>
  <dc:subject xmlns:ns4="xml" ns4:lang="en">diameter</dc:subject>
  <dc:subject xmlns:ns5="xml" ns5:lang="en">radius</dc:subject>
  <dc:subject xmlns:ns6="xml" ns6:lang="en">dichotomy</dc:subject>
  <dc:subject>info:eu-repo/classification/udc/004</dc:subject>
  <dc:title xmlns:ns7="xml" ns7:lang="en">Dichotomies for Maximum Matching Cut: H-Freeness, Bounded Diameter, Bounded Radius</dc:title>
  <dc:type>http://purl.org/coar/resource_type/c_5794</dc:type>
</oai_dc:dc>