3,559 results on '"Kim, Eun Jung"'
Search Results
2. Bandwidth Parameterized by Cluster Vertex Deletion Number
- Author
-
Gima, Tatsuya, Kim, Eun Jung, Köhler, Noleen, Melissinos, Nikolaos, and Vasilakis, Manolis
- Subjects
Computer Science - Data Structures and Algorithms ,Computer Science - Computational Complexity - Abstract
Given a graph $G$ and an integer $b$, Bandwidth asks whether there exists a bijection $\pi$ from $V(G)$ to $\{1, \ldots, |V(G)|\}$ such that $\max_{\{u, v \} \in E(G)} | \pi(u) - \pi(v) | \leq 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 $\omega$ 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., Comment: An extended abstract of this article was presented at IPEC 2023
- Published
- 2023
3. Removal Mechanism of Hexavalent Chromium by Ferrous Oxalate: Role of Ferrous Iron and Oxalate
- Author
-
Ryu, Doyoon and Kim, Eun Jung
- Published
- 2024
- Full Text
- View/download PDF
4. Adult dental epithelial stem cell-derived organoids deposit hydroxylapatite biomineral.
- Author
-
Kim, Hyun-Yi, Cooley, Victoria, Kim, Eun-Jung, Li, Shujin, Lee, Jong-Min, Sheyfer, Dina, Liu, Wenjun, Klein, Ophir, Joester, Derk, and Jung, Han-Sung
- Subjects
Mice ,Animals ,Durapatite ,Dental Enamel ,Ameloblasts ,Amelogenesis ,Stem Cells ,Organoids - Abstract
Ameloblasts are specialized cells derived from the dental epithelium that produce enamel, a hierarchically structured tissue comprised of highly elongated hydroxylapatite (OHAp) crystallites. The unique function of the epithelial cells synthesizing crystallites and assembling them in a mechanically robust structure is not fully elucidated yet, partly due to limitations with in vitro experimental models. Herein, we demonstrate the ability to generate mineralizing dental epithelial organoids (DEOs) from adult dental epithelial stem cells (aDESCs) isolated from mouse incisor tissues. DEOs expressed ameloblast markers, could be maintained for more than five months (11 passages) in vitro in media containing modulators of Wnt, Egf, Bmp, Fgf and Notch signaling pathways, and were amenable to cryostorage. When transplanted underneath murine kidney capsules, organoids produced OHAp crystallites similar in composition, size, and shape to mineralized dental tissues, including some enamel-like elongated crystals. DEOs are thus a powerful in vitro model to study mineralization process by dental epithelium, which can pave the way to understanding amelogenesis and developing regenerative therapy of enamel.
- Published
- 2023
5. Representing Matroids over the Reals is $\exists \mathbb R$-complete
- Author
-
Kim, Eun Jung, de Mesmay, Arnaud, and Miltzow, Tillmann
- Subjects
Computer Science - Computational Complexity ,Mathematics - Combinatorics - Abstract
A matroid $M$ is an ordered pair $(E,I)$, where $E$ is a finite set called the ground set and a collection $I\subset 2^{E}$ called the independent sets which satisfy the conditions: (i) $\emptyset \in I$, (ii) $I'\subset I \in I$ implies $I'\in I$, and (iii) $I_1,I_2 \in I$ and $|I_1| < |I_2|$ implies that there is an $e\in I_2$ such that $I_1\cup \{e\} \in I$. The rank $rank(M)$ of a matroid $M$ is the maximum size of an independent set. We say that a matroid $M=(E,I)$ is representable over the reals if there is a map $\varphi \colon E \rightarrow \mathbb{R}^{rank(M)}$ such that $I\in I$ if and only if $\varphi(I)$ forms a linearly independent set. We study the problem of matroid realizability over the reals. Given a matroid $M$, we ask whether there is a set of points in the Euclidean space representing $M$. We show that matroid realizability is $\exists \mathbb R$-complete, already for matroids of rank 3. The complexity class $\exists \mathbb R$ can be defined as the family of algorithmic problems that is polynomial-time is equivalent to determining if a multivariate polynomial with integers coefficients has a real root. Our methods are similar to previous methods from the literature. Yet, the result itself was never pointed out and there is no proof readily available in the language of computer science., Comment: v2 and v3: Minor changes v4: Final version, to appear in DMTCS
- Published
- 2023
- Full Text
- View/download PDF
6. On weighted graph separation problems and flow-augmentation
- Author
-
Kim, Eun Jung, Masařík, Tomáš, Pilipczuk, Marcin, Sharma, Roohani, and Wahlström, Magnus
- Subjects
Computer Science - Data Structures and Algorithms ,Computer Science - Computational Complexity ,68Q27, 68Q25 ,F.2 - Abstract
One of the first application of the recently introduced technique of \emph{flow-augmentation} [Kim et al., STOC 2022] is a fixed-parameter algorithm for the weighted version of \textsc{Directed Feedback Vertex Set}, a landmark problem in parameterized complexity. In this note we explore applicability of flow-augmentation to other weighted graph separation problems parameterized by the size of the cutset. We show the following. -- In weighted undirected graphs \textsc{Multicut} is FPT, both in the edge- and vertex-deletion version. -- The weighted version of \textsc{Group Feedback Vertex Set} is FPT, even with an oracle access to group operations. -- The weighted version of \textsc{Directed Subset Feedback Vertex Set} is FPT. Our study reveals \textsc{Directed Symmetric Multicut} as the next important graph separation problem whose parameterized complexity remains unknown, even in the unweighted setting., Comment: 17 pages, 1 figure
- Published
- 2022
- Full Text
- View/download PDF
7. Comparison of microalgal hydrochar and pyrochar: production, physicochemical properties, and environmental application
- Author
-
Park, Chaerin and Kim, Eun Jung
- Published
- 2024
- Full Text
- View/download PDF
8. Flow-augmentation III: Complexity dichotomy for Boolean CSPs parameterized by the number of unsatisfied constraints
- Author
-
Kim, Eun Jung, Kratsch, Stefan, Pilipczuk, Marcin, and Wahlström, Magnus
- Subjects
Computer Science - Computational Complexity ,Computer Science - Data Structures and Algorithms - Abstract
We study the parameterized problem of satisfying ``almost all'' constraints of a given formula $F$ over a fixed, finite Boolean constraint language $\Gamma$, with or without weights. More precisely, for each finite Boolean constraint language $\Gamma$, we consider the following two problems. In Min SAT$(\Gamma)$, the input is a formula $F$ over $\Gamma$ and an integer $k$, and the task is to find an assignment $\alpha \colon V(F) \to \{0,1\}$ that satisfies all but at most $k$ constraints of $F$, or determine that no such assignment exists. In Weighted Min SAT$(\Gamma$), the input additionally contains a weight function $w \colon F \to \mathbb{Z}_+$ and an integer $W$, and the task is to find an assignment $\alpha$ such that (1) $\alpha$ satisfies all but at most $k$ constraints of $F$, and (2) the total weight of the violated constraints is at most $W$. We give a complete dichotomy for the fixed-parameter tractability of these problems: We show that for every Boolean constraint language $\Gamma$, either Weighted Min SAT$(\Gamma)$ is FPT; or Weighted Min SAT$(\Gamma)$ is W[1]-hard but Min SAT$(\Gamma)$ is FPT; or Min SAT$(\Gamma)$ is W[1]-hard. This generalizes recent work of Kim et al. (SODA 2021) which did not consider weighted problems, and only considered languages $\Gamma$ that cannot express implications $(u \to v)$ (as is used to, e.g., model digraph cut problems). Our result generalizes and subsumes multiple previous results, including the FPT algorithms for Weighted Almost 2-SAT, weighted and unweighted $\ell$-Chain SAT, and Coupled Min-Cut, as well as weighted and directed versions of the latter. The main tool used in our algorithms is the recently developed method of directed flow-augmentation (Kim et al., STOC 2022)., Comment: v2. Major update to all three flow-augmentation papers
- Published
- 2022
9. Algorithmic Applications of Tree-Cut Width
- Author
-
Ganian, Robert, Kim, Eun Jung, and Szeider, Stefan
- Subjects
Computer Science - Data Structures and Algorithms - Abstract
The recently introduced graph parameter tree-cut width plays a similar role with respect to immersions as the graph parameter treewidth plays with respect to minors. In this paper, we provide the first algorithmic applications of tree-cut width to hard combinatorial problems. Tree-cut width is known to be lower-bounded by a function of treewidth, but it can be much larger and hence has the potential to facilitate the efficient solution of problems that are not known to be fixed-parameter tractable (FPT) when parameterized by treewidth. We introduce the notion of nice tree-cut decompositions and provide FPT algorithms for the showcase problems Capacitated Vertex Cover, Capacitated Dominating Set, and Imbalance parameterized by the tree-cut width of an input graph. On the other hand, we show that List Coloring, Precoloring Extension, and Boolean CSP (the latter parameterized by the tree-cut width of the incidence graph) are W[1]-hard and hence unlikely to be fixed-parameter tractable when parameterized by tree-cut width., Comment: Full version to appear in the Siam Journal on Discrete Mathematics
- Published
- 2022
10. Feasibility of an implantable bioreactor for renal cell therapy using silicon nanopore membranes
- Author
-
Kim, Eun Jung, Chen, Caressa, Gologorsky, Rebecca, Santandreu, Ana, Torres, Alonso, Wright, Nathan, Goodin, Mark S, Moyer, Jarrett, Chui, Benjamin W, Blaha, Charles, Brakeman, Paul, Vartanian, Shant, Tang, Qizhi, David Humes, H, Fissell, William H, and Roy, Shuvo
- Subjects
Biological Sciences ,Engineering ,Biomedical Engineering ,Kidney Disease ,Organ Transplantation ,Transplantation ,Biotechnology ,Nanotechnology ,Bioengineering ,Renal and urogenital ,Humans ,Animals ,Swine ,Silicon ,Feasibility Studies ,Nanopores ,Kidney ,Bioreactors ,Cell- and Tissue-Based Therapy ,Epithelial Cells - Abstract
The definitive treatment for end-stage renal disease is kidney transplantation, which remains limited by organ availability and post-transplant complications. Alternatively, an implantable bioartificial kidney could address both problems while enhancing the quality and length of patient life. An implantable bioartificial kidney requires a bioreactor containing renal cells to replicate key native cell functions, such as water and solute reabsorption, and metabolic and endocrinologic functions. Here, we report a proof-of-concept implantable bioreactor containing silicon nanopore membranes to offer a level of immunoprotection to human renal epithelial cells. After implantation into pigs without systemic anticoagulation or immunosuppression therapy for 7 days, we show that cells maintain >90% viability and functionality, with normal or elevated transporter gene expression and vitamin D activation. Despite implantation into a xenograft model, we find that cells exhibit minimal damage, and recipient cytokine levels are not suggestive of hyperacute rejection. These initial data confirm the potential feasibility of an implantable bioreactor for renal cell therapy utilizing silicon nanopore membranes.
- Published
- 2023
11. Twin-width VIII: delineation and win-wins
- Author
-
Bonnet, Édouard, Chakraborty, Dibyayan, Kim, Eun Jung, Köhler, Noleen, Lopes, Raul, and Thomassé, Stéphan
- Subjects
Computer Science - Data Structures and Algorithms ,Computer Science - Discrete Mathematics ,Computer Science - Logic in Computer Science ,Mathematics - Combinatorics ,05C85, 05C75 ,F.2.2 - Abstract
We introduce the notion of delineation. A graph class $\mathcal C$ is said delineated if for every hereditary closure $\mathcal D$ of a subclass of $\mathcal C$, it holds that $\mathcal D$ has bounded twin-width if and only if $\mathcal D$ is monadically dependent. An effective strengthening of delineation for a class $\mathcal C$ implies that tractable FO model checking on $\mathcal C$ is perfectly understood: On hereditary closures $\mathcal D$ of subclasses of $\mathcal C$, FO model checking is fixed-parameter tractable (FPT) exactly when $\mathcal 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 show that segment graphs, directed path graphs, 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_4$-free two-lengthed segment graphs have unbounded twin-width. Our new results, combined with the known FPT algorithm for FO model checking on graphs given with $O(1)$-sequences, lead to win-win arguments. For instance, we derive FPT algorithms for $k$-Ladder on visibility graphs of 1.5D terrains, and $k$-Independent Set on visibility graphs of simple polygons., Comment: 51 pages, 19 figures
- Published
- 2022
12. The expatriate and local hotel general managers: differing approaches to employees’ loyalty
- Author
-
Lee, Yong-Ki, Sinha, Paresha N., Kim, Soon-Ho, Swanson, Eric Melvin, Yang, Jae-Jang, and Kim, Eun-Jung
- Published
- 2023
- Full Text
- View/download PDF
13. Minimum 19-Year Clinical Results and Patient Satisfaction After Total Knee Arthroplasty
- Author
-
Kim, Young-Hoo, Park, Jang-Won, Jang, Young-Soo, and Kim, Eun-Jung
- Published
- 2024
- Full Text
- View/download PDF
14. Stability Enhancement of Target Enzymes via Tyrosinase-Mediated Site-Specific Polysaccharide Coating
- Author
-
Kim, Hyun, Lee, Uk-Jae, Lim, Gyu-Min, Kim, Jin-Young, Lee, Jeongchan, Song, Hanbit, Kim, Eun-jung, Kim, Jungbae, Hwang, Nathaniel S., and Kim, Byung-Gee
- Published
- 2023
- Full Text
- View/download PDF
15. Therapeutic Effects of Combination of Nebivolol and Donepezil: Targeting Multifactorial Mechanisms in ALS
- Author
-
Lee, Soo Yeon, Cho, Hye-Yeon, Oh, Jung-Pyo, Park, Jiae, Bae, Sang-Hun, Park, Haesun, Kim, Eun Jung, and Lee, Ji-Hyun
- Published
- 2023
- Full Text
- View/download PDF
16. Attack of the Knights: A Non Uniform Cache Side-Channel Attack
- Author
-
Mahmud, Farabi, Kim, Sungkeun, Chawla, Harpreet Singh, Tsai, Chia-Che, Kim, Eun Jung, and Muzahid, Abdullah
- Subjects
Computer Science - Cryptography and Security ,Computer Science - Hardware Architecture - Abstract
For a distributed last-level cache (LLC) in a large multicore chip, the access time to one LLC bank can significantly differ from that to another due to the difference in physical distance. In this paper, we successfully demonstrated a new distance-based side-channel attack by timing the AES decryption operation and extracting part of an AES secret key on an Intel Knights Landing CPU. We introduce several techniques to overcome the challenges of the attack, including the use of multiple attack threads to ensure LLC hits, to detect vulnerable memory locations, and to obtain fine-grained timing of the victim operations. While operating as a covert channel, this attack can reach a bandwidth of 205 kbps with an error rate of only 0.02%. We also observed that the side-channel attack can extract 4 bytes of an AES key with 100% accuracy with only 4000 trial rounds of encryption
- Published
- 2021
- Full Text
- View/download PDF
17. Flow-augmentation I: Directed graphs
- Author
-
Kim, Eun Jung, Kratsch, Stefan, Pilipczuk, Marcin, and Wahlström, Magnus
- Subjects
Computer Science - Data Structures and Algorithms ,Computer Science - Discrete Mathematics - Abstract
We show a flow-augmentation algorithm in directed graphs: There exists a randomized polynomial-time algorithm that, given a directed graph $G$, two vertices $s,t \in V(G)$, and an integer $k$, adds (randomly) to $G$ a number of arcs such that for every minimal $st$-cut $Z$ in $G$ of size at most $k$, with probability $2^{-\mathrm{poly}(k)}$ the set $Z$ becomes a minimum $st$-cut in the resulting graph. We also provide a deterministic counterpart of this procedure. The directed flow-augmentation tool allows us to prove fixed-parameter tractability of a number of problems parameterized by the cardinality of the deletion set, whose parameterized complexity status was repeatedly posed as open problems: (1) Chain SAT, defined by Chitnis, Egri, and Marx [ESA'13, Algorithmica'17], (2) a number of weighted variants of classic directed cut problems, such as Weighted $st$-Cut} or Weighted Directed Feedback Vertex Set. By proving that Chain SAT is FPT, we confirm a conjecture of Chitnis, Egri, and Marx that, for any graph $H$, if the List $H$-Coloring problem is polynomial-time solvable, then the corresponding vertex-deletion problem is fixed-parameter tractable., Comment: v2. Major update of three flow-augmentation papers. Includes a deterministic version. Weighted Almost 2-SAT algorithm has been removed, as it is superseded by a more general algorithm of Flow-Augmentation III (arXiv:2207.07422)
- Published
- 2021
18. Twin-width VI: the lens of contraction sequences
- Author
-
Bonnet, Édouard, Kim, Eun Jung, Reinald, Amadeus, and Thomassé, Stéphan
- Subjects
Computer Science - Data Structures and Algorithms ,Computer Science - Discrete Mathematics ,Computer Science - Logic in Computer Science ,Mathematics - Combinatorics ,68R10, 05C85 ,F.2.2 - Abstract
A contraction sequence of a graph consists of iteratively merging two of its vertices until only one vertex remains. The recently introduced twin-width graph invariant is based on contraction sequences. More precisely, if one puts red edges between two vertices representing non-homogeneous subsets, the twin-width is the minimum integer $d$ such that a contraction sequence keeps red degree at most $d$. By changing the condition imposed on the trigraphs (i.e., graphs with some edges being red) and possibly slightly tweaking the notion of contractions, we show how to characterize the well-established bounded rank-width, tree-width, linear rank-width, path-width, and proper minor-closed classes by means of contraction sequences. As an application we give a transparent alternative proof of the celebrated Courcelle's theorem (actually of its generalization by Courcelle, Makowsky, and Rotics), that MSO$_2$ (resp. MSO$_1$) model checking on graphs with bounded tree-width (resp. bounded rank-width) is fixed-parameter tractable in the size of the input sentence. We then explore new avenues along the general theme of contraction sequences both in order to refine the landscape between bounded tree-width and bounded twin-width (via spanning twin-width) and to capture more general classes than bounded twin-width. To this end, we define an oriented version of twin-width, where appearing red edges are oriented away from the newly contracted vertex, and the mere red out-degree should remain bounded. Surprisingly, classes of bounded oriented twin-width coincide with those of bounded twin-width. Finally we examine, from an algorithmic standpoint, the concept of partial contraction sequences, where, instead of terminating on a single-vertex graph, the sequence ends when reaching a particular target class., Comment: 27 pages, 3 figures
- Published
- 2021
19. EPTAS and Subexponential Algorithm for Maximum Clique on Disk and Unit Ball Graphs
- Author
-
Bonamy, Marthe, Bonnet, Édouard, Bousquet, Nicolas, Charbit, Pierre, Giannopoulos, Panos, Kim, Eun Jung, Rzążewski, Paweł, Sikora, Florian, and Thomassé, Stéphan
- Subjects
Computer Science - Data Structures and Algorithms ,Computer Science - Computational Complexity ,Computer Science - Computational Geometry - 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 \textsc{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 that the disjoint union of two odd cycles is never the complement of a disk graph nor of a unit (3-dimensional) ball graph. From that fact and existing results, we derive a simple QPTAS and a subexponential algorithm running in time $2^{\tilde{O}(n^{2/3})}$ for \textsc{Maximum Clique} on disk and unit ball graphs. We then obtain a randomized EPTAS for computing the independence number on graphs having no disjoint union of two odd cycles as an induced subgraph, bounded VC-dimension, and linear independence number. This, in combination with our structural results, yields a randomized EPTAS for \textsc{Max Clique} on disk and unit ball graphs. \textsc{Max Clique} on unit ball graphs is equivalent to finding, given a collection of points in $\mathbb R^3$, a maximum subset of points with diameter at most some fixed value. In stark contrast, \textsc{Maximum Clique} on ball graphs and unit $4$-dimensional ball graphs, as well as intersection graphs of filled ellipses (even close to unit disks) or filled triangles is unlikely to have such algorithms. Indeed, we show that, for all those problems, there is a constant ratio of approximation which cannot be attained even in time $2^{n^{1-\varepsilon}}$, unless the Exponential Time Hypothesis fails., Comment: arXiv admin note: substantial text overlap with arXiv:1712.05010, arXiv:1803.01822
- Published
- 2021
- Full Text
- View/download PDF
20. Obstructions for matroids of path-width at most k and graphs of linear rank-width at most k
- Author
-
Kanté, Mamadou Mostapha, Kim, Eun Jung, Kwon, O-joung, and Oum, Sang-il
- Subjects
Mathematics - Combinatorics ,05B35 (Primary), 05C75 (Secondary) - Abstract
Every minor-closed class of matroids of bounded branch-width can be characterized by a list of excluded minors, but unlike graphs, this list may need to be infinite in general. However, for each fixed finite field $\mathbb F$, the list needs to contain only finitely many $\mathbb F$-representable matroids, due to the well-quasi-ordering of $\mathbb 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 $\mathbb 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 $\mathbb F$, every $\mathbb F$-representable excluded minor for the class of matroids of path-width at most $k$ has at most $2^{|\mathbb{F}|^{O(k^2)}}$ elements. We can therefore compute, for any integer $k$ and a fixed finite field $\mathbb F$, the set of $\mathbb 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 $\mathbb 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^2)}}$ vertices, which also results in a similar algorithmic consequence for linear rank-width of graphs., Comment: 19 pages; slightly revised
- Published
- 2021
21. Harnessing the dental cells derived from human induced pluripotent stem cells for hard tissue engineering
- Author
-
Kim, Eun-Jung, Kim, Ka-Hwa, Kim, Hyun-Yi, Lee, Dong-Joon, Li, Shujin, Ngoc Han, Mai, and Jung, Han-Sung
- Published
- 2024
- Full Text
- View/download PDF
22. Jagged1 intracellular domain/SMAD3 complex transcriptionally regulates TWIST1 to drive glioma invasion
- Author
-
Kim, Jung Yun, Hong, Nayoung, Park, Sehyeon, Ham, Seok Won, Kim, Eun-Jung, Kim, Sung-Ok, Jang, Junseok, Kim, Yoonji, Kim, Jun-Kyum, Kim, Sung-Chan, Park, Jong-Whi, and Kim, Hyunggee
- Published
- 2023
- Full Text
- View/download PDF
23. Comparison of postoperative nausea and vomiting between Remimazolam and Propofol in Patients undergoing oral and maxillofacial surgery: a prospective Randomized Controlled Trial
- Author
-
Kim, Eun-Jung, Kim, Cheul-Hong, Yoon, Ji-Young, Byeon, Gyeong-Jo, Kim, Hee Young, and Choi, Eun-Ji
- Published
- 2023
- Full Text
- View/download PDF
24. Twin-width and polynomial kernels
- Author
-
Bonnet, Édouard, Kim, Eun Jung, Reinald, Amadeus, Thomassé, Stéphan, and Watrigant, Rémi
- Subjects
Computer Science - Data Structures and Algorithms ,Computer Science - Computational Complexity ,Computer Science - Discrete Mathematics ,Mathematics - Combinatorics ,05C85 ,F.2.2 - 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. Our main result is that a polynomial kernel for $k$-Dominating Set on graphs of twin-width at most 4 would contradict a standard complexity-theoretic assumption. The reduction is quite involved, especially to get the twin-width upper bound down to 4, and can be tweaked to work for Connected $k$-Dominating Set and Total $k$-Dominating Set (albeit with a worse upper bound on the twin-width). The $k$-Independent Set problem admits the same lower bound by a much simpler argument, previously observed [ICALP '21], which extends to $k$-Independent Dominating Set, $k$-Path, $k$-Induced Path, $k$-Induced Matching, etc. 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. Interestingly the kernel applies to graphs of Vapnik-Chervonenkis 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 optimization/decision graph problems can be solved in polynomial time on graphs of twin-width at most 1., Comment: 32 pages, 11 figures
- Published
- 2021
25. A Constant-factor Approximation for Weighted Bond Cover
- Author
-
Kim, Eun Jung, Lee, Euiwoong, and Thilikos, Dimitrios M.
- Subjects
Computer Science - Data Structures and Algorithms ,05C35, 05C83, 05C85, 68R10, 68W25 ,F.2.2 ,G.2.2 - Abstract
The {\sc Weighted} $\mathcal{F}$-\textsc{Vertex Deletion} for a class ${\cal F}$ of graphs asks, weighted graph $G$, for a minimum weight vertex set $S$ such that $G-S\in{\cal F}.$ The case when ${\cal F}$ is minor-closed and excludes some graph as a minor has received particular attention but a constant-factor approximation remained elusive for \textsc{Weighted} $\mathcal{F}$-{\sc Vertex Deletion}. Only three cases of minor-closed ${\cal F}$ are known to admit constant-factor approximations, namely \textsc{Vertex Cover}, \textsc{Feedback Vertex Set} and \textsc{Diamond Hitting Set}. We study the problem for the class ${\cal F}$ of $\theta_c$-minor-free graphs, under the equivalent setting of the \textsc{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 $\theta_c$-minor-model either contains a large two-terminal {\sl protrusion}, or contains a constant-size $\theta_c$-minor-model, or a collection of pairwise disjoint {\sl 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 \textsc{Weighted} $\mathcal{F}$-\textsc{Vertex Deletion}, our result may be useful as a template for algorithms for other minor-closed families.
- Published
- 2021
26. Generation of a novel monoclonal antibody against inflammatory biomarker S100A8 using hybridoma technology
- Author
-
Kim, Jong-Pyo, Yun, Hanool, Kim, Eun-Jung, Kim, Yun-Gon, Lee, Chang-Soo, Ko, Byoung Joon, Kim, Byung-Gee, and Jeong, Hee-Jin
- Published
- 2023
- Full Text
- View/download PDF
27. Potential use of polydimethylsiloxane phantom in acupuncture manipulation practice
- Author
-
Lee, Yeonsun, Lee, Hyosang, Kim, Eun Jung, Lee, Seung Deok, and Jung, Chan Yung
- Published
- 2024
- Full Text
- View/download PDF
28. Subpial delivery of adeno-associated virus 9-synapsin-caveolin-1 (AAV9-SynCav1) preserves motor neuron and neuromuscular junction morphology, motor function, delays disease onset, and extends survival in hSOD1G93A mice
- Author
-
Wang, Shanshan, Ichinomiya, Taiga, Savchenko, Paul, Wang, Dongsheng, Sawada, Atsushi, Li, Xiaojing, Duong, Tiffany, Li, Wenxi, Bonds, Jacqueline A, Kim, Eun Jung, Miyanohara, Atsushi, Roth, David M, Patel, Hemal H, Patel, Piyush M, Tadokoro, Takahiro, Marsala, Martin, and Head, Brian P
- Subjects
Medical Biotechnology ,Biomedical and Clinical Sciences ,Neurosciences ,Neurodegenerative ,ALS ,Genetics ,Rare Diseases ,Brain Disorders ,Prevention ,Neurological ,Amyotrophic Lateral Sclerosis ,Animals ,Caveolin 1 ,Dependovirus ,Disease Models ,Animal ,Female ,Gene Transfer Techniques ,Humans ,Male ,Mice ,Mice ,Transgenic ,Motor Neurons ,Neuromuscular Junction ,Rats ,Superoxide Dismutase ,Synapsins ,caveolin-1 ,membrane/lipid raft ,gene therapy ,hSOD1(G93A) ,amyotrophic lateral sclerosis ,motor neuron ,neuromuscular junction ,hSOD1G93A ,Oncology and Carcinogenesis ,Oncology and carcinogenesis - Abstract
Elevating neuroprotective proteins using adeno-associated virus (AAV)-mediated gene delivery shows great promise in combating devastating neurodegenerative diseases. Amyotrophic lateral sclerosis (ALS) is one such disease resulting from loss of upper and lower motor neurons (MNs) with 90-95% of cases sporadic (SALS) in nature. Due to the unknown etiology of SALS, interventions that afford neuronal protection and preservation are urgently needed. Caveolin-1 (Cav-1), a membrane/lipid rafts (MLRs) scaffolding and neuroprotective protein, and MLR-associated signaling components are decreased in degenerating neurons in postmortem human brains. We previously showed that, when crossing our SynCav1 transgenic mouse (TG) with the mutant human superoxide dismutase 1 (hSOD1G93A) mouse model of ALS, the double transgenic mouse (SynCav1 TG/hSOD1G93A) exhibited better motor function and longer survival. The objective of the current study was to test whether neuron-targeted Cav-1 upregulation in the spinal cord using AAV9-SynCav1 could improve motor function and extend longevity in mutant humanized mouse and rat (hSOD1G93A) models of familial (F)ALS. Methods: Motor function was assessed by voluntary running wheel (RW) in mice and forelimb grip strength (GS) and motor evoked potentials (MEP) in rats. Immunofluorescence (IF) microscopy for choline acetyltransferase (ChAT) was used to assess MN morphology. Neuromuscular junctions (NMJs) were measured by bungarotoxin-a (Btx-a) and synaptophysin IF. Body weight (BW) was measured weekly, and the survival curve was determined by Kaplan-Meier analysis. Results: Following subpial gene delivery to the lumbar spinal cord, male and female hSOD1G93A mice treated with SynCav1 exhibited delayed disease onset, greater running-wheel performance, preserved spinal alpha-motor neuron morphology and NMJ integrity, and 10% increased longevity, independent of affecting expression of the mutant hSOD1G93A protein. Cervical subpial SynCav1 delivery to hSOD1G93A rats preserved forelimb GS and MEPs in the brachial and gastrocnemius muscles. Conclusion: In summary, subpial delivery of SynCav1 protects and preserves spinal motor neurons, and extends longevity in a familial mouse model of ALS without reducing the toxic monogenic component. Furthermore, subpial SynCav1 delivery preserved neuromuscular function in a rat model of FALS. The latter findings strongly indicate the therapeutic applicability of SynCav1 to treat ALS attributed to monogenic (FALS) and potentially in sporadic cases (i.e., SALS).
- Published
- 2022
29. Twin-width II: small classes
- Author
-
Bonnet, Édouard, Geniet, Colin, Kim, Eun Jung, Thomassé, Stéphan, and Watrigant, Rémi
- Subjects
Twin-width ,small classes ,expanders ,clique subdivisions ,sparsity - Abstract
The recently introduced twin-width of a graph $G$ is the minimum integer $d$ such that $G$ has a $d$-contraction sequence, that is, a sequence of $\left| V(G) \right|-1$ iterated vertex identifications for which the overall maximum number of red edges incident to a single vertex is at most $d$, where a red edge appears between two sets of identified vertices if they are not homogeneous in $G$ (not fully adjacent nor fully non-adjacent). We show that if a graph admits a $d$-contraction sequence, then it also has a linear-arity tree of $f(d)$-contractions, for some function $f$. Informally if we accept to worsen the twin-width bound, we can choose the next contraction from a set of $\Theta(\left| V(G) \right|)$ pairwise disjoint pairs of vertices. This has two main consequences. First it permits to show that every bounded twin-width class is small, i.e., has at most $n!c^n$ graphs labeled by $[n]$, for some constant $c$. This unifies and extends the same result for bounded treewidth graphs [Beineke and Pippert, JCT '69], proper subclasses of permutations graphs [Marcus and Tardos, JCTA '04], and proper minor-free classes [Norine et al., JCTB '06]. It implies in turn that bounded-degree graphs, interval graphs, and unit disk graphs have unbounded twin-width. The second consequence is an $O(\log n)$-adjacency labeling scheme for bounded twin-width graphs, confirming several cases of the implicit graph conjecture. We then explore the small conjecture that, conversely, every small hereditary class has bounded twin-width. The conjecture passes many tests. Inspired by sorting networks of logarithmic depth, we show that $\log_{\Theta(\log \log d)}n$-subdivisions of $K_n$ (a small class when $d$ is constant) have twin-width at most $d$. We obtain a rather sharp converse with a surprisingly direct proof: the $\log_{d+1}n$-subdivision of $K_n$ has twin-width at least $d$. Secondly graphs with bounded stack or queue number (also small classes) have bounded twin-width. These sparse classes are surprisingly rich since they contain certain (small) classes of expanders. Thirdly we show that cubic expanders obtained by iterated random 2-lifts from $K_4$ [Bilu and Linial, Combinatorica '06] also have bounded twin-width. These graphs are related to so-called separable permutations and also form a small class. We suggest a promising connection between the small conjecture and group theory. Finally we define a robust notion of sparse twin-width. We show that for a hereditary class $\mathcal C$ of bounded twin-width the five following conditions are equivalent: every graph in $\mathcal C$ (1) has no $K_{t,t}$ subgraph for some fixed $t$, (2) has an adjacency matrix without a $d$-by-$d$ division with a 1 entry in each of the $d^2$ cells for some fixed $d$, (3) has at most linearly many edges, (4) the subgraph closure of $\mathcal C$ has bounded twin-width, and (5) $\mathcal C$ has bounded expansion. We discuss how sparse classes with similar behavior with respect to clique subdivisions compare to bounded sparse twin-width.Mathematics Subject Classifications: 68R10, 05C30, 05C48Keywords: Twin-width, small classes, expanders, clique subdivisions, sparsity
- Published
- 2022
30. Continual Learning Approach for Improving the Data and Computation Mapping in Near-Memory Processing System
- Author
-
Majumder, Pritam, Huang, Jiayi, Kim, Sungkeun, Muzahid, Abdullah, Siegers, Dylan, Tsai, Chia-Che, and Kim, Eun Jung
- Subjects
Computer Science - Hardware Architecture ,Computer Science - Machine Learning ,Computer Science - Networking and Internet Architecture ,Computer Science - Operating Systems - Abstract
The resurgence of near-memory processing (NMP) with the advent of big data has shifted the computation paradigm from processor-centric to memory-centric computing. To meet the bandwidth and capacity demands of memory-centric computing, 3D memory has been adopted to form a scalable memory-cube network. Along with NMP and memory system development, the mapping for placing data and guiding computation in the memory-cube network has become crucial in driving the performance improvement in NMP. However, it is very challenging to design a universal optimal mapping for all applications due to unique application behavior and intractable decision space. In this paper, we propose an artificially intelligent memory mapping scheme, AIMM, that optimizes data placement and resource utilization through page and computation remapping. Our proposed technique involves continuously evaluating and learning the impact of mapping decisions on system performance for any application. AIMM uses a neural network to achieve a near-optimal mapping during execution, trained using a reinforcement learning algorithm that is known to be effective for exploring a vast design space. We also provide a detailed AIMM hardware design that can be adopted as a plugin module for various NMP systems. Our experimental evaluation shows that AIMM improves the baseline NMP performance in single and multiple program scenario by up to 70% and 50%, respectively.
- Published
- 2021
31. The efficacy and safety of Simiao Xiaobi decoction on rheumatoid arthritis: A systematic review and meta‑analysis
- Author
-
Chae, Soo-Yeon, Park, Seo-Hyun, Kim, Joo-Hee, Kim, Eun-Jung, Seo, Byung-Kwan, Park, Seong-Sik, and Sung, Won-Suk
- Published
- 2024
- Full Text
- View/download PDF
32. Educational interventions for improving nursing shift handovers: A systematic review
- Author
-
Choi, Jin Yi, Byun, Mikyoung, and Kim, Eun Jung
- Published
- 2024
- Full Text
- View/download PDF
33. Complexity and algorithms for constant diameter augmentation problems
- Author
-
Kim, Eun Jung, Milanic, Martin, Monnot, Jérôme, and Picouleau, Christophe
- Subjects
Mathematics - Combinatorics - Abstract
We study the following problem: for given integers $d,k$ and graph $G$, can we obtain a graph with diameter $d$ via at most $k$ edge deletions ? We determine the computational complexity of this and related problems for different values of $d$.
- Published
- 2020
34. Towards constant-factor approximation for chordal / distance-hereditary vertex deletion
- Author
-
Ahn, Jungho, Kim, Eun Jung, and Lee, Euiwoong
- Subjects
Computer Science - Data Structures and Algorithms ,Computer Science - Discrete Mathematics ,Mathematics - Combinatorics - Abstract
For a family of graphs $\mathcal{F}$, Weighted $\mathcal{F}$-Deletion is the problem for which the input is a vertex weighted graph $G=(V,E)$ and the goal is to delete $S\subseteq V$ with minimum weight such that $G\setminus S\in\mathcal{F}$. 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 $F$ 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., Comment: 27 pages, 2 figures
- Published
- 2020
35. Grundy Distinguishes Treewidth from Pathwidth
- Author
-
Belmonte, Rémy, Kim, Eun Jung, Lampis, Michael, Mitsou, Valia, and Otachi, Yota
- Subjects
Computer Science - Data Structures and Algorithms - 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., Comment: Conference version appeared in ESA 2020. This is the full version which has been accepted for publication at SIDMA
- Published
- 2020
- Full Text
- View/download PDF
36. On the tree-width of even-hole-free graphs
- Author
-
Aboulker, Pierre, Adler, Isolde, Kim, Eun Jung, Sintiari, Ni Luh Dewi, and Trotignon, Nicolas
- Subjects
Computer Science - Discrete Mathematics ,Computer Science - Data Structures and Algorithms ,Mathematics - Combinatorics - Abstract
The class of all even-hole-free graphs has unbounded tree-width, as it contains all complete graphs. Recently, a class of (even-hole, $K_4$)-free graphs was constructed, that still has unbounded tree-width [Sintiari and Trotignon, 2019]. The class has unbounded degree and contains arbitrarily large clique-minors. We ask whether this is necessary. We prove that for every graph $G$, if $G$ excludes a fixed graph $H$ as a minor, then $G$ either has small tree-width, or $G$ contains a large wall or the line graph of a large wall as induced subgraph. This can be seen as a strengthening of Robertson and Seymour's excluded grid theorem for the case of minor-free graphs. Our theorem implies that every class of even-hole-free graphs excluding a fixed graph as a minor has bounded tree-width. In fact, our theorem applies to a more general class: (theta, prism)-free graphs. This implies the known result that planar even hole-free graph have bounded tree-width [da Silva and Linhares Sales, Discrete Applied Mathematics 2010]. We conjecture that even-hole-free graphs of bounded degree have bounded tree-width. If true, this would mean that even-hole-freeness is testable in the bounded-degree graph model of property testing. We prove the conjecture for subcubic graphs and we give a bound on the tree-width of the class of (even hole, pyramid)-free graphs of degree at most 4.
- Published
- 2020
- Full Text
- View/download PDF
37. Twin-width III: Max Independent Set, Min Dominating Set, and Coloring
- Author
-
Bonnet, Édouard, Geniet, Colin, Kim, Eun Jung, Thomassé, Stéphan, and Watrigant, Rémi
- Subjects
Computer Science - Data Structures and Algorithms ,Computer Science - Computational Complexity ,Computer Science - Discrete Mathematics ,Mathematics - Combinatorics ,05C85 ,F.2.2 - Abstract
We recently introduced the graph invariant twin-width, 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 is provided. We further show how to solve weighted $k$-Independent Set, Subgraph Isomorphism, and Induced Subgraph Isomorphism, in time $2^{O(k \log k)}n$. These 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, we establish that bounded twin-width classes are $\chi$-bounded. This significantly extends the $\chi$-boundedness of bounded rank-width classes, and does so with a very concise proof. 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. Given that biclique edge-partition, we show how to solve the unweighted Single-Source Shortest Paths and hence All-Pairs Shortest Paths in sublinear time $O(n \log n)$ and time $O(n^2 \log n)$, respectively. Finally we show that Min Dominating Set and related problems have constant integrality gaps on bounded twin-width classes, thereby getting constant approximations on these classes., Comment: 38 pages, 6 figures. This version contains more results, notably the approximation for Min Dominating Set, and the title has been edited accordingly
- Published
- 2020
38. Flow-augmentation II: Undirected graphs
- Author
-
Kim, Eun Jung, Kratsch, Stefan, Pilipczuk, Marcin, and Wahlström, Magnus
- Subjects
Computer Science - Data Structures and Algorithms - Abstract
We present an undirected version of the recently introduced flow-augmentation technique: Given an undirected multigraph $G$ with distinguished vertices $s,t \in V(G)$ and an integer $k$, one can in randomized $k^{O(1)} \cdot (|V(G)| + |E(G)|)$ time sample a set $A \subseteq \binom{V(G)}{2}$ such that the following holds: for every inclusion-wise minimal $st$-cut $Z$ in $G$ of cardinality at most $k$, $Z$ becomes a minimum-cardinality cut between $s$ and $t$ in $G+A$ (i.e., in the multigraph $G$ with all edges of $A$ added) with probability $2^{-O(k \log k)}$. Compared to the version for directed graphs [STOC 2022], the version presented here has improved success probability ($2^{-O(k \log k)}$ instead of $2^{-O(k^4 \log k)}$), linear dependency on the graph size in the running time bound, and an arguably simpler proof. An immediate corollary is that the Bi-objective $st$-Cut problem can be solved in randomized FPT time $2^{O(k \log k)} (|V(G)|+|E(G)|)$ on undirected graphs., Comment: v2. Major update of all three flow-augmentation papers. The partial dichotomy part has been removed from this work, as it is superseded by the full dichotomy of Flow-Augmentation III (arXiv:2207.07422)
- Published
- 2020
39. Twin-width II: small classes
- Author
-
Bonnet, Édouard, Geniet, Colin, Kim, Eun Jung, Thomassé, Stéphan, and Watrigant, Rémi
- Subjects
Computer Science - Discrete Mathematics ,Computer Science - Data Structures and Algorithms ,Computer Science - Logic in Computer Science ,Mathematics - Combinatorics ,68R10, 05C30, 05C48 ,G.2.2 - Abstract
The twin-width of a graph $G$ is the minimum integer $d$ such that $G$ has a $d$-contraction sequence, that is, a sequence of $|V(G)|-1$ iterated vertex identifications for which the overall maximum number of red edges incident to a single vertex is at most $d$, where a red edge appears between two sets of identified vertices if they are not homogeneous in $G$. We show that if a graph admits a $d$-contraction sequence, then it also has a linear-arity tree of $f(d)$-contractions, for some function $f$. First this permits to show that every bounded twin-width class is small, i.e., has at most $n!c^n$ graphs labeled by $[n]$, for some constant $c$. This unifies and extends the same result for bounded treewidth graphs [Beineke and Pippert, JCT '69], proper subclasses of permutations graphs [Marcus and Tardos, JCTA '04], and proper minor-free classes [Norine et al., JCTB '06]. The second consequence is an $O(\log n)$-adjacency labeling scheme for bounded twin-width graphs, confirming several cases of the implicit graph conjecture. We then explore the "small conjecture" that, conversely, every small hereditary class has bounded twin-width. Inspired by sorting networks of logarithmic depth, we show that $\log_{\Theta(\log \log d)}n$-subdivisions of $K_n$ (a small class when $d$ is constant) have twin-width at most $d$. We obtain a rather sharp converse with a surprisingly direct proof: the $\log_{d+1}n$-subdivision of $K_n$ has twin-width at least $d$. Secondly graphs with bounded stack or queue number (also small classes) have bounded twin-width. Thirdly we show that cubic expanders obtained by iterated random 2-lifts from $K_4$~[Bilu and Linial, Combinatorica '06] have bounded twin-width, too. We suggest a promising connection between the small conjecture and group theory. Finally we define a robust notion of sparse twin-width and discuss how it compares with other sparse classes., Comment: 37 pages, 9 figures
- Published
- 2020
40. Twin-width I: tractable FO model checking
- Author
-
Bonnet, Édouard, Kim, Eun Jung, Thomassé, Stéphan, and Watrigant, Rémi
- Subjects
Computer Science - Data Structures and Algorithms ,Computer Science - Discrete Mathematics ,Computer Science - Logic in Computer Science ,68Q25 ,F.2.2 - Abstract
Inspired by a width invariant defined on permutations by Guillemot and Marx [SODA '14], we introduce the notion of twin-width on graphs and on matrices. Proper minor-closed classes, bounded rank-width graphs, map graphs, $K_t$-free unit $d$-dimensional ball graphs, posets with antichains of bounded size, and proper subclasses of dimension-2 posets all have bounded twin-width. On all these classes (except map graphs without geometric embedding) we show how to compute in polynomial time a sequence of $d$-contractions, witness that the twin-width is at most $d$. We show that FO model checking, that is deciding if a given first-order formula $\phi$ evaluates to true for a given binary structure $G$ on a domain $D$, is FPT in $|\phi|$ on classes of bounded twin-width, provided the witness is given. More precisely, being given a $d$-contraction sequence for $G$, our algorithm runs in time $f(d,|\phi|) \cdot |D|$ where $f$ is a computable but non-elementary function. We also prove that bounded twin-width is preserved by FO interpretations and transductions (allowing operations such as squaring or complementing a graph). This unifies and significantly extends the knowledge on fixed-parameter tractability of FO model checking on non-monotone classes, such as the FPT algorithm on bounded-width posets by Gajarsk\'y et al. [FOCS '15]., Comment: 49 pages, 9 figures
- Published
- 2020
41. Grundy Coloring & friends, Half-Graphs, Bicliques
- Author
-
Aboulker, Pierre, Bonnet, Édouard, Kim, Eun Jung, and Sikora, Florian
- Subjects
Computer Science - Computational Complexity ,Computer Science - Discrete Mathematics ,Computer Science - Data Structures and Algorithms ,Mathematics - Combinatorics ,68W05 ,F.2.2 - Abstract
The first-fit coloring is a heuristic that assigns to each vertex, arriving in a specified order $\sigma$, the smallest available color. The problem Grundy Coloring asks how many colors are needed for the most adversarial vertex ordering $\sigma$, 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., Comment: 25 pages, 5 figures
- Published
- 2020
42. Sensor development for multiple simultaneous classifications using genetically engineered M13 bacteriophages
- Author
-
Lee, Yujin, Kim, Sung-Jo, Kim, Ye-Ji, Kim, You Hwan, Yoon, Ji-Young, Shin, Jonghyun, Ok, Soo-Min, Kim, Eun-Jung, Choi, Eun Jung, and Oh, Jin-Woo
- Published
- 2023
- Full Text
- View/download PDF
43. Hyperammonemia induces microglial NLRP3 inflammasome activation via mitochondrial oxidative stress in hepatic encephalopathy
- Author
-
Cheon, So Yeong, Kim, Min-Yu, Kim, Jeongmin, Kim, Eun Jung, Kam, Eun Hee, Cho, Inja, Koo, Bon-Nyeo, and Kim, So Yeon
- Published
- 2023
- Full Text
- View/download PDF
44. Study on the characteristics of functionally graded materials from Ni-20cr to Ti-6Al-4V via directed energy deposition
- Author
-
Kim, Eun-Jung, Lee, Choon-Man, and Kim, Dong-Hyeon
- Published
- 2023
- Full Text
- View/download PDF
45. Grundy Coloring and Friends, Half-Graphs, Bicliques
- Author
-
Aboulker, Pierre, Bonnet, Édouard, Kim, Eun Jung, and Sikora, Florian
- Published
- 2023
- Full Text
- View/download PDF
46. Twin-width and Polynomial Kernels
- Author
-
Bonnet, Édouard, Kim, Eun Jung, Reinald, Amadeus, Thomassé, Stéphan, and Watrigant, Rémi
- Published
- 2022
- Full Text
- View/download PDF
47. Remote Control: A Simple Deadlock Avoidance Scheme for Modular System on Chip
- Author
-
Majumder, Pritam, Kim, Sungkeun, Huang, Jiayi, Yum, Ki Hwan, and Kim, Eun Jung
- Subjects
Computer Science - Hardware Architecture ,Computer Science - Networking and Internet Architecture - Abstract
The increase in design cost and complexity have motivated designers to adopt modular design of System on Chip (SoC) by integrating independently designed small chiplets. However, it introduces new challenges for correctness validation, increasing chances of forming deadlock in the system involving multiple chiplets. Although there have been many solutions available for deadlock freedom in flat networks, the study on deadlock issue in chiplet-based systems is still in its infancy. A recent study suggests adding extra turn restrictions as a viable solution for this problem. However, imposing extra turn restrictions reduces chiplet design flexibility and interposer design complexity. In addition, it may lead to non-minimal route and traffic imbalance forming hotspots, resulting in high latency and low throughput. We propose Remote Control (RC), a simple routing oblivious deadlock avoidance scheme. Our proposal is based on two key observations. First, packets with destinations in the current chiplet are blocked by packets with destinations outside the chiplet. Second, deadlock always involves multiple boundary routers. Hence, we segregate different traffics to alleviate mutual blocking at the chiplet's boundary routers. Along with guarantee of deadlock freedom and performance enhancements, our simple RC scheme also provides more routing flexibility to both chiplet and SoC designers, as compared to the state-of-the-art.
- Published
- 2019
48. Lidocaine intensifies the anti-osteogenic effect on inflammation-induced human dental pulp stem cells via mitogen-activated protein kinase inhibition
- Author
-
Lee, Sang-Hoon, Kim, Cheul-Hong, Yoon, Ji-Young, Choi, Eun-Ji, Kim, Mi Kyoung, Yoon, Ji-Uk, Kim, Hee Young, and Kim, Eun-Jung
- Published
- 2023
- Full Text
- View/download PDF
49. New Results on Directed Edge Dominating Set
- Author
-
Belmonte, Rémy, Hanaka, Tesshu, Katsikarelis, Ioannis, Kim, Eun Jung, and Lampis, Michael
- Subjects
Computer Science - Computational Complexity ,Computer Science - Data Structures and Algorithms - 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 by $tw$ (even if the size of the optimal is added as a second parameter), 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.
- Published
- 2019
- Full Text
- View/download PDF
50. Obstructions for matroids of path-width at most k and graphs of linear rank-width at most k
- Author
-
Kanté, Mamadou Moustapha, Kim, Eun Jung, Kwon, O-joung, and Oum, Sang-il
- Published
- 2023
- Full Text
- View/download PDF
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.