liu.seSearch for publications in DiVA
Change search
ReferencesLink to record
Permanent link

Direct link
An Approximability-related Parameter on Graphs - Properties and Applications
Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, Faculty of Science & Engineering.
Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, Faculty of Science & Engineering.
University of Paris Est Marne La Vallee, France.
2015 (English)In: DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE, ISSN 1462-7264, Vol. 17, no 1, 33-66 p.Article in journal (Refereed) Published
Abstract [en]

We introduce a binary parameter on optimisation problems called separation. The parameter is used to relate the approximation ratios of different optimisation problems; in other words, we can convert approximability (and non-approximability) result for one problem into (non)-approximability results for other problems. Our main application is the problem (weighted) maximum H-colourable subgraph (MAX H-COL), which is a restriction of the general maximum constraint satisfaction problem (MAX CSP) to a single, binary, and symmetric relation. Using known approximation ratios for MAX k-CUT, we obtain general asymptotic approximability results for MAX H-COL for an arbitrary graph H. For several classes of graphs, we provide near-optimal results under the unique games conjecture. We also investigate separation as a graph parameter. In this vein, we study its properties on circular complete graphs. Furthermore, we establish a close connection to work by Samal on cubical colourings of graphs. This connection shows that our parameter is closely related to a special type of chromatic number. We believe that this insight may turn out to be crucial for understanding the behaviour of the parameter, and in the longer term, for understanding the approximability of optimisation problems such as MAX H-COL.

Place, publisher, year, edition, pages
DISCRETE MATHEMATICS THEORETICAL COMPUTER SCIENCE , 2015. Vol. 17, no 1, 33-66 p.
Keyword [en]
graph H-colouring; approximation; graph homomorphism; circular colouring; combinatorial optimisation; graph theory
National Category
Computer and Information Science
Identifiers
URN: urn:nbn:se:liu:diva-117670ISI: 000352198400003OAI: oai:DiVA.org:liu-117670DiVA: diva2:811332
Note

Funding Agencies|National Graduate School in Computer Science (CUGS), Sweden; Center for Industrial Information Technology (CENIIT) [04.01]; Swedish Research Council (VR) [2006-4532, 621-2009-4431]; European Communitys Seventh Framework Programme (FP7) [257039]; LIX-Qualcomm Postdoctoral Fellowship

Available from: 2015-05-11 Created: 2015-05-06 Last updated: 2015-05-25

Open Access in DiVA

No full text

Other links

link

Search in DiVA

By author/editor
Färnqvist, TommyJonsson, Peter
By organisation
Software and SystemsFaculty of Science & Engineering
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 40 hits
ReferencesLink to record
Permanent link

Direct link