Report
View in EDS

On The Complexity of Matching Cut for Graphs of Bounded Radius and $H$-Free Graphs

Bibliographic Details
Title: On The Complexity of Matching Cut for Graphs of Bounded Radius and $H$-Free Graphs
Authors: Lucke, Felicia, Paulusma, Daniël, Ries, Bernard
Publication Year: 2022
Subject Terms: Mathematics - Combinatorics, Computer Science - Computational Complexity, Computer Science - Discrete Mathematics, Computer Science - Data Structures and Algorithms
More Details: For a connected graph $G=(V,E)$, a matching $M\subseteq E$ is a matching cut of $G$ if $G-M$ is disconnected. It is known that for an integer $d$, the corresponding decision problem Matching Cut is polynomial-time solvable for graphs of diameter at most $d$ if $d\leq 2$ and NP-complete if $d\geq 3$. We prove the same dichotomy for graphs of bounded radius. For a graph $H$, a graph is $H$-free if it does not contain $H$ as an induced subgraph. As a consequence of our result, we can solve Matching Cut in polynomial time for $P_6$-free graphs, extending a recent result of Feghali for $P_5$-free graphs. We then extend our result to hold even for $(sP_3+P_6)$-free graphs for every $s\geq 0$ and initiate a complexity classification of Matching Cut for $H$-free graphs.
Document Type: Working Paper
Access URL: http://arxiv.org/abs/2204.07129
Accession Number: edsarx.2204.07129
Database: arXiv
FullText Text:
  Availability: 0
CustomLinks:
  – Url: http://arxiv.org/abs/2204.07129
    Name: EDS - Arxiv
    Category: fullText
    Text: View this record from Arxiv
    MouseOverText: View this record from Arxiv
  – Url: https://resolver.ebsco.com/c/xy5jbn/result?sid=EBSCO:edsarx&genre=article&issn=&ISBN=&volume=&issue=&date=20220414&spage=&pages=&title=On The Complexity of Matching Cut for Graphs of Bounded Radius and $H$-Free Graphs&atitle=On%20The%20Complexity%20of%20Matching%20Cut%20for%20Graphs%20of%20Bounded%20Radius%20and%20%24H%24-Free%20Graphs&aulast=Lucke%2C%20Felicia&id=DOI:
    Name: Full Text Finder (for New FTF UI) (s8985755)
    Category: fullText
    Text: Find It @ SCU Libraries
    MouseOverText: Find It @ SCU Libraries
Header DbId: edsarx
DbLabel: arXiv
An: edsarx.2204.07129
RelevancyScore: 1028
AccessLevel: 3
PubType: Report
PubTypeId: report
PreciseRelevancyScore: 1027.64074707031
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: On The Complexity of Matching Cut for Graphs of Bounded Radius and $H$-Free Graphs
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Lucke%2C+Felicia%22">Lucke, Felicia</searchLink><br /><searchLink fieldCode="AR" term="%22Paulusma%2C+Daniël%22">Paulusma, Daniël</searchLink><br /><searchLink fieldCode="AR" term="%22Ries%2C+Bernard%22">Ries, Bernard</searchLink>
– Name: DatePubCY
  Label: Publication Year
  Group: Date
  Data: 2022
– Name: Subject
  Label: Subject Terms
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Mathematics+-+Combinatorics%22">Mathematics - Combinatorics</searchLink><br /><searchLink fieldCode="DE" term="%22Computer+Science+-+Computational+Complexity%22">Computer Science - Computational Complexity</searchLink><br /><searchLink fieldCode="DE" term="%22Computer+Science+-+Discrete+Mathematics%22">Computer Science - Discrete Mathematics</searchLink><br /><searchLink fieldCode="DE" term="%22Computer+Science+-+Data+Structures+and+Algorithms%22">Computer Science - Data Structures and Algorithms</searchLink>
– Name: Abstract
  Label: Description
  Group: Ab
  Data: For a connected graph $G=(V,E)$, a matching $M\subseteq E$ is a matching cut of $G$ if $G-M$ is disconnected. It is known that for an integer $d$, the corresponding decision problem Matching Cut is polynomial-time solvable for graphs of diameter at most $d$ if $d\leq 2$ and NP-complete if $d\geq 3$. We prove the same dichotomy for graphs of bounded radius. For a graph $H$, a graph is $H$-free if it does not contain $H$ as an induced subgraph. As a consequence of our result, we can solve Matching Cut in polynomial time for $P_6$-free graphs, extending a recent result of Feghali for $P_5$-free graphs. We then extend our result to hold even for $(sP_3+P_6)$-free graphs for every $s\geq 0$ and initiate a complexity classification of Matching Cut for $H$-free graphs.
– Name: TypeDocument
  Label: Document Type
  Group: TypDoc
  Data: Working Paper
– Name: URL
  Label: Access URL
  Group: URL
  Data: <link linkTarget="URL" linkTerm="http://arxiv.org/abs/2204.07129" linkWindow="_blank">http://arxiv.org/abs/2204.07129</link>
– Name: AN
  Label: Accession Number
  Group: ID
  Data: edsarx.2204.07129
PLink https://login.libproxy.scu.edu/login?url=https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&scope=site&db=edsarx&AN=edsarx.2204.07129
RecordInfo BibRecord:
  BibEntity:
    Subjects:
      – SubjectFull: Mathematics - Combinatorics
        Type: general
      – SubjectFull: Computer Science - Computational Complexity
        Type: general
      – SubjectFull: Computer Science - Discrete Mathematics
        Type: general
      – SubjectFull: Computer Science - Data Structures and Algorithms
        Type: general
    Titles:
      – TitleFull: On The Complexity of Matching Cut for Graphs of Bounded Radius and $H$-Free Graphs
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Lucke, Felicia
      – PersonEntity:
          Name:
            NameFull: Paulusma, Daniël
      – PersonEntity:
          Name:
            NameFull: Ries, Bernard
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 14
              M: 04
              Type: published
              Y: 2022
ResultId 1