Improved kernels for Signed Max Cut parameterized above lower bound on (r,l)-graphs
A graph $G$ is signed if each edge is assigned $+$ or $-$. A signed graph is balanced if there is a bipartition of its vertex set such that an edge has sign $-$ if and only if its endpoints are in different parts. The Edwards-Erd\"os bound states that every graph with $n$ vertices and $m$ edges...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2017-06-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/1540/pdf |
| _version_ | 1797270067756400640 |
|---|---|
| author | Luerbio Faria Sulamita Klein Ignasi Sau Rubens Sucupira |
| author_facet | Luerbio Faria Sulamita Klein Ignasi Sau Rubens Sucupira |
| author_sort | Luerbio Faria |
| collection | DOAJ |
| description | A graph $G$ is signed if each edge is assigned $+$ or $-$. A signed graph is
balanced if there is a bipartition of its vertex set such that an edge has sign
$-$ if and only if its endpoints are in different parts. The Edwards-Erd\"os
bound states that every graph with $n$ vertices and $m$ edges has a balanced
subgraph with at least $\frac{m}{2}+\frac{n-1}{4}$ edges. In the Signed Max Cut
Above Tight Lower Bound (Signed Max Cut ATLB) problem, given a signed graph $G$
and a parameter $k$, the question is whether $G$ has a balanced subgraph with
at least $\frac{m}{2}+\frac{n-1}{4}+\frac{k}{4}$ edges. This problem
generalizes Max Cut Above Tight Lower Bound, for which a kernel with $O(k^5)$
vertices was given by Crowston et al. [ICALP 2012, Algorithmica 2015]. Crowston
et al. [TCS 2013] improved this result by providing a kernel with $O(k^3)$
vertices for the more general Signed Max Cut ATLB problem. In this article we
are interested in improving the size of the kernels for Signed Max Cut ATLB on
restricted graph classes for which the problem remains hard. For two integers
$r,\ell \geq 0$, a graph $G$ is an $(r,\ell)$-graph if $V(G)$ can be
partitioned into $r$ independent sets and $\ell$ cliques. Building on the
techniques of Crowston et al. [TCS 2013], we provide a kernel with $O(k^2)$
vertices on $(r,\ell)$-graphs for any fixed $r,\ell \geq 0$, and a simple
linear kernel on subclasses of split graphs for which we prove that the problem
is still NP-hard. |
| first_indexed | 2024-04-25T01:58:23Z |
| format | Article |
| id | doaj.art-3e81a948f2f84ab488a8c418c2630511 |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T01:58:23Z |
| publishDate | 2017-06-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-3e81a948f2f84ab488a8c418c26305112024-03-07T15:32:48ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502017-06-01Vol. 19 no. 1Discrete Algorithms10.23638/DMTCS-19-1-141540Improved kernels for Signed Max Cut parameterized above lower bound on (r,l)-graphsLuerbio FariaSulamita KleinIgnasi Sauhttps://orcid.org/0000-0002-8981-9287Rubens SucupiraA graph $G$ is signed if each edge is assigned $+$ or $-$. A signed graph is balanced if there is a bipartition of its vertex set such that an edge has sign $-$ if and only if its endpoints are in different parts. The Edwards-Erd\"os bound states that every graph with $n$ vertices and $m$ edges has a balanced subgraph with at least $\frac{m}{2}+\frac{n-1}{4}$ edges. In the Signed Max Cut Above Tight Lower Bound (Signed Max Cut ATLB) problem, given a signed graph $G$ and a parameter $k$, the question is whether $G$ has a balanced subgraph with at least $\frac{m}{2}+\frac{n-1}{4}+\frac{k}{4}$ edges. This problem generalizes Max Cut Above Tight Lower Bound, for which a kernel with $O(k^5)$ vertices was given by Crowston et al. [ICALP 2012, Algorithmica 2015]. Crowston et al. [TCS 2013] improved this result by providing a kernel with $O(k^3)$ vertices for the more general Signed Max Cut ATLB problem. In this article we are interested in improving the size of the kernels for Signed Max Cut ATLB on restricted graph classes for which the problem remains hard. For two integers $r,\ell \geq 0$, a graph $G$ is an $(r,\ell)$-graph if $V(G)$ can be partitioned into $r$ independent sets and $\ell$ cliques. Building on the techniques of Crowston et al. [TCS 2013], we provide a kernel with $O(k^2)$ vertices on $(r,\ell)$-graphs for any fixed $r,\ell \geq 0$, and a simple linear kernel on subclasses of split graphs for which we prove that the problem is still NP-hard.https://dmtcs.episciences.org/1540/pdfcomputer science - data structures and algorithms05c85, 05c10g.2.2 |
| spellingShingle | Luerbio Faria Sulamita Klein Ignasi Sau Rubens Sucupira Improved kernels for Signed Max Cut parameterized above lower bound on (r,l)-graphs Discrete Mathematics & Theoretical Computer Science computer science - data structures and algorithms 05c85, 05c10 g.2.2 |
| title | Improved kernels for Signed Max Cut parameterized above lower bound on (r,l)-graphs |
| title_full | Improved kernels for Signed Max Cut parameterized above lower bound on (r,l)-graphs |
| title_fullStr | Improved kernels for Signed Max Cut parameterized above lower bound on (r,l)-graphs |
| title_full_unstemmed | Improved kernels for Signed Max Cut parameterized above lower bound on (r,l)-graphs |
| title_short | Improved kernels for Signed Max Cut parameterized above lower bound on (r,l)-graphs |
| title_sort | improved kernels for signed max cut parameterized above lower bound on r l graphs |
| topic | computer science - data structures and algorithms 05c85, 05c10 g.2.2 |
| url | https://dmtcs.episciences.org/1540/pdf |
| work_keys_str_mv | AT luerbiofaria improvedkernelsforsignedmaxcutparameterizedabovelowerboundonrlgraphs AT sulamitaklein improvedkernelsforsignedmaxcutparameterizedabovelowerboundonrlgraphs AT ignasisau improvedkernelsforsignedmaxcutparameterizedabovelowerboundonrlgraphs AT rubenssucupira improvedkernelsforsignedmaxcutparameterizedabovelowerboundonrlgraphs |