MPI-INF Logo
Campus Event Calendar

Event Entry

What and Who

Graph Homomorphism for Bounded Cliquewidth

Magnus Wahlström
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (own work)
AG 1, AG 4, RG1, MMCI, AG 3, AG 5, SWS  
AG Audience
English

Date, Time and Location

Friday, 3 April 2009
13:00
30 Minutes
E1 4
024
Saarbrücken

Abstract

A graph homomorphism from G to H is a mapping from V(G) to V(H) that preserves edges (i.e. for an edge (u,v) in G, (f(u),f(v)) is an edge in H, but not necessarily vice versa). Deciding whether a graph homomorphism exists is a hard problem; the best upper bound we know still has a behaviour of n(H)^O(n(G)). "Plain-exponential" time bounds like c^n(G) or even c^(n(G)+n(H)) are known only for special cases, such as chromatic number (where H is K_k and the problem can be solved in time O(2^n(G))), or if H has bounded treewidth.


We show that the problem can be solved in plain-exponential time if H has cliquewidth at most k. Given a k-expression for H, we can count the number of graph homomorphisms in time O((2k+1)^n(G)), and to complete the result, we show that if H has cliquewidth at most k, then a k-expression for H can be found in time O((2k+1)^n(H)).

Since complete graphs have cliquewidth 2, and bounded treewidth implies bounded cliquewidth, this unifies and extends the previously known plain-exponential time cases.

Contact

Magnus Wahlström
--email hidden
passcode not visible
logged in users only

Magnus Wahlström, 03/27/2009 16:55
Magnus Wahlström, 03/27/2009 11:16 -- Created document.