Arash Rafiey (SFU)
11/10/13 12:30 Talks
List H-coloring (time and space complexity)
Speaker:
Arash Rafiey (Simon Fraser University, Computing Science)
Abstract:
The Dichotomy Conjecture for constraint satisfaction problems (CSPs) states that every CSP is in P or is NP-complete (Feder-Vardi, 1993) (equivalent to homomorphism problem to digraphs). We will talk about the time complexity and the space complexity of conservative binary CSP (also known as list homomorphism problem to digraphs). For digraph H, let LHOM(H) denote the list homomorphism problem to H.
We briefly talk about the time complexity of LHOM(H) and mention that for every digraph H, LHOM(H) is either polynomial or NP-complete. Moreover, there is an obstruction characterization of digraphs H that make LHOM(H) easy.
Considering space complexity, we show that LHOM(H) is solvable in logspace or is hard for NL. This is done by introducing a digraph structure called circular N. If H does not contain a circular N then LHOM(H) is solvable in logspace, and otherwise LHOM(H) is NL-hard. The solution is based on reducing the lists using a decomposition of an auxiliary digraph and repeatedly applying Reingold's algorithm for undirected reachability (2005). Moreover, the presence of a circular N can be decided in time polynomial in the size of H.
Based on joint works with Pavol Hell, Lazlo Egri, and Beniot Larose.
Date:
Friday, October 11, 2013
Time:
12:30 pm - 1:30 pm
Location:
TASC1 Building, Room No. 9204, Simon Fraser University, Burnaby
Arash Rafiey (Simon Fraser University, Computing Science)
Abstract:
The Dichotomy Conjecture for constraint satisfaction problems (CSPs) states that every CSP is in P or is NP-complete (Feder-Vardi, 1993) (equivalent to homomorphism problem to digraphs). We will talk about the time complexity and the space complexity of conservative binary CSP (also known as list homomorphism problem to digraphs). For digraph H, let LHOM(H) denote the list homomorphism problem to H.
We briefly talk about the time complexity of LHOM(H) and mention that for every digraph H, LHOM(H) is either polynomial or NP-complete. Moreover, there is an obstruction characterization of digraphs H that make LHOM(H) easy.
Considering space complexity, we show that LHOM(H) is solvable in logspace or is hard for NL. This is done by introducing a digraph structure called circular N. If H does not contain a circular N then LHOM(H) is solvable in logspace, and otherwise LHOM(H) is NL-hard. The solution is based on reducing the lists using a decomposition of an auxiliary digraph and repeatedly applying Reingold's algorithm for undirected reachability (2005). Moreover, the presence of a circular N can be decided in time polynomial in the size of H.
Based on joint works with Pavol Hell, Lazlo Egri, and Beniot Larose.
Date:
Friday, October 11, 2013
Time:
12:30 pm - 1:30 pm
Location:
TASC1 Building, Room No. 9204, Simon Fraser University, Burnaby