Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

Sitting closer to friends than enemies, revisited

Tools
- Tools
+ Tools

Cygan, Marek, Pilipczuk, Marcin, Pilipczuk, Michał and Wojtaszczyk, Jakub Onufry (2015) Sitting closer to friends than enemies, revisited. Theory of Computing Systems, 56 . pp. 394-405. doi:10.1007/s00224-014-9558-4 ISSN 1432-4350.

[img]
Preview
PDF (Creative Commons : Attribution 4.0)
WRAP_art%3A10.1007%2Fs00224-014-9558-4.pdf - Published Version - Requires a PDF viewer.

Download (684Kb) | Preview
Official URL: http://dx.doi.org/10.1007/s00224-014-9558-4

Request Changes to record.

Abstract

Signed graphs, i.e., undirected graphs with edges labelled with a plus or minus sign, are commonly used to model relationships in social networks. Recently, Kermarrec and Thraves (2011) initiated the study of the problem of appropriately visualising the network: They asked whether any signed graph can be embedded into the metric space TeX in such a manner that every vertex is closer to all its friends (neighbours via positive edges) than to all its enemies (neighbours via negative edges). Interestingly, embeddability into TeX can be expressed as a purely combinatorial problem. In this paper we pursue a deeper study of this case, answering several questions posed by Kermarrec and Thraves. First, we refine the approach of Kermarrec and Thraves for the case of complete signed graphs by showing that the problem is closely related to the recognition of proper interval graphs. Second, we prove that the general case, whose polynomial-time tractability remained open, is in fact NP-complete. Finally, we provide lower and upper bounds for the time complexity of the general case: we prove that the existence of a subexponential time (in the number of vertices and edges of the input signed graph) algorithm would violate the Exponential Time Hypothesis, whereas a simple dynamic programming approach gives a running time single-exponential in the number of vertices.

Item Type: Journal Article
Subjects: Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software
Divisions: Faculty of Science, Engineering and Medicine > Science > Computer Science
Library of Congress Subject Headings (LCSH): Graph theory, Online social networks
Journal or Publication Title: Theory of Computing Systems
Publisher: Springer
ISSN: 1432-4350
Official Date: February 2015
Dates:
DateEvent
February 2015Published
21 May 2014Accepted
26 September 2013Submitted
Volume: 56
Number of Pages: 12
Page Range: pp. 394-405
DOI: 10.1007/s00224-014-9558-4
Status: Peer Reviewed
Publication Status: Published
Access rights to Published version: Restricted or Subscription Access
Date of first compliant deposit: 28 December 2015
Date of first compliant Open Access: 28 December 2015
Funder: Seventh Framework Programme (European Commission) (FP7), European Research Council (ERC), Fundacja na rzecz Nauki Polskiej [Foundation for Polish Science] (FNP), Narodowe Centrum Nauki (NCN)
Grant number: 267959 (ERC), 279352 (ERC), N206567140 (NCN)

Request changes or add full text files to a record

Repository staff actions (login required)

View Item View Item

Downloads

Downloads per month over past year

View more statistics

twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us