Student Voices

Travel Report: Shenwei Huang, Computing, United Kingdom

December 19, 2014

I was honored to receive International Research Travel Award to work with Daniel Paulusma and Matthew Johnson, two professors at School of Engineering and Computing Sciences, Durham University in UK.

During my visit in May 2014, Daniel, Matthew and I continued a project on graph coloring that we already started early this year. A graph is a mathematic notion to model networks in which each object is called a vertex while a link, which we call an edge, may or may not exist between any pairs of objects. The graph coloring problem is to color vertices of a graph in such a way that any two vertices should not be colored alike whenever there is an edge between them. If we are only allowed to use a fixed number of colors, say k colors, then the problem is called k-coloring. In general, k-coloring is NP-complete, which roughly means that it is hard for a computer with the most powerful computational capacity to decide if a given graph can be colored using at most k colors. We studied this problem on ( , ) s t C P -free graphs, those that exclude a path t P and a cycle s C as induced subgraphs. We proved that k-coloring remains NPcomplete on ( , ) s t C P -free graphs for some values of s and t, and give a summary of complexity of k-coloring as well as two generalizations in terms of all combinations of s and t.

Moreover, Daniel and I, together with one of Daniel’s postdocs, Konrad Dabrowski, started a project on clique-width. Clique-width of a graph is the minimum number of labels needed to construct the graph under a set of specific rules. The typical problem one asks in this area is that if a given graph class has bounded or unbounded clique-width. Clique-width is closely related to the existence of efficient algorithms on graphs. The celebrated Courcelle’s Theorem states that any graph property that can be expressed in certain second order logic admits a linear time algorithm on any graph class of bounded clique-width. Therefore, it is vital to find graph classes of bounded clique-width. What we did was to investigate graphs that exclude two small graphs H1 and H2 as induced subgraphs. We refer to these graphs as (H1,H2)-free graphs. Continuing a line of Dabrowski and Paulusma, we found, via a new technique we developed, three more pairs (H1,H2) such that the class of (H1,H2)-free graphs have bounded clique-width.

The joint work we did leads to a couple of joint papers. The paper titled “Narrowing the Complexity Gap for Colouring ( , ) s t C P -Free Graphs” has appeared in the proceeding of AAIM 2014 while the paper “Bounding Clique-Width via Perfect Graphs” has been accepted by LATA 2015, which is to appear next March. Currently, Daniel, Konard and I are continuing the study of clique-width and we expect to obtain some further interesting results.

It was a wonderful experience to cooperate with scholars from other institutions. Not only does it help to advance our knowledge in a more efficient way, it also provides me the opportunity to learn from more experienced researchers in terms of how to ask questions. Sometimes it is more difficult to find a good problem than to solve one.

Print
No comments yet

Recent Blog Posts

  • Volunteer Posting: Innovate Now Conference October 23, 2017
    The Innovate Now Conference on October 30-31 at the Vancouver Convention Centre is looking for student volunteers to assist with registration.

  • External Award: Mitacs Accelerate Social Inclusion Grants October 23, 2017
    Mitacs and United Way have partenered to provide funding and training for graduate students and postdocs doing research related to social inclusion. Apply by January 8, 2018.

  • Planning for Sea Level Rise Seminar October 20, 2017
    John Englander, Oceanographer, Consultant, and Leading Expert on Sea Level Rise, will be visiting SFU Burnaby on November 8, 2017. This event is open to anyone in the SFU community.

View Posts by Category