Imbalance parameterized by twin cover revisited

Show simple item record Misra, Neeldhara Mittal, Harshil 2020-05-21T10:45:25Z 2020-05-21T10:45:25Z 2020-05
dc.identifier.citation Misra, Neeldhara and Mittal, Harshil, "Imbalance parameterized by twin cover revisited", arXiv, Cornell University Library, DOI: arXiv:2005.03800, May. 2020. en_US
dc.description.abstract We study the problem of Imbalance parameterized by the twin cover of a graph. We show that Imbalance is XP parameterized by twin cover, and FPT when parameterized by the twin cover and the size of the largest clique outside the twin cover. In contrast, we introduce a notion of succinct representations of graphs in terms of their twin cover and demonstrate that Imbalance is NP-hard in the setting of succinct representations, even for graphs that have a twin cover of size one.
dc.description.statementofresponsibility by Neeldhara Misra and Harshil Mittal
dc.language.iso en_US en_US
dc.publisher Cornell University Library en_US
dc.title Imbalance parameterized by twin cover revisited en_US
dc.type Pre-Print en_US
dc.relation.journal arXiv

Files in this item

Files Size Format View

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record

Search Digital Repository


My Account