Imbalance parameterized by twin cover revisited

Show simple item record

dc.contributor.author Misra, Neeldhara
dc.contributor.author Mittal, Harshil
dc.date.accessioned 2020-05-21T10:45:25Z
dc.date.available 2020-05-21T10:45:25Z
dc.date.issued 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.identifier.uri http://arxiv.org/abs/2005.03800
dc.identifier.uri https://repository.iitgn.ac.in/handle/123456789/5416
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


Browse

My Account