<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, Daniël</dc:creator>
  <dc:creator>Ries, Bernard</dc:creator>
  <dc:date>2024</dc:date>
  <dc:description xmlns:ns0="xml" ns0:lang="en">The (Perfect) Matching Cut problem is to decide if a graph 𝐺 has a (perfect) matching cut, i.e., a (perfect) matching that is also an edge cut of 𝐺. Both Matching Cut and Perfect Matching Cut are known to be NP-complete. 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 perform a complexity study for the Maximum Matching Cut problem, which is to determine a largest matching cut in a graph. Our results yield full dichotomies of Maximum Matching Cut for graphs of bounded diameter, bounded radius and 𝐻-free graphs. A disconnected perfect matching of a graph 𝐺 is a perfect matching that contains a matching cut of 𝐺. We also show how our new techniques can be used for finding a disconnected perfect matching with a largest matching cut for special graph classes. In this way we can prove that the decision problem Disconnected Perfect Matching is polynomial-time solvable for (𝑃6 + 𝑠𝑃2)-free graphs for every 𝑠 ≥ 0, extending a known result for 𝑃5-free graphs (Bouquet and Picouleau, 2020).</dc:description>
  <dc:format>application/pdf</dc:format>
  <dc:identifier>https://folia.unifr.ch/global/documents/329174</dc:identifier>
  <dc:identifier>https://folia.unifr.ch/documents/329174/files/matchingcut.pdf</dc:identifier>
  <dc:language>eng</dc:language>
  <dc:relation>info:eu-repo/semantics/altIdentifier/doi/10.1016/j.tcs.2024.114795</dc:relation>
  <dc:relation>info:eu-repo/semantics/altIdentifier/issn/0304-3975</dc:relation>
  <dc:rights>info:eu-repo/semantics/openAccess</dc:rights>
  <dc:rights>CC BY</dc:rights>
  <dc:source>Theoretical Computer Science. - Elsevier BV. - 2024, vol. 1017, p. 114795</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_6501</dc:type>
</oai_dc:dc>