8 Search Results for "Le, Van Bang"

Document
DOI: 10.4230/LIPIcs.ISAAC.2023.31
Matching Cuts in Graphs of High Girth and H-Free Graphs

Authors: Carl Feghali, Felicia Lucke, Daniël Paulusma, and Bernard Ries

Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)

Abstract
The (Perfect) Matching Cut problem is to decide if a connected graph has a (perfect) matching that is also an edge cut. The Disconnected Perfect Matching problem is to decide if a connected graph has a perfect matching that contains a matching cut. Both Matching Cut and Disconnected Perfect Matching are NP-complete for planar graphs of girth 5, whereas Perfect Matching Cut is known to be NP-complete even for subcubic bipartite graphs of arbitrarily large fixed girth. We prove that Matching Cut and Disconnected Perfect Matching are also NP-complete for bipartite graphs of arbitrarily large fixed girth and bounded maximum degree. Our result for Matching Cut resolves a 20-year old open problem. We also show that the more general problem d-Cut, for every fixed d ≥ 1, is NP-complete for bipartite graphs of arbitrarily large fixed girth and bounded maximum degree. Furthermore, we show that Matching Cut, Perfect Matching Cut and Disconnected Perfect Matching are NP-complete for H-free graphs whenever H contains a connected component with two vertices of degree at least 3. Afterwards, we update the state-of-the-art summaries for H-free graphs and compare them with each other, and with a known and full classification of the Maximum Matching Cut problem, which is to determine a largest matching cut of a graph G. Finally, by combining existing results, we obtain a complete complexity classification of Perfect Matching Cut for H-subgraph-free graphs where H is any finite set of graphs.
Cite as

Carl Feghali, Felicia Lucke, Daniël Paulusma, and Bernard Ries. Matching Cuts in Graphs of High Girth and H-Free Graphs. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 31:1-31:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{feghali_et_al:LIPIcs.ISAAC.2023.31,
  author =	{Feghali, Carl and Lucke, Felicia and Paulusma, Dani\"{e}l and Ries, Bernard},
  title =	{{Matching Cuts in Graphs of High Girth and H-Free Graphs}},
  booktitle =	{34th International Symposium on Algorithms and Computation (ISAAC 2023)},
  pages =	{31:1--31:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-289-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{283},
  editor =	{Iwata, Satoru and Kakimura, Naonori},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.31},
  URN =		{urn:nbn:de:0030-drops-193332},
  doi =		{10.4230/LIPIcs.ISAAC.2023.31},
  annote =	{Keywords: matching cut, perfect matching, girth, H-free graph}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2022.68
Complexity of the Cluster Vertex Deletion Problem on H-Free Graphs

Authors: Hoang-Oanh Le and Van Bang Le

Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)

Abstract
The well-known Cluster Vertex Deletion problem (cluster-vd) asks for a given graph G and an integer k whether it is possible to delete at most k vertices of G such that the resulting graph is a cluster graph (a disjoint union of cliques). We give a complete characterization of graphs H for which cluster-vd on H-free graphs is polynomially solvable and for which it is NP-complete.
Cite as

Hoang-Oanh Le and Van Bang Le. Complexity of the Cluster Vertex Deletion Problem on H-Free Graphs. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 68:1-68:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{le_et_al:LIPIcs.MFCS.2022.68,
  author =	{Le, Hoang-Oanh and Le, Van Bang},
  title =	{{Complexity of the Cluster Vertex Deletion Problem on H-Free Graphs}},
  booktitle =	{47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
  pages =	{68:1--68:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-256-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{241},
  editor =	{Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.68},
  URN =		{urn:nbn:de:0030-drops-168663},
  doi =		{10.4230/LIPIcs.MFCS.2022.68},
  annote =	{Keywords: Cluster vertex deletion, Vertex cover, Computational complexity, Complexity dichotomy}
}
Document
DOI: 10.4230/LIPIcs.STACS.2021.37
Refined Notions of Parameterized Enumeration Kernels with Applications to Matching Cut Enumeration

Authors: Petr A. Golovach, Christian Komusiewicz, Dieter Kratsch, and Van Bang Le

Published in: LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)

Abstract
An enumeration kernel as defined by Creignou et al. [Theory Comput. Syst. 2017] for a parameterized enumeration problem consists of an algorithm that transforms each instance into one whose size is bounded by the parameter plus a solution-lifting algorithm that efficiently enumerates all solutions from the set of the solutions of the kernel. We propose to consider two new versions of enumeration kernels by asking that the solutions of the original instance can be enumerated in polynomial time or with polynomial delay from the kernel solutions. Using the NP-hard Matching Cut problem parameterized by structural parameters such as the vertex cover number or the cyclomatic number of the input graph, we show that the new enumeration kernels present a useful notion of data reduction for enumeration problems which allows to compactly represent the set of feasible solutions.
Cite as

Petr A. Golovach, Christian Komusiewicz, Dieter Kratsch, and Van Bang Le. Refined Notions of Parameterized Enumeration Kernels with Applications to Matching Cut Enumeration. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 37:1-37:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{golovach_et_al:LIPIcs.STACS.2021.37,
  author =	{Golovach, Petr A. and Komusiewicz, Christian and Kratsch, Dieter and Le, Van Bang},
  title =	{{Refined Notions of Parameterized Enumeration Kernels with Applications to Matching Cut Enumeration}},
  booktitle =	{38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)},
  pages =	{37:1--37:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-180-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{187},
  editor =	{Bl\"{a}ser, Markus and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021.37},
  URN =		{urn:nbn:de:0030-drops-136823},
  doi =		{10.4230/LIPIcs.STACS.2021.37},
  annote =	{Keywords: enumeration problems, polynomial delay, output-sensitive algorithms, kernelization, structural parameterizations, matching cuts}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2019.13
Constrained Representations of Map Graphs and Half-Squares

Authors: Hoang-Oanh Le and Van Bang Le

Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)

Abstract
The square of a graph H, denoted H^2, is obtained from H by adding new edges between two distinct vertices whenever their distance in H is two. The half-squares of a bipartite graph B=(X,Y,E_B) are the subgraphs of B^2 induced by the color classes X and Y, B^2[X] and B^2[Y]. For a given graph G=(V,E_G), if G=B^2[V] for some bipartite graph B=(V,W,E_B), then B is a representation of G and W is the set of points in B. If in addition B is planar, then G is also called a map graph and B is a witness of G [Chen, Grigni, Papadimitriou. Map graphs. J. ACM , 49 (2) (2002) 127-138]. While Chen, Grigni, Papadimitriou proved that any map graph G=(V,E_G) has a witness with at most 3|V|-6 points, we show that, given a map graph G and an integer k, deciding if G admits a witness with at most k points is NP-complete. As a by-product, we obtain NP-completeness of edge clique partition on planar graphs; until this present paper, the complexity status of edge clique partition for planar graphs was previously unknown. We also consider half-squares of tree-convex bipartite graphs and prove the following complexity dichotomy: Given a graph G=(V,E_G) and an integer k, deciding if G=B^2[V] for some tree-convex bipartite graph B=(V,W,E_B) with |W|<=k points is NP-complete if G is non-chordal dually chordal and solvable in linear time otherwise. Our proof relies on a characterization of half-squares of tree-convex bipartite graphs, saying that these are precisely the chordal and dually chordal graphs.
Cite as

Hoang-Oanh Le and Van Bang Le. Constrained Representations of Map Graphs and Half-Squares. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 13:1-13:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{le_et_al:LIPIcs.MFCS.2019.13,
  author =	{Le, Hoang-Oanh and Le, Van Bang},
  title =	{{Constrained Representations of Map Graphs and Half-Squares}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{13:1--13:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-117-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{138},
  editor =	{Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.13},
  URN =		{urn:nbn:de:0030-drops-109574},
  doi =		{10.4230/LIPIcs.MFCS.2019.13},
  annote =	{Keywords: map graph, half-square, edge clique cover, edge clique partition, graph classes}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2018.19
Matching Cut: Kernelization, Single-Exponential Time FPT, and Exact Exponential Algorithms

Authors: Christian Komusiewicz, Dieter Kratsch, and Van Bang Le

Published in: LIPIcs, Volume 115, 13th International Symposium on Parameterized and Exact Computation (IPEC 2018)

Abstract
In a graph, a matching cut is an edge cut that is a matching. Matching Cut, which is known to be NP-complete, is the problem of deciding whether or not a given graph G has a matching cut. In this paper we show that Matching Cut admits a quadratic-vertex kernel for the parameter distance to cluster and a linear-vertex kernel for the parameter distance to clique. We further provide an O^*(2^{dc(G)}) time and an O^*(2^{dc^-}(G)}) time FPT algorithm for Matching Cut, where dc(G) and dc^-(G) are the distance to cluster and distance to co-cluster, respectively. We also improve the running time of the best known branching algorithm to solve Matching Cut from O^*(1.4143^n) to O^*(1.3803^n). Moreover, we point out that, unless NP subseteq coNP/poly, Matching Cut does not admit a polynomial kernel when parameterized by treewidth.
Cite as

Christian Komusiewicz, Dieter Kratsch, and Van Bang Le. Matching Cut: Kernelization, Single-Exponential Time FPT, and Exact Exponential Algorithms. In 13th International Symposium on Parameterized and Exact Computation (IPEC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 115, pp. 19:1-19:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{komusiewicz_et_al:LIPIcs.IPEC.2018.19,
  author =	{Komusiewicz, Christian and Kratsch, Dieter and Le, Van Bang},
  title =	{{Matching Cut: Kernelization, Single-Exponential Time FPT, and Exact Exponential Algorithms}},
  booktitle =	{13th International Symposium on Parameterized and Exact Computation (IPEC 2018)},
  pages =	{19:1--19:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-084-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{115},
  editor =	{Paul, Christophe and Pilipczuk, Michal},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2018.19},
  URN =		{urn:nbn:de:0030-drops-102207},
  doi =		{10.4230/LIPIcs.IPEC.2018.19},
  annote =	{Keywords: matching cut, decomposable graph, graph algorithm}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2016.50
On the Complexity of Matching Cut in Graphs of Fixed Diameter

Authors: Hoang-Oanh Le and Van Bang Le

Published in: LIPIcs, Volume 64, 27th International Symposium on Algorithms and Computation (ISAAC 2016)

Abstract
In a graph, a matching cut is an edge cut that is a matching. Matching Cut is the problem of deciding whether or not a given graph has a matching cut, which is known to be NP-complete even when restricted to bipartite graphs. It has been proved that Matching Cut is polynomially solvable for graphs of diameter two. In this paper, we show that, for any fixed integer d geq 4, Matching Cut is NP-complete in the class of graphs of diameter d. This almost resolves an open problem posed by Borowiecki and Jesse-Józefczyk in [Matching cutsets in graphs of diameter 2, Theoretical Computer Science 407 (2008) 574-582]. We then show that, for any fixed integer d geq 5, Matching Cut is NP-complete even when restricted to the class of bipartite graphs of diameter d. Complementing the hardness results, we show that Matching Cut is in polynomial-time solvable in the class of bipartite graphs of diameter at most three, and point out a new and simple polynomial-time algorithm solving Matching Cut in graphs of diameter 2.
Cite as

Hoang-Oanh Le and Van Bang Le. On the Complexity of Matching Cut in Graphs of Fixed Diameter. In 27th International Symposium on Algorithms and Computation (ISAAC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 64, pp. 50:1-50:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{le_et_al:LIPIcs.ISAAC.2016.50,
  author =	{Le, Hoang-Oanh and Le, Van Bang},
  title =	{{On the Complexity of Matching Cut in Graphs of Fixed Diameter}},
  booktitle =	{27th International Symposium on Algorithms and Computation (ISAAC 2016)},
  pages =	{50:1--50:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-026-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{64},
  editor =	{Hong, Seok-Hee},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2016.50},
  URN =		{urn:nbn:de:0030-drops-68205},
  doi =		{10.4230/LIPIcs.ISAAC.2016.50},
  annote =	{Keywords: matching cut, NP-hardness, graph algorithm, computational complexity, decomposable graph}
}
Document
DOI: 10.4230/LIPIcs.STACS.2009.1827
Computing Graph Roots Without Short Cycles

Authors: Babak Farzad, Lap Chi Lau, Van Bang Le, and Nguyen Ngoc Tuy

Published in: LIPIcs, Volume 3, 26th International Symposium on Theoretical Aspects of Computer Science (2009)

Abstract
Graph $G$ is the square of graph $H$ if two vertices $x,y$ have an edge in $G$ if and only if $x,y$ are of distance at most two in $H$. Given $H$ it is easy to compute its square $H^2$, however Motwani and Sudan proved that it is NP-complete to determine if a given graph $G$ is the square of some graph $H$ (of girth $3$). In this paper we consider the characterization and recognition problems of graphs that are squares of graphs of small girth, i.e. to determine if $G=H^2$ for some graph $H$ of small girth. The main results are the following. \begin{itemize} \item There is a graph theoretical characterization for graphs that are squares of some graph of girth at least $7$. A corollary is that if a graph $G$ has a square root $H$ of girth at least $7$ then $H$ is unique up to isomorphism. \item There is a polynomial time algorithm to recognize if $G=H^2$ for some graph $H$ of girth at least $6$. \item It is NP-complete to recognize if $G=H^2$ for some graph $H$ of girth $4$. \end{itemize} These results almost provide a dichotomy theorem for the complexity of the recognition problem in terms of girth of the square roots. The algorithmic and graph theoretical results generalize previous results on tree square roots, and provide polynomial time algorithms to compute a graph square root of small girth if it exists. Some open questions and conjectures will also be discussed.
Cite as

Babak Farzad, Lap Chi Lau, Van Bang Le, and Nguyen Ngoc Tuy. Computing Graph Roots Without Short Cycles. In 26th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 3, pp. 397-408, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{farzad_et_al:LIPIcs.STACS.2009.1827,
  author =	{Farzad, Babak and Lau, Lap Chi and Le, Van Bang and Tuy, Nguyen Ngoc},
  title =	{{Computing Graph Roots Without Short Cycles}},
  booktitle =	{26th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{397--408},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-09-5},
  ISSN =	{1868-8969},
  year =	{2009},
  volume =	{3},
  editor =	{Albers, Susanne and Marion, Jean-Yves},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2009.1827},
  URN =		{urn:nbn:de:0030-drops-18279},
  doi =		{10.4230/LIPIcs.STACS.2009.1827},
  annote =	{Keywords: Graph roots, Graph powers, Recognition algorithms, NP-completeness}
}
Document
DOI: 10.4230/DagSemProc.07211.2
Linear-time certifying recognition for partitioned probe cographs

Authors: Van Bang Le and H.N. de Ridder

Published in: Dagstuhl Seminar Proceedings, Volume 7211, Exact, Approximative, Robust and Certifying Algorithms on Particular Graph Classes (2007)

Abstract
Cographs are those graphs without induced path on four vetices. A graph $G=(V, E)$ with a partition $V=Pcup N$ where $N$ is an independent set is a partitioned probe cograph if one can add new edges between certain vertices in $N$ in such a way that the graph obtained is a cograph. We characterize partitioned probe cographs in terms of five forbidden induced subgraphs. Using this characterization, we give a linear-time recognition algorithm for partitioned probe cographs. Our algorithm produces a certificate for membership that can be checked in linear time and a certificate for non-membership that can be checked in sublinear time.
Cite as

Van Bang Le and H.N. de Ridder. Linear-time certifying recognition for partitioned probe cographs. In Exact, Approximative, Robust and Certifying Algorithms on Particular Graph Classes. Dagstuhl Seminar Proceedings, Volume 7211, pp. 1-4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{le_et_al:DagSemProc.07211.2,
  author =	{Le, Van Bang and de Ridder, H.N.},
  title =	{{Linear-time certifying recognition for partitioned probe cographs}},
  booktitle =	{Exact, Approximative, Robust and Certifying Algorithms on Particular Graph Classes},
  pages =	{1--4},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{7211},
  editor =	{Andreas Brandst\"{a}dt and Klaus Jansen and Dieter Kratsch and Jeremy P. Spinrad},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.07211.2},
  URN =		{urn:nbn:de:0030-drops-12703},
  doi =		{10.4230/DagSemProc.07211.2},
  annote =	{Keywords: Cograph, probe cograph, certifying graph algorithm}
}
  • Refine by Author
  • 7 Le, Van Bang
  • 3 Le, Hoang-Oanh
  • 2 Komusiewicz, Christian
  • 2 Kratsch, Dieter
  • 1 Farzad, Babak
  • Show More...

  • Refine by Classification
  • 3 Mathematics of computing → Graph algorithms
  • 3 Mathematics of computing → Graph theory
  • 2 Theory of computation → Graph algorithms analysis
  • 2 Theory of computation → Parameterized complexity and exact algorithms

  • Refine by Keyword
  • 3 matching cut
  • 2 decomposable graph
  • 2 graph algorithm
  • 1 Cluster vertex deletion
  • 1 Cograph
  • Show More...

  • Refine by Type
  • 8 document

  • Refine by Publication Year
  • 2 2019
  • 1 2007
  • 1 2009
  • 1 2016
  • 1 2021
  • Show More...

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