Vertex deletion into bipartite permutation graphs

2020
book section
conference proceedings
4
dc.abstract.enA permutation graph can be defined as an intersection graph of segments whose endpoints lie on two parallel lines 𝓁₁ and 𝓁₂, one on each. A bipartite permutation graph is a permutation graph which is bipartite. In this paper we study the parameterized complexity of the bipartite permutation vertex deletion problem, which asks, for a given n-vertex graph, whether we can remove at most k vertices to obtain a bipartite permutation graph. This problem is NP-complete by the classical result of Lewis and Yannakakis [John M. Lewis and Mihalis Yannakakis, 1980]. We analyze the structure of the so-called almost bipartite permutation graphs which may contain holes (large induced cycles) in contrast to bipartite permutation graphs. We exploit the structural properties of the shortest hole in a such graph. We use it to obtain an algorithm for the bipartite permutation vertex deletion problem with running time f(k)n^O(1), and also give a polynomial-time 9-approximation algorithm.pl
dc.affiliationWydział Matematyki i Informatyki : Instytut Informatyki Analitycznejpl
dc.affiliationSzkoła Doktorska Nauk Ścisłych i Przyrodniczychpl
dc.conference15th International Symposium on Parameterized and Exact Computation (IPEC 2020)pl
dc.conference.cityHong Kong
dc.conference.countryChiny
dc.conference.datefinish2020-12-18
dc.conference.datestart2020-12-14
dc.conference.shortcutIPEC
dc.contributor.authorBożyk, Łukaszpl
dc.contributor.authorDerbisz, Jan - 244282 pl
dc.contributor.authorKrawczyk, Tomasz - 129445 pl
dc.contributor.authorNovotná, Janapl
dc.contributor.authorOkrasa, Karolinapl
dc.date.accessioned2020-12-28T12:23:52Z
dc.date.available2020-12-28T12:23:52Z
dc.date.issued2020pl
dc.date.openaccess0
dc.description.accesstimew momencie opublikowania
dc.description.conftypeinternationalpl
dc.description.physical5:1-5:16pl
dc.description.publication0,9pl
dc.description.seriesLIPIcs - Leibniz International Proceedings in Informatics
dc.description.seriesnumberVol. 180
dc.description.versionostateczna wersja wydawcy
dc.identifier.doi10.4230/LIPIcs.IPEC.2020.5pl
dc.identifier.isbn978-3-95977-172-6pl
dc.identifier.projectUMO-2015/17/B/ST6/01873pl
dc.identifier.projectROD UJ / OPpl
dc.identifier.seriesissn1868-8969
dc.identifier.urihttps://ruj.uj.edu.pl/xmlui/handle/item/259372
dc.languageengpl
dc.language.containerengpl
dc.pubinfoDagstuhl : Schloss Dagstuhl - Leibniz-Zentrum für Informatikpl
dc.rightsUdzielam licencji. Uznanie autorstwa - Bez utworów zależnych 3.0*
dc.rights.licenceCC-BY
dc.rights.urihttp://creativecommons.org/licenses/by/3.0/legalcode*
dc.share.typeotwarte czasopismo
dc.subject.enpermutation graphspl
dc.subject.encomparability graphspl
dc.subject.enpartially ordered setpl
dc.subject.engraph modification problemspl
dc.subtypeConferenceProceedingspl
dc.titleVertex deletion into bipartite permutation graphspl
dc.title.container15th International Symposium on Parameterized and Exact Computation (IPEC 2020)pl
dc.typeBookSectionpl
dspace.entity.typePublication
dc.abstract.enpl
A permutation graph can be defined as an intersection graph of segments whose endpoints lie on two parallel lines 𝓁₁ and 𝓁₂, one on each. A bipartite permutation graph is a permutation graph which is bipartite. In this paper we study the parameterized complexity of the bipartite permutation vertex deletion problem, which asks, for a given n-vertex graph, whether we can remove at most k vertices to obtain a bipartite permutation graph. This problem is NP-complete by the classical result of Lewis and Yannakakis [John M. Lewis and Mihalis Yannakakis, 1980]. We analyze the structure of the so-called almost bipartite permutation graphs which may contain holes (large induced cycles) in contrast to bipartite permutation graphs. We exploit the structural properties of the shortest hole in a such graph. We use it to obtain an algorithm for the bipartite permutation vertex deletion problem with running time f(k)n^O(1), and also give a polynomial-time 9-approximation algorithm.
dc.affiliationpl
Wydział Matematyki i Informatyki : Instytut Informatyki Analitycznej
dc.affiliationpl
Szkoła Doktorska Nauk Ścisłych i Przyrodniczych
dc.conferencepl
15th International Symposium on Parameterized and Exact Computation (IPEC 2020)
dc.conference.city
Hong Kong
dc.conference.country
Chiny
dc.conference.datefinish
2020-12-18
dc.conference.datestart
2020-12-14
dc.conference.shortcut
IPEC
dc.contributor.authorpl
Bożyk, Łukasz
dc.contributor.authorpl
Derbisz, Jan - 244282
dc.contributor.authorpl
Krawczyk, Tomasz - 129445
dc.contributor.authorpl
Novotná, Jana
dc.contributor.authorpl
Okrasa, Karolina
dc.date.accessioned
2020-12-28T12:23:52Z
dc.date.available
2020-12-28T12:23:52Z
dc.date.issuedpl
2020
dc.date.openaccess
0
dc.description.accesstime
w momencie opublikowania
dc.description.conftypepl
international
dc.description.physicalpl
5:1-5:16
dc.description.publicationpl
0,9
dc.description.series
LIPIcs - Leibniz International Proceedings in Informatics
dc.description.seriesnumber
Vol. 180
dc.description.version
ostateczna wersja wydawcy
dc.identifier.doipl
10.4230/LIPIcs.IPEC.2020.5
dc.identifier.isbnpl
978-3-95977-172-6
dc.identifier.projectpl
UMO-2015/17/B/ST6/01873
dc.identifier.projectpl
ROD UJ / OP
dc.identifier.seriesissn
1868-8969
dc.identifier.uri
https://ruj.uj.edu.pl/xmlui/handle/item/259372
dc.languagepl
eng
dc.language.containerpl
eng
dc.pubinfopl
Dagstuhl : Schloss Dagstuhl - Leibniz-Zentrum für Informatik
dc.rights*
Udzielam licencji. Uznanie autorstwa - Bez utworów zależnych 3.0
dc.rights.licence
CC-BY
dc.rights.uri*
http://creativecommons.org/licenses/by/3.0/legalcode
dc.share.type
otwarte czasopismo
dc.subject.enpl
permutation graphs
dc.subject.enpl
comparability graphs
dc.subject.enpl
partially ordered set
dc.subject.enpl
graph modification problems
dc.subtypepl
ConferenceProceedings
dc.titlepl
Vertex deletion into bipartite permutation graphs
dc.title.containerpl
15th International Symposium on Parameterized and Exact Computation (IPEC 2020)
dc.typepl
BookSection
dspace.entity.type
Publication
Affiliations

* The migration of download and view statistics prior to the date of April 8, 2024 is in progress.

Views
19
Views per month
Views per city
Krakow
7
Dublin
3
Ashburn
2
Wroclaw
2
Olsztyn
1
Shenzhen
1
Warsaw
1
Downloads
derbisz_krawczyk_et-al_vertex_deletion_into_bipartite_2020.pdf
1