Search Results

Documents authored by Kim, Eun Jung

Found 2 Possible Name Variants:

Kim, Eun Jung

Document
DOI: 10.4230/LIPIcs.IPEC.2023.21
Bandwidth Parameterized by Cluster Vertex Deletion Number

Authors: Tatsuya Gima, Eun Jung Kim, Noleen Köhler, Nikolaos Melissinos, and Manolis Vasilakis

Published in: LIPIcs, Volume 285, 18th International Symposium on Parameterized and Exact Computation (IPEC 2023)

Abstract
Given a graph G and an integer b, Bandwidth asks whether there exists a bijection π from V(G) to {1, …, |V(G)|} such that max_{{u, v} ∈ E(G)} | π(u) - π(v) | ≤ b. This is a classical NP-complete problem, known to remain NP-complete even on very restricted classes of graphs, such as trees of maximum degree 3 and caterpillars of hair length 3. In the realm of parameterized complexity, these results imply that the problem remains NP-hard on graphs of bounded pathwidth, while it is additionally known to be W[1]-hard when parameterized by the treedepth of the input graph. In contrast, the problem does become FPT when parameterized by the vertex cover number of the input graph. In this paper, we make progress towards the parameterized (in)tractability of Bandwidth. We first show that it is FPT when parameterized by the cluster vertex deletion number cvd plus the clique number ω of the input graph, thus generalizing the previously mentioned result for vertex cover. On the other hand, we show that Bandwidth is W[1]-hard when parameterized only by cvd. Our results generalize some of the previous results and narrow some of the complexity gaps.
Cite as

Tatsuya Gima, Eun Jung Kim, Noleen Köhler, Nikolaos Melissinos, and Manolis Vasilakis. Bandwidth Parameterized by Cluster Vertex Deletion Number. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 21:1-21:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{gima_et_al:LIPIcs.IPEC.2023.21,
  author =	{Gima, Tatsuya and Kim, Eun Jung and K\"{o}hler, Noleen and Melissinos, Nikolaos and Vasilakis, Manolis},
  title =	{{Bandwidth Parameterized by Cluster Vertex Deletion Number}},
  booktitle =	{18th International Symposium on Parameterized and Exact Computation (IPEC 2023)},
  pages =	{21:1--21:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-305-8},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{285},
  editor =	{Misra, Neeldhara and Wahlstr\"{o}m, Magnus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.21},
  URN =		{urn:nbn:de:0030-drops-194401},
  doi =		{10.4230/LIPIcs.IPEC.2023.21},
  annote =	{Keywords: Bandwidth, Clique number, Cluster vertex deletion number, Parameterized complexity}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2022.9
Twin-Width VIII: Delineation and Win-Wins

Authors: Édouard Bonnet, Dibyayan Chakraborty, Eun Jung Kim, Noleen Köhler, Raul Lopes, and Stéphan Thomassé

Published in: LIPIcs, Volume 249, 17th International Symposium on Parameterized and Exact Computation (IPEC 2022)

Abstract
We introduce the notion of delineation. A graph class C is said delineated by twin-width (or simply, delineated) if for every hereditary closure D of a subclass of C, it holds that D has bounded twin-width if and only if D is monadically dependent. An effective strengthening of delineation for a class C implies that tractable FO model checking on C is perfectly understood: On hereditary closures of subclasses D of C, FO model checking on D is fixed-parameter tractable (FPT) exactly when D has bounded twin-width. Ordered graphs [BGOdMSTT, STOC '22] and permutation graphs [BKTW, JACM '22] are effectively delineated, while subcubic graphs are not. On the one hand, we prove that interval graphs, and even, rooted directed path graphs are delineated. On the other hand, we observe or show that segment graphs, directed path graphs (with arbitrarily many roots), and visibility graphs of simple polygons are not delineated. In an effort to draw the delineation frontier between interval graphs (that are delineated) and axis-parallel two-lengthed segment graphs (that are not), we investigate the twin-width of restricted segment intersection classes. It was known that (triangle-free) pure axis-parallel unit segment graphs have unbounded twin-width [BGKTW, SODA '21]. We show that K_{t,t}-free segment graphs, and axis-parallel H_t-free unit segment graphs have bounded twin-width, where H_t is the half-graph or ladder of height t. In contrast, axis-parallel H₄-free two-lengthed segment graphs have unbounded twin-width. We leave as an open question whether unit segment graphs are delineated. More broadly, we explore which structures (large bicliques, half-graphs, or independent sets) are responsible for making the twin-width large on the main classes of intersection and visibility graphs. Our new results, combined with the FPT algorithm for first-order model checking on graphs given with O(1)-sequences [BKTW, JACM '22], give rise to a variety of algorithmic win-win arguments. They all fall in the same framework: If p is an FO definable graph parameter that effectively functionally upperbounds twin-width on a class C, then p(G) ⩾ k can be decided in FPT time f(k) ⋅ |V(G)|^O(1). For instance, we readily derive FPT algorithms for k-Ladder on visibility graphs of 1.5D terrains, and k-Independent Set on visibility graphs of simple polygons. This showcases that the theory of twin-width can serve outside of classes of bounded twin-width.
Cite as

Édouard Bonnet, Dibyayan Chakraborty, Eun Jung Kim, Noleen Köhler, Raul Lopes, and Stéphan Thomassé. Twin-Width VIII: Delineation and Win-Wins. In 17th International Symposium on Parameterized and Exact Computation (IPEC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 249, pp. 9:1-9:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bonnet_et_al:LIPIcs.IPEC.2022.9,
  author =	{Bonnet, \'{E}douard and Chakraborty, Dibyayan and Kim, Eun Jung and K\"{o}hler, Noleen and Lopes, Raul and Thomass\'{e}, St\'{e}phan},
  title =	{{Twin-Width VIII: Delineation and Win-Wins}},
  booktitle =	{17th International Symposium on Parameterized and Exact Computation (IPEC 2022)},
  pages =	{9:1--9:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-260-0},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{249},
  editor =	{Dell, Holger and Nederlof, Jesper},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2022.9},
  URN =		{urn:nbn:de:0030-drops-173650},
  doi =		{10.4230/LIPIcs.IPEC.2022.9},
  annote =	{Keywords: Twin-width, intersection graphs, visibility graphs, monadic dependence and stability, first-order model checking}
}
Document
DOI: 10.4230/LIPIcs.STACS.2022.40
Obstructions for Matroids of Path-Width at most k and Graphs of Linear Rank-Width at most k

Authors: Mamadou Moustapha Kanté, Eun Jung Kim, O-joung Kwon, and Sang-il Oum

Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)

Abstract
Every minor-closed class of matroids of bounded branch-width can be characterized by a minimal list of excluded minors, but unlike graphs, this list could be infinite in general. However, for each fixed finite field F, the list contains only finitely many F-representable matroids, due to the well-quasi-ordering of F-representable matroids of bounded branch-width under taking matroid minors [J. F. Geelen, A. M. H. Gerards, and G. Whittle (2002)]. But this proof is non-constructive and does not provide any algorithm for computing these F-representable excluded minors in general. We consider the class of matroids of path-width at most k for fixed k. We prove that for a finite field F, every F-representable excluded minor for the class of matroids of path-width at most k has at most 2^{|𝔽|^{O(k²)}} elements. We can therefore compute, for any integer k and a fixed finite field F, the set of F-representable excluded minors for the class of matroids of path-width k, and this gives as a corollary a polynomial-time algorithm for checking whether the path-width of an F-represented matroid is at most k. We also prove that every excluded pivot-minor for the class of graphs having linear rank-width at most k has at most 2^{2^{O(k²)}} vertices, which also results in a similar algorithmic consequence for linear rank-width of graphs.
Cite as

Mamadou Moustapha Kanté, Eun Jung Kim, O-joung Kwon, and Sang-il Oum. Obstructions for Matroids of Path-Width at most k and Graphs of Linear Rank-Width at most k. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 40:1-40:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{kante_et_al:LIPIcs.STACS.2022.40,
  author =	{Kant\'{e}, Mamadou Moustapha and Kim, Eun Jung and Kwon, O-joung and Oum, Sang-il},
  title =	{{Obstructions for Matroids of Path-Width at most k and Graphs of Linear Rank-Width at most k}},
  booktitle =	{39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)},
  pages =	{40:1--40:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-222-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{219},
  editor =	{Berenbrink, Petra and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.40},
  URN =		{urn:nbn:de:0030-drops-158507},
  doi =		{10.4230/LIPIcs.STACS.2022.40},
  annote =	{Keywords: path-width, matroid, linear rank-width, graph, forbidden minor, vertex-minor, pivot-minor}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2021.10
Twin-Width and Polynomial Kernels

Authors: Édouard Bonnet, Eun Jung Kim, Amadeus Reinald, Stéphan Thomassé, and Rémi Watrigant

Published in: LIPIcs, Volume 214, 16th International Symposium on Parameterized and Exact Computation (IPEC 2021)

Abstract
We study the existence of polynomial kernels for parameterized problems without a polynomial kernel on general graphs, when restricted to graphs of bounded twin-width. It was previously observed in [Bonnet et al., ICALP'21] that the problem k-Independent Set allows no polynomial kernel on graph of bounded twin-width by a very simple argument, which extends to several other problems such as k-Independent Dominating Set, k-Path, k-Induced Path, k-Induced Matching. In this work, we examine the k-Dominating Set and variants of k-Vertex Cover for the existence of polynomial kernels. As a main result, we show that k-Dominating Set does not admit a polynomial kernel on graphs of twin-width at most 4 under a standard complexity-theoretic assumption. The reduction is intricate, especially due to the effort to bring the twin-width down to 4, and it can be tweaked to work for Connected k-Dominating Set and Total k-Dominating Set with a slightly worse bound on the twin-width. On the positive side, we obtain a simple quadratic vertex kernel for Connected k-Vertex Cover and Capacitated k-Vertex Cover on graphs of bounded twin-width. These kernels rely on that graphs of bounded twin-width have Vapnik-Chervonenkis (VC) density 1, that is, for any vertex set X, the number of distinct neighborhoods in X is at most c⋅|X|, where c is a constant depending only on the twin-width. Interestingly the kernel applies to any graph class of VC density 1, and does not require a witness sequence. We also present a more intricate O(k^{1.5}) vertex kernel for Connected k-Vertex Cover. Finally we show that deciding if a graph has twin-width at most 1 can be done in polynomial time, and observe that most graph optimization/decision problems can be solved in polynomial time on graphs of twin-width at most 1.
Cite as

Édouard Bonnet, Eun Jung Kim, Amadeus Reinald, Stéphan Thomassé, and Rémi Watrigant. Twin-Width and Polynomial Kernels. In 16th International Symposium on Parameterized and Exact Computation (IPEC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 214, pp. 10:1-10:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{bonnet_et_al:LIPIcs.IPEC.2021.10,
  author =	{Bonnet, \'{E}douard and Kim, Eun Jung and Reinald, Amadeus and Thomass\'{e}, St\'{e}phan and Watrigant, R\'{e}mi},
  title =	{{Twin-Width and Polynomial Kernels}},
  booktitle =	{16th International Symposium on Parameterized and Exact Computation (IPEC 2021)},
  pages =	{10:1--10:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-216-7},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{214},
  editor =	{Golovach, Petr A. and Zehavi, Meirav},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2021.10},
  URN =		{urn:nbn:de:0030-drops-153932},
  doi =		{10.4230/LIPIcs.IPEC.2021.10},
  annote =	{Keywords: Twin-width, kernelization, lower bounds, Dominating Set}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2021.7
A Constant-Factor Approximation for Weighted Bond Cover

Authors: Eun Jung Kim, Euiwoong Lee, and Dimitrios M. Thilikos

Published in: LIPIcs, Volume 207, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)

Abstract
The Weighted ℱ-Vertex Deletion for a class ℱ of graphs asks, weighted graph G, for a minimum weight vertex set S such that G-S ∈ ℱ. The case when ℱ is minor-closed and excludes some graph as a minor has received particular attention but a constant-factor approximation remained elusive for Weighted ℱ-Vertex Deletion. Only three cases of minor-closed ℱ are known to admit constant-factor approximations, namely Vertex Cover, Feedback Vertex Set and Diamond Hitting Set. We study the problem for the class ℱ of θ_c-minor-free graphs, under the equivalent setting of the Weighted c-Bond Cover problem, and present a constant-factor approximation algorithm using the primal-dual method. For this, we leverage a structure theorem implicit in [Joret et al., SIDMA'14] which states the following: any graph G containing a θ_c-minor-model either contains a large two-terminal protrusion, or contains a constant-size θ_c-minor-model, or a collection of pairwise disjoint constant-sized connected sets that can be contracted simultaneously to yield a dense graph. In the first case, we tame the graph by replacing the protrusion with a special-purpose weighted gadget. For the second and third case, we provide a weighting scheme which guarantees a local approximation ratio. Besides making an important step in the quest of (dis)proving a constant-factor approximation for Weighted ℱ-Vertex Deletion, our result may be useful as a template for algorithms for other minor-closed families.
Cite as

Eun Jung Kim, Euiwoong Lee, and Dimitrios M. Thilikos. A Constant-Factor Approximation for Weighted Bond Cover. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 7:1-7:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{kim_et_al:LIPIcs.APPROX/RANDOM.2021.7,
  author =	{Kim, Eun Jung and Lee, Euiwoong and Thilikos, Dimitrios M.},
  title =	{{A Constant-Factor Approximation for Weighted Bond Cover}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)},
  pages =	{7:1--7:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-207-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{207},
  editor =	{Wootters, Mary and Sanit\`{a}, Laura},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2021.7},
  URN =		{urn:nbn:de:0030-drops-147002},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2021.7},
  annote =	{Keywords: Constant-factor approximation algorithms, Primal-dual method, Bonds in graphs, Graph minors, Graph modification problems}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2021.35
Twin-width III: Max Independent Set, Min Dominating Set, and Coloring

Authors: Édouard Bonnet, Colin Geniet, Eun Jung Kim, Stéphan Thomassé, and Rémi Watrigant

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

Abstract
We recently introduced the notion of twin-width, a novel graph invariant, and showed that first-order model checking can be solved in time f(d,k)n for n-vertex graphs given with a witness that the twin-width is at most d, called d-contraction sequence or d-sequence, and formulas of size k [Bonnet et al., FOCS '20]. The inevitable price to pay for such a general result is that f is a tower of exponentials of height roughly k. In this paper, we show that algorithms based on twin-width need not be impractical. We present 2^{O(k)}n-time algorithms for k-Independent Set, r-Scattered Set, k-Clique, and k-Dominating Set when an O(1)-sequence of the graph is given in input. We further show how to solve the weighted version of k-Independent Set, Subgraph Isomorphism, and Induced Subgraph Isomorphism, in the slightly worse running time 2^{O(k log k)}n. Up to logarithmic factors in the exponent, all these running times are optimal, unless the Exponential Time Hypothesis fails. Like our FO model checking algorithm, these new algorithms are based on a dynamic programming scheme following the sequence of contractions forward. We then show a second algorithmic use of the contraction sequence, by starting at its end and rewinding it. As an example of such a reverse scheme, we present a polynomial-time algorithm that properly colors the vertices of a graph with relatively few colors, thereby establishing that bounded twin-width classes are χ-bounded. This significantly extends the χ-boundedness of bounded rank-width classes, and does so with a very concise proof. It readily yields a constant approximation for Max Independent Set on K_t-free graphs of bounded twin-width, and a 2^{O(OPT)}-approximation for Min Coloring on bounded twin-width graphs. We further observe that a constant approximation for Max Independent Set on bounded twin-width graphs (but arbitrarily large clique number) would actually imply a PTAS. The third algorithmic use of twin-width builds on the second one. Playing the contraction sequence backward, we show that bounded twin-width graphs can be edge-partitioned into a linear number of bicliques, such that both sides of the bicliques are on consecutive vertices, in a fixed vertex ordering. This property is trivially shared with graphs of bounded average degree. Given that biclique edge-partition, we show how to solve the unweighted Single-Source Shortest Paths and hence All-Pairs Shortest Paths in time O(n log n) and time O(n² log n), respectively. In sharp contrast, even Diameter does not admit a truly subquadratic algorithm on bounded twin-width graphs, unless the Strong Exponential Time Hypothesis fails. The fourth algorithmic use of twin-width builds on the so-called versatile tree of contractions [Bonnet et al., SODA '21], a branching and more robust witness of low twin-width. We present constant-approximation algorithms for Min Dominating Set and related problems, on bounded twin-width graphs, by showing that the integrality gap is constant. This is done by going down the versatile tree and stopping accordingly to a problem-dependent criterion. At the reached node, a greedy approach yields the desired approximation.
Cite as

Édouard Bonnet, Colin Geniet, Eun Jung Kim, Stéphan Thomassé, and Rémi Watrigant. Twin-width III: Max Independent Set, Min Dominating Set, and Coloring. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 35:1-35:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{bonnet_et_al:LIPIcs.ICALP.2021.35,
  author =	{Bonnet, \'{E}douard and Geniet, Colin and Kim, Eun Jung and Thomass\'{e}, St\'{e}phan and Watrigant, R\'{e}mi},
  title =	{{Twin-width III: Max Independent Set, Min Dominating Set, and Coloring}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{35:1--35:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.35},
  URN =		{urn:nbn:de:0030-drops-141044},
  doi =		{10.4230/LIPIcs.ICALP.2021.35},
  annote =	{Keywords: Twin-width, Max Independent Set, Min Dominating Set, Coloring, Parameterized Algorithms, Approximation Algorithms, Exact Algorithms}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2020.62
Towards Constant-Factor Approximation for Chordal / Distance-Hereditary Vertex Deletion

Authors: Jungho Ahn, Eun Jung Kim, and Euiwoong Lee

Published in: LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)

Abstract
For a family of graphs ℱ, Weighted ℱ-Deletion is the problem for which the input is a vertex weighted graph G = (V, E) and the goal is to delete S ⊆ V with minimum weight such that G⧵S ∈ ℱ. Designing a constant-factor approximation algorithm for large subclasses of perfect graphs has been an interesting research direction. Block graphs, 3-leaf power graphs, and interval graphs are known to admit constant-factor approximation algorithms, but the question is open for chordal graphs and distance-hereditary graphs. In this paper, we add one more class to this list by presenting a constant-factor approximation algorithm when ℱ is the intersection of chordal graphs and distance-hereditary graphs. They are known as ptolemaic graphs and form a superset of both block graphs and 3-leaf power graphs above. Our proof presents new properties and algorithmic results on inter-clique digraphs as well as an approximation algorithm for a variant of Feedback Vertex Set that exploits this relationship (named Feedback Vertex Set with Precedence Constraints), each of which may be of independent interest.
Cite as

Jungho Ahn, Eun Jung Kim, and Euiwoong Lee. Towards Constant-Factor Approximation for Chordal / Distance-Hereditary Vertex Deletion. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 62:1-62:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{ahn_et_al:LIPIcs.ISAAC.2020.62,
  author =	{Ahn, Jungho and Kim, Eun Jung and Lee, Euiwoong},
  title =	{{Towards Constant-Factor Approximation for Chordal / Distance-Hereditary Vertex Deletion}},
  booktitle =	{31st International Symposium on Algorithms and Computation (ISAAC 2020)},
  pages =	{62:1--62:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-173-3},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{181},
  editor =	{Cao, Yixin and Cheng, Siu-Wing and Li, Minming},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.62},
  URN =		{urn:nbn:de:0030-drops-134063},
  doi =		{10.4230/LIPIcs.ISAAC.2020.62},
  annote =	{Keywords: ptolemaic, approximation algorithm, linear programming, feedback vertex set}
}
Document
DOI: 10.4230/LIPIcs.ESA.2020.14
Grundy Distinguishes Treewidth from Pathwidth

Authors: Rémy Belmonte, Eun Jung Kim, Michael Lampis, Valia Mitsou, and Yota Otachi

Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)

Abstract
Structural graph parameters, such as treewidth, pathwidth, and clique-width, are a central topic of study in parameterized complexity. A main aim of research in this area is to understand the "price of generality" of these widths: as we transition from more restrictive to more general notions, which are the problems that see their complexity status deteriorate from fixed-parameter tractable to intractable? This type of question is by now very well-studied, but, somewhat strikingly, the algorithmic frontier between the two (arguably) most central width notions, treewidth and pathwidth, is still not understood: currently, no natural graph problem is known to be W-hard for one but FPT for the other. Indeed, a surprising development of the last few years has been the observation that for many of the most paradigmatic problems, their complexities for the two parameters actually coincide exactly, despite the fact that treewidth is a much more general parameter. It would thus appear that the extra generality of treewidth over pathwidth often comes "for free". Our main contribution in this paper is to uncover the first natural example where this generality comes with a high price. We consider Grundy Coloring, a variation of coloring where one seeks to calculate the worst possible coloring that could be assigned to a graph by a greedy First-Fit algorithm. We show that this well-studied problem is FPT parameterized by pathwidth; however, it becomes significantly harder (W[1]-hard) when parameterized by treewidth. Furthermore, we show that Grundy Coloring makes a second complexity jump for more general widths, as it becomes para-NP-hard for clique-width. Hence, Grundy Coloring nicely captures the complexity trade-offs between the three most well-studied parameters. Completing the picture, we show that Grundy Coloring is FPT parameterized by modular-width.
Cite as

Rémy Belmonte, Eun Jung Kim, Michael Lampis, Valia Mitsou, and Yota Otachi. Grundy Distinguishes Treewidth from Pathwidth. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 14:1-14:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{belmonte_et_al:LIPIcs.ESA.2020.14,
  author =	{Belmonte, R\'{e}my and Kim, Eun Jung and Lampis, Michael and Mitsou, Valia and Otachi, Yota},
  title =	{{Grundy Distinguishes Treewidth from Pathwidth}},
  booktitle =	{28th Annual European Symposium on Algorithms (ESA 2020)},
  pages =	{14:1--14:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-162-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{173},
  editor =	{Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.14},
  URN =		{urn:nbn:de:0030-drops-128803},
  doi =		{10.4230/LIPIcs.ESA.2020.14},
  annote =	{Keywords: Treewidth, Pathwidth, Clique-width, Grundy Coloring}
}
Document
DOI: 10.4230/LIPIcs.STACS.2020.58
Grundy Coloring & Friends, Half-Graphs, Bicliques

Authors: Pierre Aboulker, Édouard Bonnet, Eun Jung Kim, and Florian Sikora

Published in: LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)

Abstract
The first-fit coloring is a heuristic that assigns to each vertex, arriving in a specified order σ, the smallest available color. The problem Grundy Coloring asks how many colors are needed for the most adversarial vertex ordering σ, i.e., the maximum number of colors that the first-fit coloring requires over all possible vertex orderings. Since its inception by Grundy in 1939, Grundy Coloring has been examined for its structural and algorithmic aspects. A brute-force f(k)n^{2^{k-1}}-time algorithm for Grundy Coloring on general graphs is not difficult to obtain, where k is the number of colors required by the most adversarial vertex ordering. It was asked several times whether the dependency on k in the exponent of n can be avoided or reduced, and its answer seemed elusive until now. We prove that Grundy Coloring is W[1]-hard and the brute-force algorithm is essentially optimal under the Exponential Time Hypothesis, thus settling this question by the negative. The key ingredient in our W[1]-hardness proof is to use so-called half-graphs as a building block to transmit a color from one vertex to another. Leveraging the half-graphs, we also prove that b-Chromatic Core is W[1]-hard, whose parameterized complexity was posed as an open question by Panolan et al. [JCSS '17]. A natural follow-up question is, how the parameterized complexity changes in the absence of (large) half-graphs. We establish fixed-parameter tractability on K_{t,t}-free graphs for b-Chromatic Core and Partial Grundy Coloring, making a step toward answering this question. The key combinatorial lemma underlying the tractability result might be of independent interest.
Cite as

Pierre Aboulker, Édouard Bonnet, Eun Jung Kim, and Florian Sikora. Grundy Coloring & Friends, Half-Graphs, Bicliques. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 58:1-58:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{aboulker_et_al:LIPIcs.STACS.2020.58,
  author =	{Aboulker, Pierre and Bonnet, \'{E}douard and Kim, Eun Jung and Sikora, Florian},
  title =	{{Grundy Coloring \& Friends, Half-Graphs, Bicliques}},
  booktitle =	{37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)},
  pages =	{58:1--58:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-140-5},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{154},
  editor =	{Paul, Christophe and Bl\"{a}ser, Markus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.58},
  URN =		{urn:nbn:de:0030-drops-119190},
  doi =		{10.4230/LIPIcs.STACS.2020.58},
  annote =	{Keywords: Grundy coloring, parameterized complexity, ETH lower bounds, K\underline\{t,t\}-free graphs, half-graphs}
}
Document
DOI: 10.4230/LIPIcs.STACS.2019.13
Token Sliding on Split Graphs

Authors: Rémy Belmonte, Eun Jung Kim, Michael Lampis, Valia Mitsou, Yota Otachi, and Florian Sikora

Published in: LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)

Abstract
We consider the complexity of the Independent Set Reconfiguration problem under the Token Sliding rule. In this problem we are given two independent sets of a graph and are asked if we can transform one to the other by repeatedly exchanging a vertex that is currently in the set with one of its neighbors, while maintaining the set independent. Our main result is to show that this problem is PSPACE-complete on split graphs (and hence also on chordal graphs), thus resolving an open problem in this area. We then go on to consider the c-Colorable Reconfiguration problem under the same rule, where the constraint is now to maintain the set c-colorable at all times. As one may expect, a simple modification of our reduction shows that this more general problem is PSPACE-complete for all fixed c >= 1 on chordal graphs. Somewhat surprisingly, we show that the same cannot be said for split graphs: we give a polynomial time (n^{O(c)}) algorithm for all fixed values of c, except c=1, for which the problem is PSPACE-complete. We complement our algorithm with a lower bound showing that c-Colorable Reconfiguration is W[2]-hard on split graphs parameterized by c and the length of the solution, as well as a tight ETH-based lower bound for both parameters.
Cite as

Rémy Belmonte, Eun Jung Kim, Michael Lampis, Valia Mitsou, Yota Otachi, and Florian Sikora. Token Sliding on Split Graphs. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 13:1-13:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{belmonte_et_al:LIPIcs.STACS.2019.13,
  author =	{Belmonte, R\'{e}my and Kim, Eun Jung and Lampis, Michael and Mitsou, Valia and Otachi, Yota and Sikora, Florian},
  title =	{{Token Sliding on Split Graphs}},
  booktitle =	{36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)},
  pages =	{13:1--13:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-100-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{126},
  editor =	{Niedermeier, Rolf and Paul, Christophe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.13},
  URN =		{urn:nbn:de:0030-drops-102529},
  doi =		{10.4230/LIPIcs.STACS.2019.13},
  annote =	{Keywords: reconfiguration, independent set, split graph}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2018.20
Data-Compression for Parametrized Counting Problems on Sparse Graphs

Authors: Eun Jung Kim, Maria Serna, and Dimitrios M. Thilikos

Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)

Abstract
We study the concept of compactor, which may be seen as a counting-analogue of kernelization in counting parameterized complexity. For a function F:Sigma^* -> N and a parameterization kappa: Sigma^* -> N, a compactor (P,M) consists of a polynomial-time computable function P, called condenser, and a computable function M, called extractor, such that F=M o P, and the condensing P(x) of x has length at most s(kappa(x)), for any input x in Sigma^*. If s is a polynomial function, then the compactor is said to be of polynomial-size. Although the study on counting-analogue of kernelization is not unprecedented, it has received little attention so far. We study a family of vertex-certified counting problems on graphs that are MSOL-expressible; that is, for an MSOL-formula phi with one free set variable to be interpreted as a vertex subset, we want to count all A subseteq V(G) where |A|=k and (G,A) models phi. In this paper, we prove that every vertex-certified counting problems on graphs that is MSOL-expressible and treewidth modulable, when parameterized by k, admits a polynomial-size compactor on H-topological-minor-free graphs with condensing time O(k^2n^2) and decoding time 2^{O(k)}. This implies the existence of an FPT-algorithm of running time O(n^2 k^2)+2^{O(k)}. All aforementioned complexities are under the Uniform Cost Measure (UCM) model where numbers can be stored in constant space and arithmetic operations can be done in constant time.
Cite as

Eun Jung Kim, Maria Serna, and Dimitrios M. Thilikos. Data-Compression for Parametrized Counting Problems on Sparse Graphs. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 20:1-20:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{kim_et_al:LIPIcs.ISAAC.2018.20,
  author =	{Kim, Eun Jung and Serna, Maria and Thilikos, Dimitrios M.},
  title =	{{Data-Compression for Parametrized Counting Problems on Sparse Graphs}},
  booktitle =	{29th International Symposium on Algorithms and Computation (ISAAC 2018)},
  pages =	{20:1--20:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.20},
  URN =		{urn:nbn:de:0030-drops-99688},
  doi =		{10.4230/LIPIcs.ISAAC.2018.20},
  annote =	{Keywords: Parameterized counting, compactor, protrusion decomposition}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2018.67
New Results on Directed Edge Dominating Set

Authors: Rémy Belmonte, Tesshu Hanaka, Ioannis Katsikarelis, Eun Jung Kim, and Michael Lampis

Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

Abstract
We study a family of generalizations of Edge Dominating Set on directed graphs called Directed (p,q)-Edge Dominating Set. In this problem an arc (u,v) is said to dominate itself, as well as all arcs which are at distance at most q from v, or at distance at most p to u. First, we give significantly improved FPT algorithms for the two most important cases of the problem, (0,1)-dEDS and (1,1)-dEDS (that correspond to versions of Dominating Set on line graphs), as well as polynomial kernels. We also improve the best-known approximation for these cases from logarithmic to constant. In addition, we show that (p,q)-dEDS is FPT parameterized by p+q+tw, but W-hard parameterized just by tw, where tw is the treewidth of the underlying graph of the input. We then go on to focus on the complexity of the problem on tournaments. Here, we provide a complete classification for every possible fixed value of p,q, which shows that the problem exhibits a surprising behavior, including cases which are in P; cases which are solvable in quasi-polynomial time but not in P; and a single case (p=q=1) which is NP-hard (under randomized reductions) and cannot be solved in sub-exponential time, under standard assumptions.
Cite as

Rémy Belmonte, Tesshu Hanaka, Ioannis Katsikarelis, Eun Jung Kim, and Michael Lampis. New Results on Directed Edge Dominating Set. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 67:1-67:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{belmonte_et_al:LIPIcs.MFCS.2018.67,
  author =	{Belmonte, R\'{e}my and Hanaka, Tesshu and Katsikarelis, Ioannis and Kim, Eun Jung and Lampis, Michael},
  title =	{{New Results on Directed Edge Dominating Set}},
  booktitle =	{43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
  pages =	{67:1--67:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Potapov, Igor and Spirakis, Paul and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.67},
  URN =		{urn:nbn:de:0030-drops-96490},
  doi =		{10.4230/LIPIcs.MFCS.2018.67},
  annote =	{Keywords: Edge Dominating Set, Tournaments, Treewidth}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2018.80
Finding Branch-Decompositions of Matroids, Hypergraphs, and More

Authors: Jisu Jeong, Eun Jung Kim, and Sang-il Oum

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract
Given n subspaces of a finite-dimensional vector space over a fixed finite field F, we wish to find a "branch-decomposition" of these subspaces of width at most k, that is a subcubic tree T with n leaves mapped bijectively to the subspaces such that for every edge e of T, the sum of subspaces associated to the leaves in one component of T-e and the sum of subspaces associated to the leaves in the other component have the intersection of dimension at most k. This problem includes the problems of computing branch-width of F-represented matroids, rank-width of graphs, branch-width of hypergraphs, and carving-width of graphs. We present a fixed-parameter algorithm to construct such a branch-decomposition of width at most k, if it exists, for input subspaces of a finite-dimensional vector space over F. Our algorithm is analogous to the algorithm of Bodlaender and Kloks (1996) on tree-width of graphs. To extend their framework to branch-decompositions of vector spaces, we developed highly generic tools for branch-decompositions on vector spaces. For this problem, a fixed-parameter algorithm was known due to Hlinený and Oum (2008). But their method is highly indirect. Their algorithm uses the non-trivial fact by Geelen et al. (2003) that the number of forbidden minors is finite and uses the algorithm of Hlinený (2006) on checking monadic second-order formulas on F-represented matroids of small branch-width. Our result does not depend on such a fact and is completely self-contained, and yet matches their asymptotic running time for each fixed k.
Cite as

Jisu Jeong, Eun Jung Kim, and Sang-il Oum. Finding Branch-Decompositions of Matroids, Hypergraphs, and More. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 80:1-80:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{jeong_et_al:LIPIcs.ICALP.2018.80,
  author =	{Jeong, Jisu and Kim, Eun Jung and Oum, Sang-il},
  title =	{{Finding Branch-Decompositions of Matroids, Hypergraphs, and More}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{80:1--80:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.80},
  URN =		{urn:nbn:de:0030-drops-90849},
  doi =		{10.4230/LIPIcs.ICALP.2018.80},
  annote =	{Keywords: branch-width, rank-width, carving-width, fixed-parameter tractability}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2018.12
QPTAS and Subexponential Algorithm for Maximum Clique on Disk Graphs

Authors: Édouard Bonnet, Panos Giannopoulos, Eun Jung Kim, Pawel Rzazewski, and Florian Sikora

Published in: LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018)

Abstract
A (unit) disk graph is the intersection graph of closed (unit) disks in the plane. Almost three decades ago, an elegant polynomial-time algorithm was found for Maximum Clique on unit disk graphs [Clark, Colbourn, Johnson; Discrete Mathematics '90]. Since then, it has been an intriguing open question whether or not tractability can be extended to general disk graphs. We show the rather surprising structural result that a disjoint union of cycles is the complement of a disk graph if and only if at most one of those cycles is of odd length. From that, we derive the first QPTAS and subexponential algorithm running in time 2^{O~(n^{2/3})} for Maximum Clique on disk graphs. In stark contrast, Maximum Clique on intersection graphs of filled ellipses or filled triangles is unlikely to have such algorithms, even when the ellipses are close to unit disks. Indeed, we show that there is a constant ratio of approximation which cannot be attained even in time 2^{n^{1-epsilon}}, unless the Exponential Time Hypothesis fails.
Cite as

Édouard Bonnet, Panos Giannopoulos, Eun Jung Kim, Pawel Rzazewski, and Florian Sikora. QPTAS and Subexponential Algorithm for Maximum Clique on Disk Graphs. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 12:1-12:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{bonnet_et_al:LIPIcs.SoCG.2018.12,
  author =	{Bonnet, \'{E}douard and Giannopoulos, Panos and Kim, Eun Jung and Rzazewski, Pawel and Sikora, Florian},
  title =	{{QPTAS and Subexponential Algorithm for Maximum Clique on Disk Graphs}},
  booktitle =	{34th International Symposium on Computational Geometry (SoCG 2018)},
  pages =	{12:1--12:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-066-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{99},
  editor =	{Speckmann, Bettina and T\'{o}th, Csaba D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.12},
  URN =		{urn:nbn:de:0030-drops-87259},
  doi =		{10.4230/LIPIcs.SoCG.2018.12},
  annote =	{Keywords: disk graph, maximum clique, computational complexity}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2015.78
Parameterized Algorithms for Min-Max Multiway Cut and List Digraph Homomorphism

Authors: Eun Jung Kim, Christophe Paul, Ignasi Sau, and Dimitrios M. Thilikos

Published in: LIPIcs, Volume 43, 10th International Symposium on Parameterized and Exact Computation (IPEC 2015)

Abstract
In this paper we design FPT-algorithms for two parameterized problems. The first is List Digraph Homomorphism: given two digraphs G and H and a list of allowed vertices of H for every vertex of G, the question is whether there exists a homomorphism from G to H respecting the list constraints. The second problem is a variant of Multiway Cut, namely Min-Max Multiway Cut: given a graph G, a non-negative integer l, and a set T of r terminals, the question is whether we can partition the vertices of G into r parts such that (a) each part contains one terminal and (b) there are at most l edges with only one endpoint in this part. We parameterize List Digraph Homomorphism by the number w of edges of G that are mapped to non-loop edges of H and we give a time 2^{O(l * log(h) + l^{2 * log(l)}} * n^{4} * log(n) algorithm, where h is the order of the host graph H.We also prove that Min-Max Multiway Cut can be solved in time 2^{O((l * r)^2 * log(l *r))} * n^{4} * log(n). Our approach introduces a general problem, called List Allocation, whose expressive power permits the design of parameterized reductions of both aforementioned problems to it. Then our results are based on an FPT-algorithm for the List Allocation problem that is designed using a suitable adaptation of the randomized contractions technique (introduced by [Chitnis, Cygan, Hajiaghayi, Pilipczuk, and Pilipczuk, FOCS 2012]).
Cite as

Eun Jung Kim, Christophe Paul, Ignasi Sau, and Dimitrios M. Thilikos. Parameterized Algorithms for Min-Max Multiway Cut and List Digraph Homomorphism. In 10th International Symposium on Parameterized and Exact Computation (IPEC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 43, pp. 78-89, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{kim_et_al:LIPIcs.IPEC.2015.78,
  author =	{Kim, Eun Jung and Paul, Christophe and Sau, Ignasi and Thilikos, Dimitrios M.},
  title =	{{Parameterized Algorithms for Min-Max Multiway Cut and List Digraph Homomorphism}},
  booktitle =	{10th International Symposium on Parameterized and Exact Computation (IPEC 2015)},
  pages =	{78--89},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-92-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{43},
  editor =	{Husfeldt, Thore and Kanj, Iyad},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2015.78},
  URN =		{urn:nbn:de:0030-drops-55738},
  doi =		{10.4230/LIPIcs.IPEC.2015.78},
  annote =	{Keywords: Parameterized complexity, Fixed-Parameter Tractable algorithm, Multiway Cut, Digraph homomorphism}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2015.138
An FPT Algorithm and a Polynomial Kernel for Linear Rankwidth-1 Vertex Deletion

Authors: Mamadou Moustapha Kanté, Eun Jung Kim, O-joung Kwon, and Christophe Paul

Published in: LIPIcs, Volume 43, 10th International Symposium on Parameterized and Exact Computation (IPEC 2015)

Abstract
Linear rankwidth is a linearized variant of rankwidth, introduced by Oum and Seymour [Approximating clique-width and branch-width. J. Combin. Theory Ser. B, 96(4):514-528, 2006.], and it is similar to pathwidth, which is the linearized variant of treewidth. Motivated from the results on graph modification problems into graphs of bounded treewidth or pathwidth, we investigate a graph modification problem into the class of graphs having linear rankwidth at most one, called the Linear Rankwidth-1 Vertex Deletion (shortly, LRW1-Vertex Deletion). In this problem, given an n-vertex graph G and a positive integer k, we want to decide whether there is a set of at most k vertices whose removal turns G into a graph of linear rankwidth at most one and if one exists, find such a vertex set. While the meta-theorem of Courcelle, Makowsky, and Rotics implies thatLRW1-Vertex Deletion can be solved in time f(k) * n^3 for some function f, it is not clear whether this problem allows a runtime with a modest exponential function. We establish that LRW1-Vertex Deletion can be solved in time 8^k * n^{O(1)}. The major obstacle to this end is how to handle a long induced cycle as an obstruction. To fix this issue, we define the necklace graphs and investigate their structural properties. We also show that the LRW1-Vertex Deletion has a polynomial kernel.
Cite as

Mamadou Moustapha Kanté, Eun Jung Kim, O-joung Kwon, and Christophe Paul. An FPT Algorithm and a Polynomial Kernel for Linear Rankwidth-1 Vertex Deletion. In 10th International Symposium on Parameterized and Exact Computation (IPEC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 43, pp. 138-150, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{kante_et_al:LIPIcs.IPEC.2015.138,
  author =	{Kant\'{e}, Mamadou Moustapha and Kim, Eun Jung and Kwon, O-joung and Paul, Christophe},
  title =	{{An FPT Algorithm and a Polynomial Kernel for Linear Rankwidth-1 Vertex Deletion}},
  booktitle =	{10th International Symposium on Parameterized and Exact Computation (IPEC 2015)},
  pages =	{138--150},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-92-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{43},
  editor =	{Husfeldt, Thore and Kanj, Iyad},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2015.138},
  URN =		{urn:nbn:de:0030-drops-55788},
  doi =		{10.4230/LIPIcs.IPEC.2015.138},
  annote =	{Keywords: (linear) rankwidth, distance-hereditary graphs, thread graphs, parameterized complexity, kernelization}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2015.270
A Polynomial Kernel for Block Graph Deletion

Authors: Eun Jung Kim and O-joung Kwon

Published in: LIPIcs, Volume 43, 10th International Symposium on Parameterized and Exact Computation (IPEC 2015)

Abstract
In the Block Graph Deletion problem, we are given a graph G on n vertices and a positive integer k, and the objective is to check whether it is possible to delete at most k vertices from G to make it a block graph, i.e., a graph in which each block is a clique. In this paper, we obtain a kernel with O(k^{6}) vertices for the Block Graph Deletion problem. This is a first step to investigate polynomial kernels for deletion problems into non-trivial classes of graphs of bounded rank-width, but unbounded tree-width. Our result also implies that Chordal Vertex Deletion admits a polynomial-size kernel on diamond-free graphs. For the kernelization and its analysis, we introduce the notion of 'complete degree' of a vertex. We believe that the underlying idea can be potentially applied to other problems. We also prove that the Block Graph Deletion problem can be solved in time 10^{k} * n^{O(1)}.
Cite as

Eun Jung Kim and O-joung Kwon. A Polynomial Kernel for Block Graph Deletion. In 10th International Symposium on Parameterized and Exact Computation (IPEC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 43, pp. 270-281, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{kim_et_al:LIPIcs.IPEC.2015.270,
  author =	{Kim, Eun Jung and Kwon, O-joung},
  title =	{{A Polynomial Kernel for Block Graph Deletion}},
  booktitle =	{10th International Symposium on Parameterized and Exact Computation (IPEC 2015)},
  pages =	{270--281},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-92-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{43},
  editor =	{Husfeldt, Thore and Kanj, Iyad},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2015.270},
  URN =		{urn:nbn:de:0030-drops-55893},
  doi =		{10.4230/LIPIcs.IPEC.2015.270},
  annote =	{Keywords: block graph, polynomial kernel, single-exponential FPT algorithm}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2015.294
Complexity and Approximability of Parameterized MAX-CSPs

Authors: Holger Dell, Eun Jung Kim, Michael Lampis, Valia Mitsou, and Tobias Mömke

Published in: LIPIcs, Volume 43, 10th International Symposium on Parameterized and Exact Computation (IPEC 2015)

Abstract
We study the optimization version of constraint satisfaction problems (Max-CSPs) in the framework of parameterized complexity; the goal is to compute the maximum fraction of constraints that can be satisfied simultaneously. In standard CSPs, we want to decide whether this fraction equals one. The parameters we investigate are structural measures, such as the treewidth or the clique-width of the variable–constraint incidence graph of the CSP instance. We consider Max-CSPs with the constraint types AND, OR, PARITY, and MAJORITY, and with various parameters k. We attempt to fully classify them into the following three cases: 1. The exact optimum can be computed in FPT-time. 2. It is W[1]-hard to compute the exact optimum, but there is a randomized FPT approximation scheme (FPT-AS), which computes a (1-epsilon)-approximation in time f(k,epsilon) * poly(n). 3. There is no FPT-AS unless FPT=W[1]. For the corresponding standard CSPs, we establish FPT vs. W[1]-hardness results.
Cite as

Holger Dell, Eun Jung Kim, Michael Lampis, Valia Mitsou, and Tobias Mömke. Complexity and Approximability of Parameterized MAX-CSPs. In 10th International Symposium on Parameterized and Exact Computation (IPEC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 43, pp. 294-306, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{dell_et_al:LIPIcs.IPEC.2015.294,
  author =	{Dell, Holger and Kim, Eun Jung and Lampis, Michael and Mitsou, Valia and M\"{o}mke, Tobias},
  title =	{{Complexity and Approximability of Parameterized MAX-CSPs}},
  booktitle =	{10th International Symposium on Parameterized and Exact Computation (IPEC 2015)},
  pages =	{294--306},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-92-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{43},
  editor =	{Husfeldt, Thore and Kanj, Iyad},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2015.294},
  URN =		{urn:nbn:de:0030-drops-55910},
  doi =		{10.4230/LIPIcs.IPEC.2015.294},
  annote =	{Keywords: Approximation, Structural Parameters, Constraint Satisfaction}
}

Kim, Heuna

Document
DOI: 10.4230/LIPIcs.SoCG.2016.48
Congruence Testing of Point Sets in 4-Space

Authors: Heuna Kim and Günter Rote

Published in: LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016)

Abstract
We give a deterministic O(n log n)-time algorithm to decide if two n-point sets in 4-dimensional Euclidean space are the same up to rotations and translations. It has been conjectured that O(n log n) algorithms should exist for any fixed dimension. The best algorithms in d-space so far are a deterministic algorithm by Brass and Knauer [Int. J. Comput. Geom. Appl., 2000] and a randomized Monte Carlo algorithm by Akutsu [Comp. Geom., 1998]. They take time O(n^2 log n) and O(n^(3/2) log n) respectively in 4-space. Our algorithm exploits many geometric structures and properties of 4-dimensional space.
Cite as

Heuna Kim and Günter Rote. Congruence Testing of Point Sets in 4-Space. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 48:1-48:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{kim_et_al:LIPIcs.SoCG.2016.48,
  author =	{Kim, Heuna and Rote, G\"{u}nter},
  title =	{{Congruence Testing of Point Sets in 4-Space}},
  booktitle =	{32nd International Symposium on Computational Geometry (SoCG 2016)},
  pages =	{48:1--48:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-009-5},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{51},
  editor =	{Fekete, S\'{a}ndor and Lubiw, Anna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.48},
  URN =		{urn:nbn:de:0030-drops-59409},
  doi =		{10.4230/LIPIcs.SoCG.2016.48},
  annote =	{Keywords: Congruence Testing Algorithm, Symmetry, Computational Geometry}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact