8 Search Results for "Bliznets, Ivan"

Document
DOI: 10.4230/LIPIcs.FSTTCS.2025.43
A Finer View of the Parameterized Landscape of Labeled Graph Contractions

Authors: Yashaswini Mathur and Prafullkumar Tale

Published in: LIPIcs, Volume 360, 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025)

Abstract
We study the Labeled Contractibility problem, where the input consists of two vertex-labeled graphs G and H, and the goal is to determine whether H can be obtained from G via a sequence of edge contractions. Lafond and Marchand [WADS 2025] initiated the parameterized complexity study of this problem, showing it to be W[1]-hard when parameterized by the number k of allowed contractions. They also proved that the problem is fixed-parameter tractable when parameterized by the tree-width tw of G, via an application of Courcelle’s theorem resulting in a non-constructive algorithm. In this work, we present a constructive fixed-parameter algorithm for Labeled Contractibility with running time 2^{𝒪(tw²)} ⋅ |V(G)|^{𝒪(1)}. We also prove that unless the Exponential Time Hypothesis ({ETH}) fails, it does not admit an algorithm running in time 2^{o(tw²)} ⋅ |V(G)|^{𝒪(1)}. This result adds Labeled Contractibility to a small list of problems that admit such a lower bound and matching algorithm. We further strengthen existing hardness results by showing that the problem remains NP-complete even when both input graphs have bounded maximum degree. We also investigate parameterizations by (k + δ(G)) where δ(G) denotes the degeneracy of G, and rule out the existence of subexponential-time algorithms. This answers question raised in Lafond and Marchand [WADS 2025]. We additionally provide an improved FPT algorithm with better dependence on (k + δ(G)) than previously known. Finally, we analyze a brute-force algorithm for Labeled Contractibility with running time |V(H)|^{𝒪(|V(G)|)}, and show that this running time is optimal under {ETH}.
Cite as

Yashaswini Mathur and Prafullkumar Tale. A Finer View of the Parameterized Landscape of Labeled Graph Contractions. In 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 360, pp. 43:1-43:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{mathur_et_al:LIPIcs.FSTTCS.2025.43,
  author =	{Mathur, Yashaswini and Tale, Prafullkumar},
  title =	{{A Finer View of the Parameterized Landscape of Labeled Graph Contractions}},
  booktitle =	{45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025)},
  pages =	{43:1--43:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-406-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{360},
  editor =	{Aiswarya, C. and Mehta, Ruta and Roy, Subhajit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2025.43},
  URN =		{urn:nbn:de:0030-drops-251237},
  doi =		{10.4230/LIPIcs.FSTTCS.2025.43},
  annote =	{Keywords: Labeled Contraction, ETH Lower-bound, Treewidth, NP-hard}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2025.5
Graph Coloring Below Guarantees via Co-Triangle Packing

Authors: Shyan Akmal and Tomohiro Koana

Published in: LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025)

Abstract
In the 𝓁-Coloring problem, we are given a graph on n nodes, and tasked with determining if its vertices can be properly colored using 𝓁 colors. In this paper we study below-guarantee graph coloring, which tests whether an n-vertex graph can be properly colored using g-k colors, where g is a trivial upper bound such as n. We introduce an algorithmic framework that builds on a packing of co-triangles K₃ (independent sets of three vertices): the algorithm greedily finds co-triangles and employs a win-win analysis. If many are found, we immediately return yes; otherwise these co-triangles form a small co-triangle modulator, whose deletion makes the graph co-triangle-free. Extending the work of [Gutin et al., SIDMA 2021], who solved 𝓁-Coloring (for any 𝓁) in randomized O^∗(2^k) time when given a K₂-free modulator of size k, we show that this problem can likewise be solved in randomized O^*(2^{k}) time when given a K₃-free modulator of size k. This result in turn yields a randomized O^*(2^{3k/2}) algorithm for (n-k)-Coloring (also known as Dual Coloring), improving the previous O^*(4^k) bound. We then introduce a smaller parameterization, (ω+μ-k)-Coloring, where ω is the clique number and μ is the size of a maximum matching in the complement graph; since ω+μ ≤ n for any graph, this problem is strictly harder. Using the same co-triangle-packing argument, we obtain a randomized O^*(2^{6k}) algorithm, establishing its fixed-parameter tractability for a smaller parameter. Complementing this finding, we show that no fixed-parameter tractable algorithm exists for (ω-k)-Coloring or (μ-k)-Coloring under standard complexity assumptions.
Cite as

Shyan Akmal and Tomohiro Koana. Graph Coloring Below Guarantees via Co-Triangle Packing. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 5:1-5:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{akmal_et_al:LIPIcs.ISAAC.2025.5,
  author =	{Akmal, Shyan and Koana, Tomohiro},
  title =	{{Graph Coloring Below Guarantees via Co-Triangle Packing}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{5:1--5:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-408-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{359},
  editor =	{Chen, Ho-Lin and Hon, Wing-Kai and Tsai, Meng-Tsung},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.5},
  URN =		{urn:nbn:de:0030-drops-249130},
  doi =		{10.4230/LIPIcs.ISAAC.2025.5},
  annote =	{Keywords: coloring, parameterized algorithms, algebraic algorithms, above-guarantee, below-guarantee, subset convolution, determinants}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2025.51
Parameterized Geometric Graph Modification with Disk Scaling

Authors: Fedor V. Fomin, Petr A. Golovach, Tanmay Inamdar, Saket Saurabh, and Meirav Zehavi

Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)

Abstract
The parameterized analysis of graph modification problems represents the most extensively studied area within Parameterized Complexity. Given a graph G and an integer k ∈ ℕ as input, the goal is to determine whether we can perform at most k operations on G to transform it into a graph belonging to a specified graph class ℱ. Typical operations are combinatorial and include vertex deletions and edge deletions, insertions, and contractions. However, in many real-world scenarios, when the input graph is constrained to be a geometric intersection graph, the modification of the graph is influenced by changes in the geometric properties of the underlying objects themselves, rather than by combinatorial modifications. It raises the question of whether vertex deletions or adjacency modifications are necessarily the most appropriate modification operations for studying modifications of geometric graphs. We propose the study of the disk intersection graph modification through the scaling of disks. This operation is typical in the realm of topology control but has not yet been explored in the context of Parameterized Complexity. We design parameterized algorithms and kernels for modifying to the most basic graph classes: edgeless, connected, and acyclic. Our technical contributions encompass a novel combination of linear programming, branching, and kernelization techniques, along with a fresh application of bidimensionality theory to analyze the area covered by disks, which may have broader applicability.
Cite as

Fedor V. Fomin, Petr A. Golovach, Tanmay Inamdar, Saket Saurabh, and Meirav Zehavi. Parameterized Geometric Graph Modification with Disk Scaling. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 51:1-51:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{fomin_et_al:LIPIcs.ITCS.2025.51,
  author =	{Fomin, Fedor V. and Golovach, Petr A. and Inamdar, Tanmay and Saurabh, Saket and Zehavi, Meirav},
  title =	{{Parameterized Geometric Graph Modification with Disk Scaling}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{51:1--51:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-361-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{325},
  editor =	{Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.51},
  URN =		{urn:nbn:de:0030-drops-226795},
  doi =		{10.4230/LIPIcs.ITCS.2025.51},
  annote =	{Keywords: parameterized algorithms, kernelization, spreading points, distant representatives, unit disk packing}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2023.22
MaxCut Above Guarantee

Authors: Ivan Bliznets and Vladislav Epifanov

Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)

Abstract
In this paper, we study the computational complexity of the Maximum Cut problem parameterized above guarantee. Our main result provides a linear kernel for the Maximum Cut problem in connected graphs parameterized above the spanning tree. This kernel significantly improves the previous O(k⁵) kernel given by Madathil, Saurabh, and Zehavi [ToCS 2020]. We also provide subexponential running time algorithms for this problem in special classes of graphs: chordal, split, and co-bipartite. We complete the picture by lower bounds under the assumption of the ETH. Moreover, we initiate a study of the Maximum Cut problem above 2/3|E| lower bound in tripartite graphs.
Cite as

Ivan Bliznets and Vladislav Epifanov. MaxCut Above Guarantee. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 22:1-22:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{bliznets_et_al:LIPIcs.MFCS.2023.22,
  author =	{Bliznets, Ivan and Epifanov, Vladislav},
  title =	{{MaxCut Above Guarantee}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{22:1--22:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.22},
  URN =		{urn:nbn:de:0030-drops-185560},
  doi =		{10.4230/LIPIcs.MFCS.2023.22},
  annote =	{Keywords: Tripartite, 3-colorable, chordal, maximum cut, FPT-algorithm, linear kernel}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2022.24
Hardness of Approximation for H-Free Edge Modification Problems: Towards a Dichotomy

Authors: Tatiana Belova and Ivan Bliznets

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

Abstract
For a fixed graph H, the H-free Edge Deletion/Completion/Editing problem asks to delete/add/edit the minimum possible number of edges in G to get a graph that does not contain an induced subgraph isomorphic to the graph H. In this work, we investigate H-free Edge Deletion/Completion/Editing problems in terms of the hardness of their approximation. We formulate a conjecture according to which all the graphs with at least five vertices can be classified into several groups of graphs with specific structural properties depending on the hardness of approximation for the corresponding H-free Edge Deletion/Completion/Editing problems. Also, we make significant progress in proving that conjecture by showing that it is sufficient to resolve it only for a finite set of graphs.
Cite as

Tatiana Belova and Ivan Bliznets. Hardness of Approximation for H-Free Edge Modification Problems: Towards a Dichotomy. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 24:1-24:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{belova_et_al:LIPIcs.ISAAC.2022.24,
  author =	{Belova, Tatiana and Bliznets, Ivan},
  title =	{{Hardness of Approximation for H-Free Edge Modification Problems: Towards a Dichotomy}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{24:1--24:15},
  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.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.24},
  URN =		{urn:nbn:de:0030-drops-173097},
  doi =		{10.4230/LIPIcs.ISAAC.2022.24},
  annote =	{Keywords: Parameterized complexity, Hardness of approximation, Edge modification problems}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2018.22
Solving Target Set Selection with Bounded Thresholds Faster than 2^n

Authors: Ivan Bliznets and Danil Sagunov

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

Abstract
In this paper we consider the Target Set Selection problem. The problem naturally arises in many fields like economy, sociology, medicine. In the Target Set Selection problem one is given a graph G with a function thr: V(G) -> N cup {0} and integers k, l. The goal of the problem is to activate at most k vertices initially so that at the end of the activation process there is at least l activated vertices. The activation process occurs in the following way: (i) once activated, a vertex stays activated forever; (ii) vertex v becomes activated if at least thr(v) of its neighbours are activated. The problem and its different special cases were extensively studied from approximation and parameterized points of view. For example, parameterizations by the following parameters were studied: treewidth, feedback vertex set, diameter, size of target set, vertex cover, cluster editing number and others. Despite the extensive study of the problem it is still unknown whether the problem can be solved in O^*((2-epsilon)^n) time for some epsilon >0. We partially answer this question by presenting several faster-than-trivial algorithms that work in cases of constant thresholds, constant dual thresholds or when the threshold value of each vertex is bounded by one-third of its degree. Also, we show that the problem parameterized by l is W[1]-hard even when all thresholds are constant.
Cite as

Ivan Bliznets and Danil Sagunov. Solving Target Set Selection with Bounded Thresholds Faster than 2^n. In 13th International Symposium on Parameterized and Exact Computation (IPEC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 115, pp. 22:1-22:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{bliznets_et_al:LIPIcs.IPEC.2018.22,
  author =	{Bliznets, Ivan and Sagunov, Danil},
  title =	{{Solving Target Set Selection with Bounded Thresholds Faster than 2^n}},
  booktitle =	{13th International Symposium on Parameterized and Exact Computation (IPEC 2018)},
  pages =	{22:1--22:14},
  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.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2018.22},
  URN =		{urn:nbn:de:0030-drops-102235},
  doi =		{10.4230/LIPIcs.IPEC.2018.22},
  annote =	{Keywords: exact exponential algorithms, target set, vertex thresholds, social influence, irreversible conversions of graphs, bootstrap percolation}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2017.6
Parameterized Algorithms for Partitioning Graphs into Highly Connected Clusters

Authors: Ivan Bliznets and Nikolai Karpov

Published in: LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)

Abstract
Clustering is a well-known and important problem with numerous applications. The graph-based model is one of the typical cluster models. In the graph model generally clusters are defined as cliques. However, such approach might be too restrictive as in some applications, not all objects from the same cluster must be connected. That is why different types of cliques relaxations often considered as clusters. In our work, we consider a problem of partitioning graph into clusters and a problem of isolating cluster of a special type where by cluster we mean highly connected subgraph. Initially, such clusterization was proposed by Hartuv and Shamir. And their HCS clustering algorithm was extensively applied in practice. It was used to cluster cDNA fingerprints, to find complexes in protein-protein interaction data, to group protein sequences hierarchically into superfamily and family clusters, to find families of regulatory RNA structures. The HCS algorithm partitions graph in highly connected subgraphs. However, it is achieved by deletion of not necessarily the minimum number of edges. In our work, we try to minimize the number of edge deletions. We consider problems from the parameterized point of view where the main parameter is a number of allowed edge deletions. The presented algorithms significantly improve previous known running times for the Highly Connected Deletion (improved from \cOs\left(81^k\right) to \cOs\left(3^k\right)), Isolated Highly Connected Subgraph (from \cOs(4^k) to \cOs\left(k^{\cO\left(k^{\sfrac{2}{3}}\right)}\right) ), Seeded Highly Connected Edge Deletion (from \cOs\left(16^{k^{\sfrac{3}{4}}}\right) to \cOs\left(k^{\sqrt{k}}\right)) problems. Furthermore, we present a subexponential algorithm for Highly Connected Deletion problem if the number of clusters is bounded. Overall our work contains three subexponential algorithms which is unusual as very recently there were known very few problems admitting subexponential algorithms.
Cite as

Ivan Bliznets and Nikolai Karpov. Parameterized Algorithms for Partitioning Graphs into Highly Connected Clusters. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 6:1-6:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{bliznets_et_al:LIPIcs.MFCS.2017.6,
  author =	{Bliznets, Ivan and Karpov, Nikolai},
  title =	{{Parameterized Algorithms for Partitioning Graphs into Highly Connected Clusters}},
  booktitle =	{42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)},
  pages =	{6:1--6:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-046-0},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{83},
  editor =	{Larsen, Kim G. and Bodlaender, Hans L. and Raskin, Jean-Francois},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.6},
  URN =		{urn:nbn:de:0030-drops-80728},
  doi =		{10.4230/LIPIcs.MFCS.2017.6},
  annote =	{Keywords: clustering, parameterized complexity, highly connected}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2016.3
Hardness of Approximation for H-Free Edge Modification Problems

Authors: Ivan Bliznets, Marek Cygan, Pawel Komosa, and Michal Pilipczuk

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

Abstract
The H-free Edge Deletion problem asks, for a given graph G and integer k, whether it is possible to delete at most k edges from G to make it H-free, that is, not containing H as an induced subgraph. The H-free Edge Completion problem is defined similarly, but we add edges instead of deleting them. The study of these two problem families has recently been the subject of intensive studies from the point of view of parameterized complexity and kernelization. In particular, it was shown that the problems do not admit polynomial kernels (under plausible complexity assumptions) for almost all graphs H, with several important exceptions occurring when the class of H-free graphs exhibits some structural properties. In this work we complement the parameterized study of edge modification problems to H-free graphs by considering their approximability. We prove that whenever H is 3-connected and has at least two non-edges, then both H-free Edge Deletion and H-free Edge Completion are very hard to approximate: they do not admit poly(OPT)-approximation in polynomial time, unless P=NP, or even in time subexponential in OPT, unless the Exponential Time Hypothesis fails. The assumption of the existence of two non-edges appears to be important: we show that whenever H is a complete graph without one edge, then H-free Edge Deletion is tightly connected to the \minhorn problem, whose approximability is still open. Finally, in an attempt to extend our hardness results beyond 3-connected graphs, we consider the cases of H being a path or a cycle, and we achieve an almost complete dichotomy there.
Cite as

Ivan Bliznets, Marek Cygan, Pawel Komosa, and Michal Pilipczuk. Hardness of Approximation for H-Free Edge Modification Problems. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 60, pp. 3:1-3:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{bliznets_et_al:LIPIcs.APPROX-RANDOM.2016.3,
  author =	{Bliznets, Ivan and Cygan, Marek and Komosa, Pawel and Pilipczuk, Michal},
  title =	{{Hardness of Approximation for H-Free Edge Modification Problems}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)},
  pages =	{3:1--3:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-018-7},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{60},
  editor =	{Jansen, Klaus and Mathieu, Claire and Rolim, Jos\'{e} D. P. and Umans, Chris},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2016.3},
  URN =		{urn:nbn:de:0030-drops-66260},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2016.3},
  annote =	{Keywords: hardness of approximation, parameterized complexity, kernelization, edge modification problems}
}
  • Refine by Type
  • 8 Document/PDF
  • 3 Document/HTML

  • Refine by Publication Year
  • 3 2025
  • 1 2023
  • 1 2022
  • 1 2019
  • 1 2017
  • Show More...

  • Refine by Author
  • 5 Bliznets, Ivan
  • 1 Akmal, Shyan
  • 1 Belova, Tatiana
  • 1 Cygan, Marek
  • 1 Epifanov, Vladislav
  • Show More...

  • Refine by Series/Journal
  • 8 LIPIcs

  • Refine by Classification
  • 3 Theory of computation → Fixed parameter tractability
  • 3 Theory of computation → Graph algorithms analysis
  • 3 Theory of computation → Parameterized complexity and exact algorithms
  • 1 Theory of computation → Branch-and-bound
  • 1 Theory of computation → Packing and covering problems

  • Refine by Keyword
  • 2 kernelization
  • 2 parameterized algorithms
  • 2 parameterized complexity
  • 1 3-colorable
  • 1 ETH Lower-bound
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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