Loading Events

« All Events

  • This event has passed.
:

Jungho Ahn (안정호), Well-partitioned chordal graphs with the obstruction set and applications

Tuesday, April 27, 2021 @ 4:30 PM - 5:30 PM KST

Room B232, IBS (기초과학연구원)

Speaker

Jungho Ahn (안정호)
KAIST & IBS Discrete Mathematics Group
https://dimag.ibs.re.kr/home/jungho/

We introduce a new subclass of chordal graphs that generalizes split graphs, which we call well-partitioned chordal graphs. Split graphs are graphs that admit a partition of the vertex set into cliques that can be arranged in a star structure, the leaves of which are of size one. Well-partitioned chordal graphs are a generalization of this concept in the following two ways. First, the cliques in the partition can be arranged in a tree structure, and second, each clique is of arbitrary size. We mainly provide a characterization of well-partitioned chordal graphs by forbidden induced subgraphs and give a polynomial-time algorithm that given any graph, either finds an obstruction or outputs a partition of its vertex set that asserts that the graph is well-partitioned chordal. We demonstrate the algorithmic use of this graph class by showing that two variants of the problem of finding pairwise disjoint paths between k given pairs of vertices are in FPT, parameterized by k, on well-partitioned chordal graphs, while on chordal graphs, these problems are only known to be in XP. From the other end, we introduce some problems that are polynomial-time solvable on split graphs but become NP-complete on well-partitioned chordal graphs.

This is joint work with Lars Jaffke, O-joung Kwon, and Paloma T. Lima.

Details

Date:
Tuesday, April 27, 2021
Time:
4:30 PM - 5:30 PM KST
Event Category:
Event Tags:
,

Venue

Room B232
IBS (기초과학연구원)

Organizer

Sang-il Oum (엄상일)
View Organizer Website
IBS 이산수학그룹 Discrete Mathematics Group
기초과학연구원 수리및계산과학연구단 이산수학그룹
대전 유성구 엑스포로 55 (우) 34126
IBS Discrete Mathematics Group (DIMAG)
Institute for Basic Science (IBS)
55 Expo-ro Yuseong-gu Daejeon 34126 South Korea
E-mail: dimag@ibs.re.kr, Fax: +82-42-878-9209
Copyright © IBS 2018. All rights reserved.