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

Exploring the Complexity of Layout Parameters in Tournaments and Semicomplete Digraphs

Uproszczony widok
cris.lastimport.scopus2024-02-12T19:51:55Z
dc.abstract.enA simple digraph is semicomplete if for any two of its vertices u and v, at least one of the arcs (u,v) and (v,u) is present. We study the complexity of computing two layout parameters of semicomplete digraphs: cutwidth and optimal linear arrangement (Ola). We prove the following: • Both parameters are NP-hard to compute and the known exact and parameterized algorithms for them have essentially optimal running times, assuming the Exponential Time Hypothesis. • The cutwidth parameter admits a quadratic Turing kernel, whereas it does not admit any polynomial kernel unless NP ⊆ coNP/poly. By contrast, Ola admits a linear kernel. These results essentially complete the complexity analysis of computing cutwidth and Ola on semicomplete digraphs (with respect to standard parameters). Our techniques also can be used to analyze the sizes of minimal obstructions for having a small cutwidth under the induced subdigraph relation.
dc.affiliationUniwersytet Warszawski
dc.contributor.authorPilipczuk, Michał
dc.contributor.authorPaul, Christophe
dc.contributor.authorBarbero, Florian
dc.date.accessioned2024-01-25T00:10:14Z
dc.date.available2024-01-25T00:10:14Z
dc.date.issued2018
dc.description.financeNie dotyczy
dc.description.number3
dc.description.volume14
dc.identifier.doi10.1145/3196276
dc.identifier.issn1549-6325
dc.identifier.urihttps://repozytorium.uw.edu.pl//handle/item/106818
dc.languageeng
dc.pbn.affiliationcomputer and information sciences
dc.relation.ispartofACM Transactions on Algorithms
dc.relation.pages1–31
dc.rightsClosedAccess
dc.sciencecloudnosend
dc.titleExploring the Complexity of Layout Parameters in Tournaments and Semicomplete Digraphs
dc.typeJournalArticle
dspace.entity.typePublication