82 Search Results for "Fomin, Fedor V."


Document
Kernelizing Temporal Exploration Problems

Authors: Emmanuel Arrighi, Fedor V. Fomin, Petr A. Golovach, and Petra Wolf

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


Abstract
We study the kernelization of exploration problems on temporal graphs. A temporal graph consists of a finite sequence of snapshot graphs 𝒢 = (G₁, G₂, … , G_L) that share a common vertex set but might have different edge sets. The non-strict temporal exploration problem (NS-TEXP for short) introduced by Erlebach and Spooner, asks if a single agent can visit all vertices of a given temporal graph where the edges traversed by the agent are present in non-strict monotonous time steps, i.e., the agent can move along the edges of a snapshot graph with infinite speed. The exploration must at the latest be completed in the last snapshot graph. The optimization variant of this problem is the k-arb NS-TEXP problem, where the agent’s task is to visit at least k vertices of the temporal graph. We show that under standard computational complexity assumptions, neither of the problems NS-TEXP nor k-arb NS-TEXP allow for polynomial kernels in the standard parameters: number of vertices n, lifetime L, number of vertices to visit k, and maximal number of connected components per time step γ; as well as in the combined parameters L+k, L + γ, and k+γ. On the way to establishing these lower bounds, we answer a couple of questions left open by Erlebach and Spooner. We also initiate the study of structural kernelization by identifying a new parameter of a temporal graph p(𝒢) = ∑_{i=1}^L (|E(G_i)|) - |V(G)| + 1. Informally, this parameter measures how dynamic the temporal graph is. Our main algorithmic result is the construction of a polynomial (in p(𝒢)) kernel for the more general Weighted k-arb NS-TEXP problem, where weights are assigned to the vertices and the task is to find a temporal walk of weight at least k.

Cite as

Emmanuel Arrighi, Fedor V. Fomin, Petr A. Golovach, and Petra Wolf. Kernelizing Temporal Exploration Problems. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 1:1-1:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{arrighi_et_al:LIPIcs.IPEC.2023.1,
  author =	{Arrighi, Emmanuel and Fomin, Fedor V. and Golovach, Petr A. and Wolf, Petra},
  title =	{{Kernelizing Temporal Exploration Problems}},
  booktitle =	{18th International Symposium on Parameterized and Exact Computation (IPEC 2023)},
  pages =	{1:1--1:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-305-8},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{285},
  editor =	{Misra, Neeldhara and Wahlstr\"{o}m, Magnus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.1},
  URN =		{urn:nbn:de:0030-drops-194201},
  doi =		{10.4230/LIPIcs.IPEC.2023.1},
  annote =	{Keywords: Temporal graph, temporal exploration, computational complexity, kernel}
}
Document
Computing Paths of Large Rank in Planar Frameworks Deterministically

Authors: Fedor V. Fomin, Petr A. Golovach, Tuukka Korhonen, and Giannos Stamoulis

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


Abstract
A framework consists of an undirected graph G and a matroid M whose elements correspond to the vertices of G. Recently, Fomin et al. [SODA 2023] and Eiben et al. [ArXiV 2023] developed parameterized algorithms for computing paths of rank k in frameworks. More precisely, for vertices s and t of G, and an integer k, they gave FPT algorithms parameterized by k deciding whether there is an (s,t)-path in G whose vertex set contains a subset of elements of M of rank k. These algorithms are based on Schwartz-Zippel lemma for polynomial identity testing and thus are randomized, and therefore the existence of a deterministic FPT algorithm for this problem remains open. We present the first deterministic FPT algorithm that solves the problem in frameworks whose underlying graph G is planar. While the running time of our algorithm is worse than the running times of the recent randomized algorithms, our algorithm works on more general classes of matroids. In particular, this is the first FPT algorithm for the case when matroid M is represented over rationals. Our main technical contribution is the nontrivial adaptation of the classic irrelevant vertex technique to frameworks to reduce the given instance to one of bounded treewidth. This allows us to employ the toolbox of representative sets to design a dynamic programming procedure solving the problem efficiently on instances of bounded treewidth.

Cite as

Fedor V. Fomin, Petr A. Golovach, Tuukka Korhonen, and Giannos Stamoulis. Computing Paths of Large Rank in Planar Frameworks Deterministically. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 32:1-32:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{fomin_et_al:LIPIcs.ISAAC.2023.32,
  author =	{Fomin, Fedor V. and Golovach, Petr A. and Korhonen, Tuukka and Stamoulis, Giannos},
  title =	{{Computing Paths of Large Rank in Planar Frameworks Deterministically}},
  booktitle =	{34th International Symposium on Algorithms and Computation (ISAAC 2023)},
  pages =	{32:1--32:15},
  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.32},
  URN =		{urn:nbn:de:0030-drops-193341},
  doi =		{10.4230/LIPIcs.ISAAC.2023.32},
  annote =	{Keywords: Planar graph, longest path, linear matroid, irrelevant vertex}
}
Document
Faster Detours in Undirected Graphs

Authors: Shyan Akmal, Virginia Vassilevska Williams, Ryan Williams, and Zixuan Xu

Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)


Abstract
The k-Detour problem is a basic path-finding problem: given a graph G on n vertices, with specified nodes s and t, and a positive integer k, the goal is to determine if G has an st-path of length exactly dist(s,t) + k, where dist(s,t) is the length of a shortest path from s to t. The k-Detour problem is NP-hard when k is part of the input, so researchers have sought efficient parameterized algorithms for this task, running in f(k)poly(n) time, for f(⋅) as slow-growing as possible. We present faster algorithms for k-Detour in undirected graphs, running in 1.853^k poly(n) randomized and 4.082^kpoly(n) deterministic time. The previous fastest algorithms for this problem took 2.746^k poly(n) randomized and 6.523^k poly(n) deterministic time [Bezáková-Curticapean-Dell-Fomin, ICALP 2017]. Our algorithms use the fact that detecting a path of a given length in an undirected graph is easier if we are promised that the path belongs to what we call a "bipartitioned" subgraph, where the nodes are split into two parts and the path must satisfy constraints on those parts. Previously, this idea was used to obtain the fastest known algorithm for finding paths of length k in undirected graphs [Björklund-Husfeldt-Kaski-Koivisto, JCSS 2017], intuitively by looking for paths of length k in randomly bipartitioned subgraphs. Our algorithms for k-Detour stem from a new application of this idea, which does not involve choosing the bipartitioned subgraphs randomly. Our work has direct implications for the k-Longest Detour problem, another related path-finding problem. In this problem, we are given the same input as in k-Detour, but are now tasked with determining if G has an st-path of length at least dist(s,t)+k. Our results for k-Detour imply that we can solve k-Longest Detour in 3.432^k poly(n) randomized and 16.661^k poly(n) deterministic time. The previous fastest algorithms for this problem took 7.539^k poly(n) randomized and 42.549^k poly(n) deterministic time [Fomin et al., STACS 2022].

Cite as

Shyan Akmal, Virginia Vassilevska Williams, Ryan Williams, and Zixuan Xu. Faster Detours in Undirected Graphs. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 7:1-7:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{akmal_et_al:LIPIcs.ESA.2023.7,
  author =	{Akmal, Shyan and Vassilevska Williams, Virginia and Williams, Ryan and Xu, Zixuan},
  title =	{{Faster Detours in Undirected Graphs}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{7:1--7:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.7},
  URN =		{urn:nbn:de:0030-drops-186601},
  doi =		{10.4230/LIPIcs.ESA.2023.7},
  annote =	{Keywords: path finding, detours, parameterized complexity, exact algorithms}
}
Document
Kernelization for Spreading Points

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

Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)


Abstract
We consider the following problem about dispersing points. Given a set of points in the plane, the task is to identify whether by moving a small number of points by small distance, we can obtain an arrangement of points such that no pair of points is "close" to each other. More precisely, for a family of n points, an integer k, and a real number d > 0, we ask whether at most k points could be relocated, each point at distance at most d from its original location, such that the distance between each pair of points is at least a fixed constant, say 1. A number of approximation algorithms for variants of this problem, under different names like distant representatives, disk dispersing, or point spreading, are known in the literature. However, to the best of our knowledge, the parameterized complexity of this problem remains widely unexplored. We make the first step in this direction by providing a kernelization algorithm that, in polynomial time, produces an equivalent instance with 𝒪(d²k³) points. As a byproduct of this result, we also design a non-trivial fixed-parameter tractable (FPT) algorithm for the problem, parameterized by k and d. Finally, we complement the result about polynomial kernelization by showing a lower bound that rules out the existence of a kernel whose size is polynomial in k alone, unless NP ⊆ coNP/poly.

Cite as

Fedor V. Fomin, Petr A. Golovach, Tanmay Inamdar, Saket Saurabh, and Meirav Zehavi. Kernelization for Spreading Points. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 48:1-48:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{fomin_et_al:LIPIcs.ESA.2023.48,
  author =	{Fomin, Fedor V. and Golovach, Petr A. and Inamdar, Tanmay and Saurabh, Saket and Zehavi, Meirav},
  title =	{{Kernelization for Spreading Points}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{48:1--48:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.48},
  URN =		{urn:nbn:de:0030-drops-187017},
  doi =		{10.4230/LIPIcs.ESA.2023.48},
  annote =	{Keywords: parameterized algorithms, kernelization, spreading points, distant representatives, unit disk packing}
}
Document
Lossy Kernelization for (Implicit) Hitting Set Problems

Authors: Fedor V. Fomin, Tien-Nam Le, Daniel Lokshtanov, Saket Saurabh, Stéphan Thomassé, and Meirav Zehavi

Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)


Abstract
We re-visit the complexity of polynomial time pre-processing (kernelization) for the d-Hitting Set problem. This is one of the most classic problems in Parameterized Complexity by itself, and, furthermore, it encompasses several other of the most well-studied problems in this field, such as Vertex Cover, Feedback Vertex Set in Tournaments (FVST) and Cluster Vertex Deletion (CVD). In fact, d-Hitting Set encompasses any deletion problem to a hereditary property that can be characterized by a finite set of forbidden induced subgraphs. With respect to bit size, the kernelization complexity of d-Hitting Set is essentially settled: there exists a kernel with 𝒪(k^d) bits (𝒪(k^d) sets and 𝒪(k^{d-1}) elements) and this it tight by the result of Dell and van Melkebeek [STOC 2010, JACM 2014]. Still, the question of whether there exists a kernel for d-Hitting Set with fewer elements has remained one of the most major open problems in Kernelization. In this paper, we first show that if we allow the kernelization to be lossy with a qualitatively better loss than the best possible approximation ratio of polynomial time approximation algorithms, then one can obtain kernels where the number of elements is linear for every fixed d. Further, based on this, we present our main result: we show that there exist approximate Turing kernelizations for d-Hitting Set that even beat the established bit-size lower bounds for exact kernelizations - in fact, we use a constant number of oracle calls, each with "near linear" (𝒪(k^{1+ε})) bit size, that is, almost the best one could hope for. Lastly, for two special cases of implicit 3-Hitting set, namely, FVST and CVD, we obtain the "best of both worlds" type of results - (1+ε)-approximate kernelizations with a linear number of vertices. In terms of size, this substantially improves the exact kernels of Fomin et al. [SODA 2018, TALG 2019], with simpler arguments.

Cite as

Fedor V. Fomin, Tien-Nam Le, Daniel Lokshtanov, Saket Saurabh, Stéphan Thomassé, and Meirav Zehavi. Lossy Kernelization for (Implicit) Hitting Set Problems. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 49:1-49:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{fomin_et_al:LIPIcs.ESA.2023.49,
  author =	{Fomin, Fedor V. and Le, Tien-Nam and Lokshtanov, Daniel and Saurabh, Saket and Thomass\'{e}, St\'{e}phan and Zehavi, Meirav},
  title =	{{Lossy Kernelization for (Implicit) Hitting Set Problems}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{49:1--49:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.49},
  URN =		{urn:nbn:de:0030-drops-187020},
  doi =		{10.4230/LIPIcs.ESA.2023.49},
  annote =	{Keywords: Hitting Set, Lossy Kernelization}
}
Document
FPT Approximation and Subexponential Algorithms for Covering Few or Many Edges

Authors: Fedor V. Fomin, Petr A. Golovach, Tanmay Inamdar, and Tomohiro Koana

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


Abstract
We study the α-Fixed Cardinality Graph Partitioning (α-FCGP) problem, the generic local graph partitioning problem introduced by Bonnet et al. [Algorithmica 2015]. In this problem, we are given a graph G, two numbers k,p and 0 ≤ α ≤ 1, the question is whether there is a set S ⊆ V of size k with a specified coverage function cov_α(S) at least p (or at most p for the minimization version). The coverage function cov_α(⋅) counts edges with exactly one endpoint in S with weight α and edges with both endpoints in S with weight 1 - α. α-FCGP generalizes a number of fundamental graph problems such as Densest k-Subgraph, Max k-Vertex Cover, and Max (k,n-k)-Cut. A natural question in the study of α-FCGP is whether the algorithmic results known for its special cases, like Max k-Vertex Cover, could be extended to more general settings. One of the simple but powerful methods for obtaining parameterized approximation [Manurangsi, SOSA 2019] and subexponential algorithms [Fomin et al. IPL 2011] for Max k-Vertex Cover is based on the greedy vertex degree orderings. The main insight of our work is that the idea of greed vertex degree ordering could be used to design fixed-parameter approximation schemes (FPT-AS) for α > 0 and the subexponential-time algorithms for the problem on apex-minor free graphs for maximization with α > 1/3 and minimization with α < 1/3.

Cite as

Fedor V. Fomin, Petr A. Golovach, Tanmay Inamdar, and Tomohiro Koana. FPT Approximation and Subexponential Algorithms for Covering Few or Many Edges. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 46:1-46:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{fomin_et_al:LIPIcs.MFCS.2023.46,
  author =	{Fomin, Fedor V. and Golovach, Petr A. and Inamdar, Tanmay and Koana, Tomohiro},
  title =	{{FPT Approximation and Subexponential Algorithms for Covering Few or Many Edges}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{46:1--46:8},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.46},
  URN =		{urn:nbn:de:0030-drops-185806},
  doi =		{10.4230/LIPIcs.MFCS.2023.46},
  annote =	{Keywords: Partial Vertex Cover, Approximation Algorithms, Max Cut}
}
Document
Track A: Algorithms, Complexity and Games
Approximating Long Cycle Above Dirac’s Guarantee

Authors: Fedor V. Fomin, Petr A. Golovach, Danil Sagunov, and Kirill Simonov

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)


Abstract
Parameterization above (or below) a guarantee is a successful concept in parameterized algorithms. The idea is that many computational problems admit "natural" guarantees bringing to algorithmic questions whether a better solution (above the guarantee) could be obtained efficiently. For example, for every boolean CNF formula on m clauses, there is an assignment that satisfies at least m/2 clauses. How difficult is it to decide whether there is an assignment satisfying more than m/2 + k clauses? Or, if an n-vertex graph has a perfect matching, then its vertex cover is at least n/2. Is there a vertex cover of size at least n/2 + k for some k ≥ 1 and how difficult is it to find such a vertex cover? The above guarantee paradigm has led to several exciting discoveries in the areas of parameterized algorithms and kernelization. We argue that this paradigm could bring forth fresh perspectives on well-studied problems in approximation algorithms. Our example is the longest cycle problem. One of the oldest results in extremal combinatorics is the celebrated Dirac’s theorem from 1952. Dirac’s theorem provides the following guarantee on the length of the longest cycle: for every 2-connected n-vertex graph G with minimum degree δ(G) ≤ n/2, the length of the longest cycle L is at least 2δ(G). Thus the "essential" part of finding the longest cycle is in approximating the "offset" k = L - 2δ(G). The main result of this paper is the above-guarantee approximation theorem for k. Informally, the theorem says that approximating the offset k is not harder than approximating the total length L of a cycle. In other words, for any (reasonably well-behaved) function f, a polynomial time algorithm constructing a cycle of length f(L) in an undirected graph with a cycle of length L, yields a polynomial time algorithm constructing a cycle of length 2δ(G)+Ω(f(k)).

Cite as

Fedor V. Fomin, Petr A. Golovach, Danil Sagunov, and Kirill Simonov. Approximating Long Cycle Above Dirac’s Guarantee. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 60:1-60:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{fomin_et_al:LIPIcs.ICALP.2023.60,
  author =	{Fomin, Fedor V. and Golovach, Petr A. and Sagunov, Danil and Simonov, Kirill},
  title =	{{Approximating Long Cycle Above Dirac’s Guarantee}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{60:1--60:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.60},
  URN =		{urn:nbn:de:0030-drops-181128},
  doi =		{10.4230/LIPIcs.ICALP.2023.60},
  annote =	{Keywords: Longest path, longest cycle, approximation algorithms, above guarantee parameterization, minimum degree, Dirac theorem}
}
Document
Track A: Algorithms, Complexity and Games
Compound Logics for Modification Problems

Authors: Fedor V. Fomin, Petr A. Golovach, Ignasi Sau, Giannos Stamoulis, and Dimitrios M. Thilikos

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)


Abstract
We introduce a novel model-theoretic framework inspired from graph modification and based on the interplay between model theory and algorithmic graph minors. The core of our framework is a new compound logic operating with two types of sentences, expressing graph modification: the modulator sentence, defining some property of the modified part of the graph, and the target sentence, defining some property of the resulting graph. In our framework, modulator sentences are in counting monadic second-order logic (CMSOL) and have models of bounded treewidth, while target sentences express first-order logic (FOL) properties along with minor-exclusion. Our logic captures problems that are not definable in first-order logic and, moreover, may have instances of unbounded treewidth. Also, it permits the modeling of wide families of problems involving vertex/edge removals, alternative modulator measures (such as elimination distance or G-treewidth), multistage modifications, and various cut problems. Our main result is that, for this compound logic, model-checking can be done in quadratic time. All derived algorithms are constructive and this, as a byproduct, extends the constructibility horizon of the algorithmic applications of the Graph Minors theorem of Robertson and Seymour. The proposed logic can be seen as a general framework to capitalize on the potential of the irrelevant vertex technique. It gives a way to deal with problem instances of unbounded treewidth, for which Courcelle’s theorem does not apply.

Cite as

Fedor V. Fomin, Petr A. Golovach, Ignasi Sau, Giannos Stamoulis, and Dimitrios M. Thilikos. Compound Logics for Modification Problems. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 61:1-61:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{fomin_et_al:LIPIcs.ICALP.2023.61,
  author =	{Fomin, Fedor V. and Golovach, Petr A. and Sau, Ignasi and Stamoulis, Giannos and Thilikos, Dimitrios M.},
  title =	{{Compound Logics for Modification Problems}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{61:1--61:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.61},
  URN =		{urn:nbn:de:0030-drops-181137},
  doi =		{10.4230/LIPIcs.ICALP.2023.61},
  annote =	{Keywords: Algorithmic meta-theorems, Graph modification problems, Model-checking, Graph minors, First-order logic, Monadic second-order logic, Flat Wall theorem, Irrelevant vertex technique}
}
Document
Coresets for Clustering in Geometric Intersection Graphs

Authors: Sayan Bandyapadhyay, Fedor V. Fomin, and Tanmay Inamdar

Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)


Abstract
Designing coresets - small-space sketches of the data preserving cost of the solutions within (1± ε)-approximate factor - is an important research direction in the study of center-based k-clustering problems, such as k-means or k-median. Feldman and Langberg [STOC'11] have shown that for k-clustering of n points in general metrics, it is possible to obtain coresets whose size depends logarithmically in n. Moreover, such a dependency in n is inevitable in general metrics. A significant amount of recent work in the area is devoted to obtaining coresests whose sizes are independent of n for special metrics, like d-dimensional Euclidean space [Huang, Vishnoi, STOC'20], doubling metrics [Huang, Jiang, Li, Wu, FOCS'18], metrics of graphs of bounded treewidth [Baker, Braverman, Huang, Jiang, Krauthgamer, Wu, ICML’20], or graphs excluding a fixed minor [Braverman, Jiang, Krauthgamer, Wu, SODA’21]. In this paper, we provide the first constructions of coresets whose size does not depend on n for k-clustering in the metrics induced by geometric intersection graphs. For example, we obtain (k log²k)/ε^𝒪(1) size coresets for k-clustering in Euclidean-weighted unit-disk graphs (UDGs) and unit-square graphs (USGs). These constructions follow from a general theorem that identifies two canonical properties of a graph metric sufficient for obtaining coresets whose size is independent of n. The proof of our theorem builds on the recent work of Cohen-Addad, Saulpic, and Schwiegelshohn [STOC '21], which ensures small-sized coresets conditioned on the existence of an interesting set of centers, called centroid set. The main technical contribution of our work is the proof of the existence of such a small-sized centroid set for graphs that satisfy the two canonical properties. Loosely speaking, the metrics of geometric intersection graphs are "similar" to the Euclidean metrics for points that are close, and to the shortest path metrics of planar graphs for points that are far apart. The main technical challenge in constructing centroid sets of small sizes is in combining these two very different metrics. The new coreset construction helps to design the first (1+ε)-approximation for center-based clustering problems in UDGs and USGs, that is fixed-parameter tractable in k and ε (FPT-AS).

Cite as

Sayan Bandyapadhyay, Fedor V. Fomin, and Tanmay Inamdar. Coresets for Clustering in Geometric Intersection Graphs. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 10:1-10:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{bandyapadhyay_et_al:LIPIcs.SoCG.2023.10,
  author =	{Bandyapadhyay, Sayan and Fomin, Fedor V. and Inamdar, Tanmay},
  title =	{{Coresets for Clustering in Geometric Intersection Graphs}},
  booktitle =	{39th International Symposium on Computational Geometry (SoCG 2023)},
  pages =	{10:1--10:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-273-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{258},
  editor =	{Chambers, Erin W. and Gudmundsson, Joachim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.10},
  URN =		{urn:nbn:de:0030-drops-178605},
  doi =		{10.4230/LIPIcs.SoCG.2023.10},
  annote =	{Keywords: k-median, k-means, clustering, coresets, geometric graphs}
}
Document
FPT Approximation for Fair Minimum-Load Clustering

Authors: Sayan Bandyapadhyay, Fedor V. Fomin, Petr A. Golovach, Nidhi Purohit, and Kirill Simonov

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


Abstract
In this paper, we consider the Minimum-Load k-Clustering/Facility Location (MLkC) problem where we are given a set P of n points in a metric space that we have to cluster and an integer k > 0 that denotes the number of clusters. Additionally, we are given a set F of cluster centers in the same metric space. The goal is to select a set C ⊆ F of k centers and assign each point in P to a center in C, such that the maximum load over all centers is minimized. Here the load of a center is the sum of the distances between it and the points assigned to it. Although clustering/facility location problems have rich literature, the minimum-load objective has not been studied substantially, and hence MLkC has remained a poorly understood problem. More interestingly, the problem is notoriously hard even in some special cases including the one in line metrics as shown by Ahmadian et al. [APPROX 2014, ACM Trans. Algorithms 2018]. They also show APX-hardness of the problem in the plane. On the other hand, the best-known approximation factor for MLkC is O(k), even in the plane. In this work, we study a fair version of MLkC inspired by the work of Chierichetti et al. [NeurIPS, 2017]. Here the input points are partitioned into 𝓁 protected groups, and only clusters that proportionally represent each group are allowed. MLkC is the special case with 𝓁 = 1. For the fair version, we are able to obtain a randomized 3-approximation algorithm in f(k,𝓁)⋅ n^O(1) time. Also, our scheme leads to an improved (1 + ε)-approximation in the case of Euclidean norm with the same running time (depending also linearly on the dimension d). Our results imply the same approximations for MLkC with running time f(k)⋅ n^O(1), achieving the first constant-factor FPT approximations for this problem in general and Euclidean metric spaces.

Cite as

Sayan Bandyapadhyay, Fedor V. Fomin, Petr A. Golovach, Nidhi Purohit, and Kirill Simonov. FPT Approximation for Fair Minimum-Load Clustering. In 17th International Symposium on Parameterized and Exact Computation (IPEC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 249, pp. 4:1-4:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{bandyapadhyay_et_al:LIPIcs.IPEC.2022.4,
  author =	{Bandyapadhyay, Sayan and Fomin, Fedor V. and Golovach, Petr A. and Purohit, Nidhi and Simonov, Kirill},
  title =	{{FPT Approximation for Fair Minimum-Load Clustering}},
  booktitle =	{17th International Symposium on Parameterized and Exact Computation (IPEC 2022)},
  pages =	{4:1--4:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-260-0},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{249},
  editor =	{Dell, Holger and Nederlof, Jesper},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2022.4},
  URN =		{urn:nbn:de:0030-drops-173600},
  doi =		{10.4230/LIPIcs.IPEC.2022.4},
  annote =	{Keywords: fair clustering, load balancing, parameterized approximation}
}
Document
Exact Exponential Algorithms for Clustering Problems

Authors: Fedor V. Fomin, Petr A. Golovach, Tanmay Inamdar, Nidhi Purohit, and Saket Saurabh

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


Abstract
In this paper we initiate a systematic study of exact algorithms for some of the well known clustering problems, namely k-MEDIAN and k-MEANS. In k-MEDIAN, the input consists of a set X of n points belonging to a metric space, and the task is to select a subset C ⊆ X of k points as centers, such that the sum of the distances of every point to its nearest center is minimized. In k-MEANS, the objective is to minimize the sum of squares of the distances instead. It is easy to design an algorithm running in time max_{k ≤ n} {n choose k} n^𝒪(1) = 𝒪^*(2ⁿ) (here, 𝒪^*(⋅) notation hides polynomial factors in n). In this paper we design first non-trivial exact algorithms for these problems. In particular, we obtain an 𝒪^*((1.89)ⁿ) time exact algorithm for k-MEDIAN that works for any value of k. Our algorithm is quite general in that it does not use any properties of the underlying (metric) space - it does not even require the distances to satisfy the triangle inequality. In particular, the same algorithm also works for k-Means. We complement this result by showing that the running time of our algorithm is asymptotically optimal, up to the base of the exponent. That is, unless the Exponential Time Hypothesis fails, there is no algorithm for these problems running in time 2^o(n)⋅n^𝒪(1). Finally, we consider the "facility location" or "supplier" versions of these clustering problems, where, in addition to the set X we are additionally given a set of m candidate centers (or facilities) F, and objective is to find a subset of k centers from F. The goal is still to minimize the k-Median/k-Means/k-Center objective. For these versions we give a 𝒪(2ⁿ (mn)^𝒪(1)) time algorithms using subset convolution. We complement this result by showing that, under the Set Cover Conjecture, the "supplier" versions of these problems do not admit an exact algorithm running in time 2^{(1-ε) n} (mn)^𝒪(1).

Cite as

Fedor V. Fomin, Petr A. Golovach, Tanmay Inamdar, Nidhi Purohit, and Saket Saurabh. Exact Exponential Algorithms for Clustering Problems. In 17th International Symposium on Parameterized and Exact Computation (IPEC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 249, pp. 13:1-13:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{fomin_et_al:LIPIcs.IPEC.2022.13,
  author =	{Fomin, Fedor V. and Golovach, Petr A. and Inamdar, Tanmay and Purohit, Nidhi and Saurabh, Saket},
  title =	{{Exact Exponential Algorithms for Clustering Problems}},
  booktitle =	{17th International Symposium on Parameterized and Exact Computation (IPEC 2022)},
  pages =	{13:1--13:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-260-0},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{249},
  editor =	{Dell, Holger and Nederlof, Jesper},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2022.13},
  URN =		{urn:nbn:de:0030-drops-173691},
  doi =		{10.4230/LIPIcs.IPEC.2022.13},
  annote =	{Keywords: clustering, k-median, k-means, exact algorithms}
}
Document
Longest Cycle Above Erdős-Gallai Bound

Authors: Fedor V. Fomin, Petr A. Golovach, Danil Sagunov, and Kirill Simonov

Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)


Abstract
In 1959, Erdős and Gallai proved that every graph G with average vertex degree ad(G) ≥ 2 contains a cycle of length at least ad(G). We provide an algorithm that for k ≥ 0 in time 2^𝒪(k)⋅n^𝒪(1) decides whether a 2-connected n-vertex graph G contains a cycle of length at least ad(G)+k. This resolves an open problem explicitly mentioned in several papers. The main ingredients of our algorithm are new graph-theoretical results interesting on their own.

Cite as

Fedor V. Fomin, Petr A. Golovach, Danil Sagunov, and Kirill Simonov. Longest Cycle Above Erdős-Gallai Bound. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 55:1-55:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{fomin_et_al:LIPIcs.ESA.2022.55,
  author =	{Fomin, Fedor V. and Golovach, Petr A. and Sagunov, Danil and Simonov, Kirill},
  title =	{{Longest Cycle Above Erd\H{o}s-Gallai Bound}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{55:1--55:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.55},
  URN =		{urn:nbn:de:0030-drops-169935},
  doi =		{10.4230/LIPIcs.ESA.2022.55},
  annote =	{Keywords: Longest path, longest cycle, fixed-parameter tractability, above guarantee parameterization, average degree, Erd\H{o}s and Gallai theorem}
}
Document
Invited Talk
Long Cycles in Graphs: Extremal Combinatorics Meets Parameterized Algorithms (Invited Talk)

Authors: Fedor V. Fomin, Petr A. Golovach, Danil Sagunov, and Kirill Simonov

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


Abstract
We discuss recent algorithmic extensions of two classic results of extremal combinatorics about long paths in graphs. First, the theorem of Dirac from 1952 asserts that a 2-connected graph G with the minimum vertex degree d > 1, is either Hamiltonian or contains a cycle of length at least 2d. Second, the theorem of Erdős-Gallai from 1959, states that a graph G with the average vertex degree D > 1, contains a cycle of length at least D. The proofs of these theorems are constructive, they provide polynomial-time algorithms constructing cycles of lengths 2d and D. We extend these algorithmic results by showing that each of the problems, to decide whether a 2-connected graph contains a cycle of length at least 2d+k or of a cycle of length at least D+k, is fixed-parameter tractable parameterized by k.

Cite as

Fedor V. Fomin, Petr A. Golovach, Danil Sagunov, and Kirill Simonov. Long Cycles in Graphs: Extremal Combinatorics Meets Parameterized Algorithms (Invited Talk). In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 1:1-1:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{fomin_et_al:LIPIcs.MFCS.2022.1,
  author =	{Fomin, Fedor V. and Golovach, Petr A. and Sagunov, Danil and Simonov, Kirill},
  title =	{{Long Cycles in Graphs: Extremal Combinatorics Meets Parameterized Algorithms}},
  booktitle =	{47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
  pages =	{1:1--1:4},
  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.1},
  URN =		{urn:nbn:de:0030-drops-167999},
  doi =		{10.4230/LIPIcs.MFCS.2022.1},
  annote =	{Keywords: Longest path, longest cycle, fixed-parameter tractability, above guarantee parameterization, average degree, dense graph, Dirac theorem, Erd\H{o}s-Gallai theorem}
}
Document
Track A: Algorithms, Complexity and Games
(Re)packing Equal Disks into Rectangle

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

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)


Abstract
The problem of packing of equal disks (or circles) into a rectangle is a fundamental geometric problem. (By a packing here we mean an arrangement of disks in a rectangle without overlapping.) We consider the following algorithmic generalization of the equal disk packing problem. In this problem, for a given packing of equal disks into a rectangle, the question is whether by changing positions of a small number of disks, we can allocate space for packing more disks. More formally, in the repacking problem, for a given set of n equal disks packed into a rectangle and integers k and h, we ask whether it is possible by changing positions of at most h disks to pack n+k disks. Thus the problem of packing equal disks is the special case of our problem with n = h = 0. While the computational complexity of packing equal disks into a rectangle remains open, we prove that the repacking problem is NP-hard already for h = 0. Our main algorithmic contribution is an algorithm that solves the repacking problem in time (h+k)^𝒪(h+k)⋅|I|^𝒪(1), where |I| is the input size. That is, the problem is fixed-parameter tractable parameterized by k and h.

Cite as

Fedor V. Fomin, Petr A. Golovach, Tanmay Inamdar, and Meirav Zehavi. (Re)packing Equal Disks into Rectangle. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 60:1-60:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{fomin_et_al:LIPIcs.ICALP.2022.60,
  author =	{Fomin, Fedor V. and Golovach, Petr A. and Inamdar, Tanmay and Zehavi, Meirav},
  title =	{{(Re)packing Equal Disks into Rectangle}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{60:1--60:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.60},
  URN =		{urn:nbn:de:0030-drops-164011},
  doi =		{10.4230/LIPIcs.ICALP.2022.60},
  annote =	{Keywords: circle packing, unit disks, parameterized complexity, fixed-parameter tractability}
}
Document
Detours in Directed Graphs

Authors: Fedor V. Fomin, Petr A. Golovach, William Lochet, Danil Sagunov, Kirill Simonov, and Saket Saurabh

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


Abstract
We study two "above guarantee" versions of the classical Longest Path problem on undirected and directed graphs and obtain the following results. In the first variant of Longest Path that we study, called Longest Detour, the task is to decide whether a graph has an (s,t)-path of length at least dist_G(s,t)+k (where dist_G(s,t) denotes the length of a shortest path from s to t). Bezáková et al. [Ivona Bezáková et al., 2019] proved that on undirected graphs the problem is fixed-parameter tractable (FPT) by providing an algorithm of running time 2^{O(k)}⋅ n. Further, they left the parameterized complexity of the problem on directed graphs open. Our first main result establishes a connection between Longest Detour on directed graphs and 3-Disjoint Paths on directed graphs. Using these new insights, we design a 2^{O (k)}· n^{O(1)} time algorithm for the problem on directed planar graphs. Further, the new approach yields a significantly faster FPT algorithm on undirected graphs. In the second variant of Longest Path, namely Longest Path above Diameter, the task is to decide whether the graph has a path of length at least diam(G)+k(diam(G)denotes the length of a longest shortest path in a graph G). We obtain dichotomy results about Longest Path above Diameter on undirected and directed graphs. For (un)directed graphs, Longest Path above Diameter is NP-complete even for k=1. However, if the input undirected graph is 2-connected, then the problem is FPT. On the other hand, for 2-connected directed graphs, we show that Longest Path above Diameter is solvable in polynomial time for each k ∈ {1,..., 4} and is NP-complete for every k ≥ 5. The parameterized complexity of Longest Detour on general directed graphs remains an interesting open problem.

Cite as

Fedor V. Fomin, Petr A. Golovach, William Lochet, Danil Sagunov, Kirill Simonov, and Saket Saurabh. Detours in Directed Graphs. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 29:1-29:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{fomin_et_al:LIPIcs.STACS.2022.29,
  author =	{Fomin, Fedor V. and Golovach, Petr A. and Lochet, William and Sagunov, Danil and Simonov, Kirill and Saurabh, Saket},
  title =	{{Detours in Directed Graphs}},
  booktitle =	{39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)},
  pages =	{29:1--29:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-222-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{219},
  editor =	{Berenbrink, Petra and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.29},
  URN =		{urn:nbn:de:0030-drops-158390},
  doi =		{10.4230/LIPIcs.STACS.2022.29},
  annote =	{Keywords: longest path, longest detour, diameter, directed graphs, parameterized complexity}
}
  • Refine by Author
  • 75 Fomin, Fedor V.
  • 37 Golovach, Petr A.
  • 31 Saurabh, Saket
  • 18 Lokshtanov, Daniel
  • 13 Zehavi, Meirav
  • Show More...

  • Refine by Classification
  • 26 Theory of computation → Parameterized complexity and exact algorithms
  • 17 Mathematics of computing → Graph algorithms
  • 7 Theory of computation → Fixed parameter tractability
  • 6 Theory of computation → Graph algorithms analysis
  • 4 Theory of computation → Facility location and clustering
  • Show More...

  • Refine by Keyword
  • 15 parameterized complexity
  • 8 kernelization
  • 7 Parameterized Complexity
  • 7 fixed-parameter tractability
  • 6 Parameterized complexity
  • Show More...

  • Refine by Type
  • 82 document

  • Refine by Publication Year
  • 13 2020
  • 9 2023
  • 8 2019
  • 7 2017
  • 7 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