Arrow Research search

Author name cluster

Sang-il Oum

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

4 papers
2 author rows

Possible papers

4

MFCS Conference 2020 Conference Paper

A Polynomial Kernel for 3-Leaf Power Deletion

  • Jungho Ahn
  • Eduard Eiben
  • O-joung Kwon
  • Sang-il Oum

For a non-negative integer 𝓁, a graph G is an 𝓁-leaf power of a tree T if V(G) is equal to the set of leaves of T, and distinct vertices v and w of G are adjacent if and only if the distance between v and w in T is at most 𝓁. Given a graph G, 3-Leaf Power Deletion asks whether there is a set S ⊆ V(G) of size at most k such that G\S is a 3-leaf power of some treeT. We provide a polynomial kernel for this problem. More specifically, we present a polynomial-time algorithm for an input instance (G, k) to output an equivalent instance (G', k') such that k'≤ k and G' has at most O(k^14) vertices.

Details

SODA Conference 2016 Conference Paper

Constructive algorithm for path-width of matroids

  • Jisu Jeong
  • Eun Jung Kim 0002
  • Sang-il Oum

Given n subspaces of a finite-dimensional vector space over a fixed finite field F, we wish to find a linear layout V 1, V 2, …, V n of the subspaces such that dim(( V 1 + V 2 + ⃛ + V i )∩( V i +1 + ⃛ + V n )) ≤ k for all i; such a linear layout is said to have width at most k. When restricted to 1-dimensional subspaces, this problem is equivalent to computing the path-width of an F -represented matroid in matroid theory and computing the trellis-width (or minimum trellis state-complexity) of a linear code in coding theory. We present a fixed-parameter tractable algorithm to construct a linear layout of width at most k, if it exists, for input subspaces of a finite-dimensional vector space over F. As corollaries, we obtain a fixed-parameter tractable algorithm to produce a path-decomposition of width at most k for an input F -represented matroid of path-width at most k, and a fixed-parameter tractable algorithm to find a linear rank-decomposition of width at most k for an input graph of linear rank-width at most k. In both corollaries, no such algorithms were known previously. Our approach is based on dynamic programming combined with the idea developed by Bodlaender and Kloks (1996) for their work on path-width and tree-width of graphs. It was previously known that a fixed-parameter tractable algorithm exists for the decision version of the problem for matroid path-width; a theorem by Geelen, Gerards, and Whittle (2002) implies that for each fixed finite field F, there are finitely many forbidden F -representable minors for the class of matroids of path-width at most k. An algorithm by Hliněný (2006) can detect a minor in an input F -represented matroid of bounded branch-width. However, this indirect approach would not produce an actual path-decomposition even if the complete list of forbidden minors were known. Our algorithm is the first one to construct such a path-decomposition and does not depend on the finiteness of forbidden minors.

Details