41 Search Results for "Guo, Jiong"


Volume

LIPIcs, Volume 63

11th International Symposium on Parameterized and Exact Computation (IPEC 2016)

IPEC 2016, August 24-26, 2016, Aarhus, Denmark

Editors: Jiong Guo and Danny Hermelin

Document
Parameterized Approximation Algorithms for TSP

Authors: Jianqi Zhou, Peihua Li, and Jiong Guo

Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)


Abstract
We study the Traveling Salesman problem (TSP), where given a complete undirected graph G = (V,E) with n vertices and an edge cost function c:E↦R_{⩾0}, the goal is to find a minimum-cost cycle visiting every vertex exactly once. It is well-known that unless P = NP, TSP cannot be approximated in polynomial time within a factor of ρ(n) for any computable function ρ, while the metric case of TSP, that the edge cost function satisfies the △-inequality, admits a polynomial-time 1.5-approximation. We investigate TSP on general graphs from the perspective of parameterized approximability. A parameterized ρ-approximation algorithm returns a ρ-approximation solution in f(k)⋅|I|^O(1) time, where f is a computable function and k is a parameter of the input I. We introduce two parameters, which measure the distance of a given TSP-instance from the metric case, and achieve the following two results: - A 3-approximation algorithm for TSP in O((3k₁)! 8^k₁⋅ n²+n³) time, where k₁ is the number of triangles in which the edge costs violate the △-inequality. - A 3-approximation algorithm for TSP in O(n^O(k₂)) time and a (6k₂+9)-approximation algorithm for TSP in O(k₂^O(k₂)⋅n³) time, where k₂ is the minimum number of vertices, whose removal results in a metric graph. To our best knowledge, the above algorithms are the first non-trivial parameterized approximation algorithms for TSP on general graphs.

Cite as

Jianqi Zhou, Peihua Li, and Jiong Guo. Parameterized Approximation Algorithms for TSP. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 50:1-50:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{zhou_et_al:LIPIcs.ISAAC.2022.50,
  author =	{Zhou, Jianqi and Li, Peihua and Guo, Jiong},
  title =	{{Parameterized Approximation Algorithms for TSP}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{50:1--50:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-258-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{248},
  editor =	{Bae, Sang Won and Park, Heejin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.50},
  URN =		{urn:nbn:de:0030-drops-173358},
  doi =		{10.4230/LIPIcs.ISAAC.2022.50},
  annote =	{Keywords: FPT-approximation algorithms, the Traveling Salesman problem, the triangle inequality, fixed-parameter tractability, metric graphs}
}
Document
A Cubic Vertex-Kernel for Trivially Perfect Editing

Authors: Maël Dumas, Anthony Perez, and Ioan Todinca

Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)


Abstract
We consider the Trivially Perfect Editing problem, where one is given an undirected graph G = (V,E) and a parameter k ∈ ℕ and seeks to edit (add or delete) at most k edges from G to obtain a trivially perfect graph. The related Trivially Perfect Completion and Trivially Perfect Deletion problems are obtained by only allowing edge additions or edge deletions, respectively. Trivially perfect graphs are both chordal and cographs, and have applications related to the tree-depth width parameter and to social network analysis. All variants of the problem are known to be NP-complete [Burzyn et al., 2006; James Nastos and Yong Gao, 2013] and to admit so-called polynomial kernels [Pål Grønås Drange and Michał Pilipczuk, 2018; Jiong Guo, 2007]. More precisely, the existence of an O(k³) vertex-kernel for Trivially Perfect Completion was announced by Guo [Jiong Guo, 2007] but without a stand-alone proof. More recently, Drange and Pilipczuk [Pål Grønås Drange and Michał Pilipczuk, 2018] provided O(k⁷) vertex-kernels for these problems and left open the existence of cubic vertex-kernels. In this work, we answer positively to this question for all three variants of the problem.

Cite as

Maël Dumas, Anthony Perez, and Ioan Todinca. A Cubic Vertex-Kernel for Trivially Perfect Editing. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 45:1-45:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{dumas_et_al:LIPIcs.MFCS.2021.45,
  author =	{Dumas, Ma\"{e}l and Perez, Anthony and Todinca, Ioan},
  title =	{{A Cubic Vertex-Kernel for Trivially Perfect Editing}},
  booktitle =	{46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
  pages =	{45:1--45:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-201-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{202},
  editor =	{Bonchi, Filippo and Puglisi, Simon J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.45},
  URN =		{urn:nbn:de:0030-drops-144851},
  doi =		{10.4230/LIPIcs.MFCS.2021.45},
  annote =	{Keywords: Parameterized complexity, kernelization algorithms, graph modification, trivially perfect graphs}
}
Document
A 2-Approximation Algorithm for the Complementary Maximal Strip Recovery Problem

Authors: Haitao Jiang, Jiong Guo, Daming Zhu, and Binhai Zhu

Published in: LIPIcs, Volume 128, 30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019)


Abstract
The Maximal Strip Recovery problem (MSR) and its complementary (CMSR) are well-studied NP-hard problems in computational genomics. The input of these dual problems are two signed permutations. The goal is to delete some gene markers from both permutations, such that, in the remaining permutations, each gene marker has at least one common neighbor. Equivalently, the resulting permutations could be partitioned into common strips of length at least two. Then MSR is to maximize the number of remaining genes, while the objective of CMSR is to delete the minimum number of gene markers. In this paper, we present a new approximation algorithm for the Complementary Maximal Strip Recovery (CMSR) problem. Our approximation factor is 2, improving the currently best 7/3-approximation algorithm. Although the improvement on the factor is not huge, the analysis is greatly simplified by a compensating method, commonly referred to as the non-oblivious local search technique. In such a method a substitution may not always increase the value of the current solution (it sometimes may even decrease the solution value), though it always improves the value of another function seemingly unrelated to the objective function.

Cite as

Haitao Jiang, Jiong Guo, Daming Zhu, and Binhai Zhu. A 2-Approximation Algorithm for the Complementary Maximal Strip Recovery Problem. In 30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 128, pp. 5:1-5:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{jiang_et_al:LIPIcs.CPM.2019.5,
  author =	{Jiang, Haitao and Guo, Jiong and Zhu, Daming and Zhu, Binhai},
  title =	{{A 2-Approximation Algorithm for the Complementary Maximal Strip Recovery Problem}},
  booktitle =	{30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019)},
  pages =	{5:1--5:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-103-0},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{128},
  editor =	{Pisanti, Nadia and P. Pissis, Solon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2019.5},
  URN =		{urn:nbn:de:0030-drops-104769},
  doi =		{10.4230/LIPIcs.CPM.2019.5},
  annote =	{Keywords: Maximal strip recovery, complementary maximal strip recovery, computational genomics, approximation algorithm, local search}
}
Document
Can a permutation be sorted by best short swaps?

Authors: Shu Zhang, Daming Zhu, Haitao Jiang, Jingjing Ma, Jiong Guo, and Haodi Feng

Published in: LIPIcs, Volume 105, 29th Annual Symposium on Combinatorial Pattern Matching (CPM 2018)


Abstract
A short swap switches two elements with at most one element caught between them. Sorting permutation by short swaps asks to find a shortest short swap sequence to transform a permutation into another. A short swap can eliminate at most three inversions. It is still open for whether a permutation can be sorted by short swaps each of which can eliminate three inversions. In this paper, we present a polynomial time algorithm to solve the problem, which can decide whether a permutation can be sorted by short swaps each of which can eliminate 3 inversions in O(n) time, and if so, sort the permutation by such short swaps in O(n^2) time, where n is the number of elements in the permutation. A short swap can cause the total length of two element vectors to decrease by at most 4. We further propose an algorithm to recognize a permutation which can be sorted by short swaps each of which can cause the element vector length sum to decrease by 4 in O(n) time, and if so, sort the permutation by such short swaps in O(n^2) time. This improves upon the O(n^2) algorithm proposed by Heath and Vergara to decide whether a permutation is so called lucky.

Cite as

Shu Zhang, Daming Zhu, Haitao Jiang, Jingjing Ma, Jiong Guo, and Haodi Feng. Can a permutation be sorted by best short swaps?. In 29th Annual Symposium on Combinatorial Pattern Matching (CPM 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 105, pp. 14:1-14:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{zhang_et_al:LIPIcs.CPM.2018.14,
  author =	{Zhang, Shu and Zhu, Daming and Jiang, Haitao and Ma, Jingjing and Guo, Jiong and Feng, Haodi},
  title =	{{Can a permutation be sorted by best short swaps?}},
  booktitle =	{29th Annual Symposium on Combinatorial Pattern Matching (CPM 2018)},
  pages =	{14:1--14:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-074-3},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{105},
  editor =	{Navarro, Gonzalo and Sankoff, David and Zhu, Binhai},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2018.14},
  URN =		{urn:nbn:de:0030-drops-86957},
  doi =		{10.4230/LIPIcs.CPM.2018.14},
  annote =	{Keywords: Algorithm, Complexity, Short Swap, Permutation, Reversal}
}
Document
Complete Volume
LIPIcs, Volume 63, IPEC'16, Complete Volume

Authors: Jiong Guo and Danny Hermelin

Published in: LIPIcs, Volume 63, 11th International Symposium on Parameterized and Exact Computation (IPEC 2016)


Abstract
LIPIcs, Volume 63, IPEC'16, Complete Volume

Cite as

11th International Symposium on Parameterized and Exact Computation (IPEC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 63, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@Proceedings{guo_et_al:LIPIcs.IPEC.2016,
  title =	{{LIPIcs, Volume 63, IPEC'16, Complete Volume}},
  booktitle =	{11th International Symposium on Parameterized and Exact Computation (IPEC 2016)},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-023-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{63},
  editor =	{Guo, Jiong and Hermelin, Danny},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2016},
  URN =		{urn:nbn:de:0030-drops-69572},
  doi =		{10.4230/LIPIcs.IPEC.2016},
  annote =	{Keywords: Complexity Measures and Classes, Analysis of Algorithms and Problem Complexity, Discrete Mathematics}
}
Document
Front Matter
Front Matter, Table of Contents, Preface, Program Committee, External Reviewers, List of Authors

Authors: Jiong Guo and Danny Hermelin

Published in: LIPIcs, Volume 63, 11th International Symposium on Parameterized and Exact Computation (IPEC 2016)


Abstract
Front Matter, Table of Contents, Preface, Program Committee, External Reviewers, List of Authors

Cite as

11th International Symposium on Parameterized and Exact Computation (IPEC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 63, pp. 0:i-0:xiv, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@InProceedings{guo_et_al:LIPIcs.IPEC.2016.0,
  author =	{Guo, Jiong and Hermelin, Danny},
  title =	{{Front Matter, Table of Contents, Preface, Program Committee, External Reviewers, List of Authors}},
  booktitle =	{11th International Symposium on Parameterized and Exact Computation (IPEC 2016)},
  pages =	{0:i--0:xiv},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-023-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{63},
  editor =	{Guo, Jiong and Hermelin, Danny},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2016.0},
  URN =		{urn:nbn:de:0030-drops-69180},
  doi =		{10.4230/LIPIcs.IPEC.2016.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Program Committee, External Reviewers, List of Authors}
}
Document
Invited Talk
Determinant Sums for Hamiltonicity (Invited Talk)

Authors: Andreas Björklund

Published in: LIPIcs, Volume 63, 11th International Symposium on Parameterized and Exact Computation (IPEC 2016)


Abstract
The best worst case guarantee algorithm to see if a graph has a Hamiltonian cycle, a closed tour visiting every vertex exactly once, for a long time was based on dynamic programming over all the vertex subsets of the graph. In this talk we will show some algebraic techniques that can be used to see if a graph has a Hamiltonian cycle much faster. These techniques utilize sums over determinants of matrices. In particular we will show how you can find out if an undirected graph has a Hamiltonian cycle much faster, but we will also talk about some partial results for the directed case and modular counting.

Cite as

Andreas Björklund. Determinant Sums for Hamiltonicity (Invited Talk). In 11th International Symposium on Parameterized and Exact Computation (IPEC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 63, p. 1:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@InProceedings{bjorklund:LIPIcs.IPEC.2016.1,
  author =	{Bj\"{o}rklund, Andreas},
  title =	{{Determinant Sums for Hamiltonicity}},
  booktitle =	{11th International Symposium on Parameterized and Exact Computation (IPEC 2016)},
  pages =	{1:1--1:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-023-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{63},
  editor =	{Guo, Jiong and Hermelin, Danny},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2016.1},
  URN =		{urn:nbn:de:0030-drops-69485},
  doi =		{10.4230/LIPIcs.IPEC.2016.1},
  annote =	{Keywords: Hamiltonian cycle, exact algorithms, matrix determinant, algebraic techniques}
}
Document
Improved Algorithms and Combinatorial Bounds for Independent Feedback Vertex Set

Authors: Akanksha Agrawal, Sushmita Gupta, Saket Saurabh, and Roohani Sharma

Published in: LIPIcs, Volume 63, 11th International Symposium on Parameterized and Exact Computation (IPEC 2016)


Abstract
In this paper we study the "independent" version of the classic Feedback Vertex Set problem in the realm of parameterized algorithms and moderately exponential time algorithms. More precisely, we study the Independent Feedback Vertex Set problem, where we are given an undirected graph G on n vertices and a positive integer k, and the objective is to check if there is an independent feedback vertex set of size at most k. A set S subseteq V(G) is called an independent feedback vertex set (ifvs) if S is an independent set and G\S is a forest. In this paper we design two deterministic exact algorithms for Independent Feedback Vertex Set with running times O*(4.1481^k) and O*(1.5981^n). In fact, the algorithm with O*(1.5981^n) running time finds the smallest sized ifvs, if an ifvs exists. Both the algorithms are based on interesting measures and improve the best known algorithms for the problem in their respective domains. In particular, the algorithm with running time O*(4.1481^k) is an improvement over the previous algorithm that ran in time O*(5^k). On the other hand, the algorithm with running time O*(1.5981^n) is the first moderately exponential time algorithm that improves over the naive algorithm that enumerates all the subsets of V(G). Additionally, we show that the number of minimal ifvses in any graph on n vertices is upper bounded by 1.7485^n.

Cite as

Akanksha Agrawal, Sushmita Gupta, Saket Saurabh, and Roohani Sharma. Improved Algorithms and Combinatorial Bounds for Independent Feedback Vertex Set. In 11th International Symposium on Parameterized and Exact Computation (IPEC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 63, pp. 2:1-2:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@InProceedings{agrawal_et_al:LIPIcs.IPEC.2016.2,
  author =	{Agrawal, Akanksha and Gupta, Sushmita and Saurabh, Saket and Sharma, Roohani},
  title =	{{Improved Algorithms and Combinatorial Bounds for Independent Feedback Vertex Set}},
  booktitle =	{11th International Symposium on Parameterized and Exact Computation (IPEC 2016)},
  pages =	{2:1--2:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-023-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{63},
  editor =	{Guo, Jiong and Hermelin, Danny},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2016.2},
  URN =		{urn:nbn:de:0030-drops-69400},
  doi =		{10.4230/LIPIcs.IPEC.2016.2},
  annote =	{Keywords: independent feedback vertex set, fixed parameter tractable, exact algorithm, enumeration}
}
Document
H-Free Graphs, Independent Sets, and Subexponential-Time Algorithms

Authors: Gábor Bacsó, Dániel Marx, and Zsolt Tuza

Published in: LIPIcs, Volume 63, 11th International Symposium on Parameterized and Exact Computation (IPEC 2016)


Abstract
It is an outstanding open question in algorithmic graph theory to determine the complexity of the MAXIMUM INDEPENDENT SET problem on P_t-free graphs, that is, on graphs not containing any induced path on t vertices. So far, polynomial-time algorithms are known only for t at most 5 [Lokshtanov et al., SODA 2014, 570-581, 2014]. Here we study the existence of subexponential-time algorithms for the problem: by generalizing an earlier result of Randerath and Schiermeyer for t=5 [Discrete App. Math., 158 (2010), 1041-1044], we show that for any t at least 5, there is an algorithm for MAXIMUM INDEPENDENT SET on P_t-free graphs whose running time is subexponential in the number of vertices. SCATTERED SET is the generalization of MAXIMUM INDEPENDENT SET where the vertices of the solution are required to be at distance at least $d$ from each other. We give a complete characterization of those graphs H for which SCATTERED SET on H-free graphs can be solved in time subexponential in the size of the input (that is, in the number of vertices plus the number of edges): * If every component of H is a path, then d-SCATTERED SET on H-free graphs with n vertices and m edges can be solved in time 2^{(n+m)^{1-O(1/|V(H)|)}}, even if d is part of the input. * Otherwise, assuming ETH, there is no 2^{o(n+m)} time algorithm for d-SCATTERED SET for any fixed d at least 3 on H-free graphs with n vertices and m edges.

Cite as

Gábor Bacsó, Dániel Marx, and Zsolt Tuza. H-Free Graphs, Independent Sets, and Subexponential-Time Algorithms. In 11th International Symposium on Parameterized and Exact Computation (IPEC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 63, pp. 3:1-3:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@InProceedings{bacso_et_al:LIPIcs.IPEC.2016.3,
  author =	{Bacs\'{o}, G\'{a}bor and Marx, D\'{a}niel and Tuza, Zsolt},
  title =	{{H-Free Graphs, Independent Sets, and Subexponential-Time Algorithms}},
  booktitle =	{11th International Symposium on Parameterized and Exact Computation (IPEC 2016)},
  pages =	{3:1--3:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-023-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{63},
  editor =	{Guo, Jiong and Hermelin, Danny},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2016.3},
  URN =		{urn:nbn:de:0030-drops-69397},
  doi =		{10.4230/LIPIcs.IPEC.2016.3},
  annote =	{Keywords: independent set, scattered set, subexponential algorithms, H-free graphs}
}
Document
Parallel Multivariate Meta-Theorems

Authors: Max Bannach and Till Tantau

Published in: LIPIcs, Volume 63, 11th International Symposium on Parameterized and Exact Computation (IPEC 2016)


Abstract
Fixed-parameter tractability is based on the observation that many hard problems become tractable even on large inputs as long as certain input parameters are small. Originally, "tractable" just meant "solvable in polynomial time," but especially modern hardware raises the question of whether we can also achieve "solvable in polylogarithmic parallel time." A framework for this study of parallel fixed-parameter tractability is available and a number of isolated algorithmic results have been obtained in recent years, but one of the unifying core tools of classical FPT theory has been missing: algorithmic meta-theorems. We establish two such theorems by giving new upper bounds on the circuit depth necessary to solve the model checking problem for monadic second-order logic, once parameterized by the tree width and the formula (this is a parallel version of Courcelle's Theorem) and once by the tree depth and the formula. For our proofs we refine the analysis of earlier algorithms, especially of Bodlaender's, but also need to add new ideas, especially in the context where the parallel runtime is bounded by a function of the parameter and does not depend on the length of the input.

Cite as

Max Bannach and Till Tantau. Parallel Multivariate Meta-Theorems. In 11th International Symposium on Parameterized and Exact Computation (IPEC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 63, pp. 4:1-4:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@InProceedings{bannach_et_al:LIPIcs.IPEC.2016.4,
  author =	{Bannach, Max and Tantau, Till},
  title =	{{Parallel Multivariate Meta-Theorems}},
  booktitle =	{11th International Symposium on Parameterized and Exact Computation (IPEC 2016)},
  pages =	{4:1--4:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-023-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{63},
  editor =	{Guo, Jiong and Hermelin, Danny},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2016.4},
  URN =		{urn:nbn:de:0030-drops-69227},
  doi =		{10.4230/LIPIcs.IPEC.2016.4},
  annote =	{Keywords: Parallel computation, FPT, meta-theorems, tree width, tree depth}
}
Document
Finding Secluded Places of Special Interest in Graphs

Authors: René van Bevern, Till Fluschnik, George B. Mertzios, Hendrik Molter, Manuel Sorge, and Ondrej Suchý

Published in: LIPIcs, Volume 63, 11th International Symposium on Parameterized and Exact Computation (IPEC 2016)


Abstract
Finding a vertex subset in a graph that satisfies a certain property is one of the most-studied topics in algorithmic graph theory. The focus herein is often on minimizing or maximizing the size of the solution, that is, the size of the desired vertex set. In several applications, however, we also want to limit the "exposure" of the solution to the rest of the graph. This is the case, for example, when the solution represents persons that ought to deal with sensitive information or a segregated community. In this work, we thus explore the (parameterized) complexity of finding such secluded vertex subsets for a wide variety of properties that they shall fulfill. More precisely, we study the constraint that the (open or closed) neighborhood of the solution shall be bounded by a parameter and the influence of this constraint on the complexity of minimizing separators, feedback vertex sets, F-free vertex deletion sets, dominating sets, and the maximization of independent sets.

Cite as

René van Bevern, Till Fluschnik, George B. Mertzios, Hendrik Molter, Manuel Sorge, and Ondrej Suchý. Finding Secluded Places of Special Interest in Graphs. In 11th International Symposium on Parameterized and Exact Computation (IPEC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 63, pp. 5:1-5:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@InProceedings{vanbevern_et_al:LIPIcs.IPEC.2016.5,
  author =	{van Bevern, Ren\'{e} and Fluschnik, Till and Mertzios, George B. and Molter, Hendrik and Sorge, Manuel and Such\'{y}, Ondrej},
  title =	{{Finding Secluded Places of Special Interest in Graphs}},
  booktitle =	{11th International Symposium on Parameterized and Exact Computation (IPEC 2016)},
  pages =	{5:1--5:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-023-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{63},
  editor =	{Guo, Jiong and Hermelin, Danny},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2016.5},
  URN =		{urn:nbn:de:0030-drops-69380},
  doi =		{10.4230/LIPIcs.IPEC.2016.5},
  annote =	{Keywords: Neighborhood, Feedback Vertex Set, Vertex Deletion, Separator, Dominating Set}
}
Document
The Parameterized Complexity of Dependency Detection in Relational Databases

Authors: Thomas Bläsius, Tobias Friedrich, and Martin Schirneck

Published in: LIPIcs, Volume 63, 11th International Symposium on Parameterized and Exact Computation (IPEC 2016)


Abstract
We study the parameterized complexity of classical problems that arise in the profiling of relational data. Namely, we characterize the complexity of detecting unique column combinations (candidate keys), functional dependencies, and inclusion dependencies with the solution size as parameter. While the discovery of uniques and functional dependencies, respectively, turns out to be W[2]-complete, the detection of inclusion dependencies is one of the first natural problems proven to be complete for the class W[3]. As a side effect, our reductions give insights into the complexity of enumerating all minimal unique column combinations or functional dependencies.

Cite as

Thomas Bläsius, Tobias Friedrich, and Martin Schirneck. The Parameterized Complexity of Dependency Detection in Relational Databases. In 11th International Symposium on Parameterized and Exact Computation (IPEC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 63, pp. 6:1-6:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@InProceedings{blasius_et_al:LIPIcs.IPEC.2016.6,
  author =	{Bl\"{a}sius, Thomas and Friedrich, Tobias and Schirneck, Martin},
  title =	{{The Parameterized Complexity of Dependency Detection in Relational Databases}},
  booktitle =	{11th International Symposium on Parameterized and Exact Computation (IPEC 2016)},
  pages =	{6:1--6:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-023-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{63},
  editor =	{Guo, Jiong and Hermelin, Danny},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2016.6},
  URN =		{urn:nbn:de:0030-drops-69202},
  doi =		{10.4230/LIPIcs.IPEC.2016.6},
  annote =	{Keywords: parameterized complexity, unique column combination, functional dependency, inclusion dependency, profiling relational data}
}
Document
A Faster Parameterized Algorithm for Pseudoforest Deletion

Authors: Hans L. Bodlaender, Hirotaka Ono, and Yota Otachi

Published in: LIPIcs, Volume 63, 11th International Symposium on Parameterized and Exact Computation (IPEC 2016)


Abstract
A pseudoforest is a graph where each connected component contains at most one cycle, or alternatively, a graph that can be turned into a forest by removing at most one edge from each connected component. In this paper, we show that the following problem can be solved in O(3^k n k^{O(1)}) time: given a graph G and an integer k, can we delete at most k vertices from G such that we obtain a pseudoforest? The result improves upon an earlier result by Philip et al. [MFCS 2015] who gave a (nonlinear) 7.56^k n^{O(1)}-time algorithm both in the exponential factor depending on k as well as in the polynomial factor depending on n.

Cite as

Hans L. Bodlaender, Hirotaka Ono, and Yota Otachi. A Faster Parameterized Algorithm for Pseudoforest Deletion. In 11th International Symposium on Parameterized and Exact Computation (IPEC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 63, pp. 7:1-7:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@InProceedings{bodlaender_et_al:LIPIcs.IPEC.2016.7,
  author =	{Bodlaender, Hans L. and Ono, Hirotaka and Otachi, Yota},
  title =	{{A Faster Parameterized Algorithm for Pseudoforest Deletion}},
  booktitle =	{11th International Symposium on Parameterized and Exact Computation (IPEC 2016)},
  pages =	{7:1--7:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-023-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{63},
  editor =	{Guo, Jiong and Hermelin, Danny},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2016.7},
  URN =		{urn:nbn:de:0030-drops-69246},
  doi =		{10.4230/LIPIcs.IPEC.2016.7},
  annote =	{Keywords: pseudoforest deletion, graph class, width parameter, parameterized complexity}
}
Document
Optimal Dynamic Program for r-Domination Problems over Tree Decompositions

Authors: Glencora Borradaile and Hung Le

Published in: LIPIcs, Volume 63, 11th International Symposium on Parameterized and Exact Computation (IPEC 2016)


Abstract
There has been recent progress in showing that the exponential dependence on treewidth in dynamic programming algorithms for solving NP-hard problems is optimal under the Strong Exponential Time Hypothesis (SETH). We extend this work to r-domination problems. In r-dominating set, one wishes to find a minimum subset S of vertices such that every vertex of G is within r hops of some vertex in S. In connected r-dominating set, one additionally requires that the set induces a connected subgraph of G. We give a O((2r+1)^tw n) time algorithm for r-dominating set and a randomized O((2r+2)^tw n^{O(1)}) time algorithm for connected r-dominating set in n-vertex graphs of treewidth tw. We show that the running time dependence on r and tw is the best possible under SETH. This adds to earlier observations that a "+1" in the denominator is required for connectivity constraints.

Cite as

Glencora Borradaile and Hung Le. Optimal Dynamic Program for r-Domination Problems over Tree Decompositions. In 11th International Symposium on Parameterized and Exact Computation (IPEC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 63, pp. 8:1-8:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@InProceedings{borradaile_et_al:LIPIcs.IPEC.2016.8,
  author =	{Borradaile, Glencora and Le, Hung},
  title =	{{Optimal Dynamic Program for r-Domination Problems over Tree Decompositions}},
  booktitle =	{11th International Symposium on Parameterized and Exact Computation (IPEC 2016)},
  pages =	{8:1--8:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-023-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{63},
  editor =	{Guo, Jiong and Hermelin, Danny},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2016.8},
  URN =		{urn:nbn:de:0030-drops-69199},
  doi =		{10.4230/LIPIcs.IPEC.2016.8},
  annote =	{Keywords: r-dominating set, Exponential Time Hypothesis, Dynamic Programming}
}
  • Refine by Author
  • 8 Guo, Jiong
  • 3 Saurabh, Saket
  • 2 Bodlaender, Hans L.
  • 2 Dell, Holger
  • 2 Fellows, Michael R.
  • Show More...

  • Refine by Classification
  • 1 Mathematics of computing
  • 1 Theory of computation → Approximation algorithms analysis
  • 1 Theory of computation → Design and analysis of algorithms
  • 1 Theory of computation → Graph algorithms analysis
  • 1 Theory of computation → Parameterized complexity and exact algorithms

  • Refine by Keyword
  • 6 fixed-parameter tractability
  • 4 parameterized complexity
  • 3 treewidth
  • 2 Dynamic Programming
  • 2 FPT
  • Show More...

  • Refine by Type
  • 40 document
  • 1 volume

  • Refine by Publication Year
  • 33 2017
  • 2 2009
  • 1 2012
  • 1 2013
  • 1 2018
  • 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