Artykuł w czasopiśmie
Brak miniatury
Licencja
ClosedAccessDostęp zamknięty
 

Edge Bipartization Faster Than 2 k∗

Uproszczony widok
cris.lastimport.scopus2024-02-12T19:48:10Z
dc.abstract.enIn the EDGE BIPARTIZATION problem one is given an undirected graph G and an integer k, and the question is whether k edges can be deleted from G so that it becomes bipartite. In 2006, Guo et al. [J. Comput. Syst. Sci., 72(8):1386-1396, 2006] proposed an algorithm solving this problem in time O(2^k m^2); today, this algorithm is a textbook example of an application of the iterative compression technique. Despite extensive progress in the understanding of the parameterized complexity of graph separation problems in the recent years, no significant improvement upon this result has been yet reported. We present an algorithm for Edge Bipartization that works in time O(1.977^k nm), which is the first algorithm with the running time dependence on the parameter better than 2^k. To this end, we combine the general iterative compression strategy of Guo et al. [J. Comput. Syst. Sci., 72(8):1386-1396, 2006], the technique proposed by Wahlström [SODA'14] of using a polynomial-time solvable relaxation in the form of a Valued Constraint Satisfaction Problem to guide a bounded-depth branching algorithm, and an involved Measure&Conquer analysis of the recursion tree.
dc.affiliationUniwersytet Warszawski
dc.conference.countryDania
dc.conference.datefinish2016-08-26
dc.conference.datestart2016-08-24
dc.conference.placeAarhus
dc.conference.seriesInternational Symposium on Parameterized and Exact Computation (was IWPEC pre 2004)
dc.conference.seriesInternational Symposium on Parameterized and Exact Computation (was IWPEC pre 2004)
dc.conference.shortcutIPEC 2016
dc.conference.weblinkhttps://conferences.au.dk/algo16/ipec/
dc.contributor.authorPilipczuk, Michał
dc.contributor.authorWrochna, Marcin
dc.contributor.authorPilipczuk, Marcin
dc.date.accessioned2024-01-24T22:25:37Z
dc.date.available2024-01-24T22:25:37Z
dc.date.issued2017
dc.description.financeNie dotyczy
dc.description.volume63
dc.identifier.doi10.4230/LIPICS.IPEC.2016.26
dc.identifier.urihttps://repozytorium.uw.edu.pl//handle/item/105669
dc.identifier.weblinkhttps://drops.dagstuhl.de/opus/volltexte/2017/6928/
dc.languageeng
dc.pbn.affiliationcomputer and information sciences
dc.relation.pages26:1--26:13
dc.rightsClosedAccess
dc.sciencecloudnosend
dc.subject.enEdge bipartization
dc.subject.enFPT algorithm
dc.titleEdge Bipartization Faster Than 2 k∗
dc.typeJournalArticle
dspace.entity.typePublication