18 Search Results for "Koana, Tomohiro"


Document
Parameterized Vertex Integrity Revisited

Authors: Tesshu Hanaka, Michael Lampis, Manolis Vasilakis, and Kanae Yoshiwatari

Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)


Abstract
Vertex integrity is a graph parameter that measures the connectivity of a graph. Informally, its meaning is that a graph has small vertex integrity if it has a small separator whose removal disconnects the graph into connected components which are themselves also small. Graphs with low vertex integrity are very structured; this renders many hard problems tractable and has recently attracted interest in this notion from the parameterized complexity community. In this paper we revisit the NP-complete problem of computing the vertex integrity of a given graph from the point of view of structural parameterizations. We present a number of new results, which also answer some recently posed open questions from the literature. Specifically, we show that unweighted vertex integrity is W[1]-hard parameterized by treedepth; we show that the problem remains W[1]-hard if we parameterize by feedback edge set size (via a reduction from a Bin Packing variant which may be of independent interest); and complementing this we show that the problem is FPT by max-leaf number. Furthermore, for weighted vertex integrity, we show that the problem admits a single-exponential FPT algorithm parameterized by vertex cover or by modular width, the latter result improving upon a previous algorithm which required weights to be polynomially bounded.

Cite as

Tesshu Hanaka, Michael Lampis, Manolis Vasilakis, and Kanae Yoshiwatari. Parameterized Vertex Integrity Revisited. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 58:1-58:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@InProceedings{hanaka_et_al:LIPIcs.MFCS.2024.58,
  author =	{Hanaka, Tesshu and Lampis, Michael and Vasilakis, Manolis and Yoshiwatari, Kanae},
  title =	{{Parameterized Vertex Integrity Revisited}},
  booktitle =	{49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)},
  pages =	{58:1--58:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-335-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{306},
  editor =	{Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.58},
  URN =		{urn:nbn:de:0030-drops-206141},
  doi =		{10.4230/LIPIcs.MFCS.2024.58},
  annote =	{Keywords: Parameterized Complexity, Treedepth, Vertex Integrity}
}
Document
Track A: Algorithms, Complexity and Games
Two-Sets Cut-Uncut on Planar Graphs

Authors: Matthias Bentert, Pål Grønås Drange, Fedor V. Fomin, Petr A. Golovach, and Tuukka Korhonen

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)


Abstract
We study Two-Sets Cut-Uncut on planar graphs. Therein, one is given an undirected planar graph G and two disjoint sets S and T of vertices as input. The question is, what is the minimum number of edges to remove from G, such that all vertices in S are separated from all vertices in T, while maintaining that every vertex in S, and respectively in T, stays in the same connected component. We show that this problem can be solved in 2^{|S|+|T|} n^𝒪(1) time with a one-sided-error randomized algorithm. Our algorithm implies a polynomial-time algorithm for the network diversion problem on planar graphs, which resolves an open question from the literature. More generally, we show that Two-Sets Cut-Uncut is fixed-parameter tractable when parameterized by the number r of faces in a planar embedding covering the terminals S ∪ T, by providing a 2^𝒪(r) n^𝒪(1)-time algorithm.

Cite as

Matthias Bentert, Pål Grønås Drange, Fedor V. Fomin, Petr A. Golovach, and Tuukka Korhonen. Two-Sets Cut-Uncut on Planar Graphs. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 22:1-22:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@InProceedings{bentert_et_al:LIPIcs.ICALP.2024.22,
  author =	{Bentert, Matthias and Drange, P\r{a}l Gr{\o}n\r{a}s and Fomin, Fedor V. and Golovach, Petr A. and Korhonen, Tuukka},
  title =	{{Two-Sets Cut-Uncut on Planar Graphs}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{22:1--22:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.22},
  URN =		{urn:nbn:de:0030-drops-201654},
  doi =		{10.4230/LIPIcs.ICALP.2024.22},
  annote =	{Keywords: planar graphs, cut-uncut, group-constrained paths}
}
Document
Track A: Algorithms, Complexity and Games
Satisfiability to Coverage in Presence of Fairness, Matroid, and Global Constraints

Authors: Tanmay Inamdar, Pallavi Jain, Daniel Lokshtanov, Abhishek Sahu, Saket Saurabh, and Anannya Upasana

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)


Abstract
In the MaxSAT with Cardinality Constraint problem (CC-MaxSAT), we are given a CNF-formula Φ, and a positive integer k, and the goal is to find an assignment β with at most k variables set to true (also called a weight k-assignment) such that the number of clauses satisfied by β is maximized. Maximum Coverage can be seen as a special case of CC-MaxSat, where the formula Φ is monotone, i.e., does not contain any negative literals. CC-MaxSat and Maximum Coverage are extremely well-studied problems in the approximation algorithms as well as the parameterized complexity literature. Our first conceptual contribution is that CC-MaxSat and Maximum Coverage are equivalent to each other in the context of FPT-Approximation parameterized by k (here, the approximation is in terms of the number of clauses satisfied/elements covered). In particular, we give a randomized reduction from CC-MaxSat to Maximum Coverage running in time 𝒪(1/ε)^{k} ⋅ (m+n)^{𝒪(1)} that preserves the approximation guarantee up to a factor of (1-ε). Furthermore, this reduction also works in the presence of "fairness" constraints on the satisfied clauses, as well as matroid constraints on the set of variables that are assigned true. Here, the "fairness" constraints are modeled by partitioning the clauses of the formula Φ into r different colors, and the goal is to find an assignment that satisfies at least t_j clauses of each color 1 ≤ j ≤ r. Armed with this reduction, we focus on designing FPT-Approximation schemes (FPT-ASes) for Maximum Coverage and its generalizations. Our algorithms are based on a novel combination of a variety of ideas, including a carefully designed probability distribution that exploits sparse coverage functions. These algorithms substantially generalize the results in Jain et al. [SODA 2023] for CC-MaxSat and Maximum Coverage for K_{d,d}-free set systems (i.e., no d sets share d elements), as well as a recent FPT-AS for Matroid Constrained Maximum Coverage by Sellier [ESA 2023] for frequency-d set systems.

Cite as

Tanmay Inamdar, Pallavi Jain, Daniel Lokshtanov, Abhishek Sahu, Saket Saurabh, and Anannya Upasana. Satisfiability to Coverage in Presence of Fairness, Matroid, and Global Constraints. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 88:1-88:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@InProceedings{inamdar_et_al:LIPIcs.ICALP.2024.88,
  author =	{Inamdar, Tanmay and Jain, Pallavi and Lokshtanov, Daniel and Sahu, Abhishek and Saurabh, Saket and Upasana, Anannya},
  title =	{{Satisfiability to Coverage in Presence of Fairness, Matroid, and Global Constraints}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{88:1--88:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.88},
  URN =		{urn:nbn:de:0030-drops-202318},
  doi =		{10.4230/LIPIcs.ICALP.2024.88},
  annote =	{Keywords: Partial Vertex Cover, Max SAT, FPT Approximation, Matroids}
}
Document
Track A: Algorithms, Complexity and Games
Detecting Disjoint Shortest Paths in Linear Time and More

Authors: Shyan Akmal, Virginia Vassilevska Williams, and Nicole Wein

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)


Abstract
In the k-Disjoint Shortest Paths (k-DSP) problem, we are given a graph G (with positive edge weights) on n nodes and m edges with specified source vertices s_1, … , s_k, and target vertices t_1, … , t_k, and are tasked with determining if G contains vertex-disjoint (s_i,t_i)-shortest paths. For any constant k, it is known that k-DSP can be solved in polynomial time over undirected graphs and directed acyclic graphs (DAGs). However, the exact time complexity of k-DSP remains mysterious, with large gaps between the fastest known algorithms and best conditional lower bounds. In this paper, we obtain faster algorithms for important cases of k-DSP, and present better conditional lower bounds for k-DSP and its variants. Previous work solved 2-DSP over weighted undirected graphs in O(n⁷) time, and weighted DAGs in O(mn) time. For the main result of this paper, we present optimal linear time algorithms for solving 2-DSP on weighted undirected graphs and DAGs. Our linear time algorithms are algebraic however, and so only solve the detection rather than search version of 2-DSP (we show how to solve the search version in O(mn) time, which is faster than the previous best runtime in weighted undirected graphs, but only matches the previous best runtime for DAGs). We also obtain a faster algorithm for k-Edge Disjoint Shortest Paths (k-EDSP) in DAGs, the variant of k-DSP where one seeks edge-disjoint instead of vertex-disjoint paths between sources and their corresponding targets. Algorithms for k-EDSP on DAGs from previous work take Ω(m^k) time. We show that k-EDSP can be solved over DAGs in O(mn^{k-1}) time, matching the fastest known runtime for solving k-DSP over DAGs. Previous work established conditional lower bounds for solving k-DSP and its variants via reductions from detecting cliques in graphs. Prior work implied that k-Clique can be reduced to 2k-DSP in DAGs and undirected graphs with O((kn)²) nodes. We improve this reduction, by showing how to reduce from k-Clique to k-DSP in DAGs and undirected graphs with O((kn)²) nodes (halving the number of paths needed in the reduced instance). A variant of k-DSP is the k-Disjoint Paths (k-DP) problem, where the solution paths no longer need to be shortest paths. Previous work reduced from k-Clique to p-DP in DAGs with O(kn) nodes, for p = k + k(k-1)/2. We improve this by showing a reduction from k-Clique to p-DP, for p = k + ⌊k²/4⌋. Under the k-Clique Hypothesis from fine-grained complexity, our results establish better conditional lower bounds for k-DSP for all k ≥ 4, and better conditional lower bounds for p-DP for all p ≤ 4031. Notably, our work gives the first nontrivial conditional lower bounds 4-DP in DAGs and 4-DSP in undirected graphs and DAGs. Before our work, nontrivial conditional lower bounds were only known for k-DP and k-DSP on such graphs when k ≥ 6.

Cite as

Shyan Akmal, Virginia Vassilevska Williams, and Nicole Wein. Detecting Disjoint Shortest Paths in Linear Time and More. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 9:1-9:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@InProceedings{akmal_et_al:LIPIcs.ICALP.2024.9,
  author =	{Akmal, Shyan and Vassilevska Williams, Virginia and Wein, Nicole},
  title =	{{Detecting Disjoint Shortest Paths in Linear Time and More}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{9:1--9:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.9},
  URN =		{urn:nbn:de:0030-drops-201529},
  doi =		{10.4230/LIPIcs.ICALP.2024.9},
  annote =	{Keywords: disjoint shortest paths, algebraic graph algorithms, disjoint paths, fine-grained complexity, clique}
}
Document
Fully Polynomial-Time Algorithms Parameterized by Vertex Integrity Using Fast Matrix Multiplication

Authors: Matthias Bentert, Klaus Heeger, and Tomohiro Koana

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


Abstract
We study the computational complexity of several polynomial-time-solvable graph problems parameterized by vertex integrity, a measure of a graph’s vulnerability to vertex removal in terms of connectivity. Vertex integrity is the smallest number ι such that there is a set S of ι' ≤ ι vertices such that every connected component of G-S contains at most ι-ι' vertices. It is known that the vertex integrity lies between the well-studied parameters vertex cover number and tree-depth. Our work follows similar studies for vertex cover number [Alon and Yuster, ESA 2007] and tree-depth [Iwata, Ogasawara, and Ohsaka, STACS 2018]. Alon and Yuster designed algorithms for graphs with small vertex cover number using fast matrix multiplications. We demonstrate that fast matrix multiplication can also be effectively used when parameterizing by vertex integrity ι by developing efficient algorithms for problems including an O(ι^{ω-1}n)-time algorithm for Maximum Matching and an O(ι^{(ω-1)/2}n²) ⊆ O(ι^{0.687} n²)-time algorithm for All-Pairs Shortest Paths. These algorithms can be faster than previous algorithms parameterized by tree-depth, for which fast matrix multiplication is not known to be effective.

Cite as

Matthias Bentert, Klaus Heeger, and Tomohiro Koana. Fully Polynomial-Time Algorithms Parameterized by Vertex Integrity Using Fast Matrix Multiplication. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 16:1-16:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{bentert_et_al:LIPIcs.ESA.2023.16,
  author =	{Bentert, Matthias and Heeger, Klaus and Koana, Tomohiro},
  title =	{{Fully Polynomial-Time Algorithms Parameterized by Vertex Integrity Using Fast Matrix Multiplication}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{16:1--16: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.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.16},
  URN =		{urn:nbn:de:0030-drops-186692},
  doi =		{10.4230/LIPIcs.ESA.2023.16},
  annote =	{Keywords: FPT in P, Algebraic Algorithms, Adaptive Algorithms, Subgraph Detection, Matching, APSP}
}
Document
Correlating Theory and Practice in Finding Clubs and Plexes

Authors: Aleksander Figiel, Tomohiro Koana, André Nichterlein, and Niklas Wünsche

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


Abstract
For solving NP-hard problems there is often a huge gap between theoretical guarantees and observed running times on real-world instances. As a first step towards tackling this issue, we propose an approach to quantify the correlation between theoretical and observed running times. We use two NP-hard problems related to finding large "cliquish" subgraphs in a given graph as demonstration of this measure. More precisely, we focus on finding maximum s-clubs and s-plexes, i. e., graphs of diameter s and graphs where each vertex is adjacent to all but s vertices. Preprocessing based on Turing kernelization is a standard tool to tackle these problems, especially on sparse graphs. We provide a parameterized analysis for the Turing kernelization and demonstrate their usefulness in practice. Moreover, we demonstrate that our measure indeed captures the correlation between these new theoretical and the observed running times.

Cite as

Aleksander Figiel, Tomohiro Koana, André Nichterlein, and Niklas Wünsche. Correlating Theory and Practice in Finding Clubs and Plexes. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 47:1-47:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{figiel_et_al:LIPIcs.ESA.2023.47,
  author =	{Figiel, Aleksander and Koana, Tomohiro and Nichterlein, Andr\'{e} and W\"{u}nsche, Niklas},
  title =	{{Correlating Theory and Practice in Finding Clubs and Plexes}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{47:1--47:18},
  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.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.47},
  URN =		{urn:nbn:de:0030-drops-187000},
  doi =		{10.4230/LIPIcs.ESA.2023.47},
  annote =	{Keywords: Preprocessing, Turing kernelization, Pearson correlation coefficient}
}
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.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
Induced Matching Below Guarantees: Average Paves the Way for Fixed-Parameter Tractability

Authors: Tomohiro Koana

Published in: LIPIcs, Volume 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)


Abstract
In this work, we study the Induced Matching problem: Given an undirected graph G and an integer 𝓁, is there an induced matching M of size at least 𝓁? An edge subset M is an induced matching in G if M is a matching such that there is no edge between two distinct edges of M. Our work looks into the parameterized complexity of Induced Matching with respect to "below guarantee" parameterizations. We consider the parameterization u - 𝓁 for an upper bound u on the size of any induced matching. For instance, any induced matching is of size at most n/2 where n is the number of vertices, which gives us a parameter n/2 - 𝓁. In fact, there is a straightforward 9^{n/2 - 𝓁} ⋅ n^O(1)-time algorithm for Induced Matching [Moser and Thilikos, J. Discrete Algorithms]. Motivated by this, we ask: Is Induced Matching FPT for a parameter smaller than n/2 - 𝓁? In search for such parameters, we consider MM(G) - 𝓁 and IS(G) - 𝓁, where MM(G) is the maximum matching size and IS(G) is the maximum independent set size of G. We find that Induced Matching is presumably not FPT when parameterized by MM(G) - 𝓁 or IS(G) - 𝓁. In contrast to these intractability results, we find that taking the average of the two helps - our main result is a branching algorithm that solves Induced Matching in 49^{(MM(G) + IS(G))/ 2 - 𝓁} ⋅ n^O(1) time. Our algorithm makes use of the Gallai-Edmonds decomposition to find a structure to branch on.

Cite as

Tomohiro Koana. Induced Matching Below Guarantees: Average Paves the Way for Fixed-Parameter Tractability. In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 39:1-39:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{koana:LIPIcs.STACS.2023.39,
  author =	{Koana, Tomohiro},
  title =	{{Induced Matching Below Guarantees: Average Paves the Way for Fixed-Parameter Tractability}},
  booktitle =	{40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)},
  pages =	{39:1--39:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-266-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{254},
  editor =	{Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2023.39},
  URN =		{urn:nbn:de:0030-drops-176914},
  doi =		{10.4230/LIPIcs.STACS.2023.39},
  annote =	{Keywords: Parameterized Complexity, Below Guarantees, Induced Matching, Gallai-Edmonds Decomposition}
}
Document
Vertex Cover and Feedback Vertex Set Above and Below Structural Guarantees

Authors: Leon Kellerhals, Tomohiro Koana, and Pascal Kunz

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


Abstract
Vertex Cover parameterized by the solution size k is the quintessential fixed-parameter tractable problem. FPT algorithms are most interesting when the parameter is small. Several lower bounds on k are well-known, such as the maximum size of a matching. This has led to a line of research on parameterizations of Vertex Cover by the difference of the solution size k and a lower bound. The most prominent cases for such lower bounds for which the problem is FPT are the matching number or the optimal fractional LP solution. We investigate parameterizations by the difference between k and other graph parameters including the feedback vertex number, the degeneracy, cluster deletion number, and treewidth with the goal of finding the border of fixed-parameter tractability for said difference parameterizations. We also consider similar parameterizations of the Feedback Vertex Set problem.

Cite as

Leon Kellerhals, Tomohiro Koana, and Pascal Kunz. Vertex Cover and Feedback Vertex Set Above and Below Structural Guarantees. In 17th International Symposium on Parameterized and Exact Computation (IPEC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 249, pp. 19:1-19:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{kellerhals_et_al:LIPIcs.IPEC.2022.19,
  author =	{Kellerhals, Leon and Koana, Tomohiro and Kunz, Pascal},
  title =	{{Vertex Cover and Feedback Vertex Set Above and Below Structural Guarantees}},
  booktitle =	{17th International Symposium on Parameterized and Exact Computation (IPEC 2022)},
  pages =	{19:1--19: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.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2022.19},
  URN =		{urn:nbn:de:0030-drops-173758},
  doi =		{10.4230/LIPIcs.IPEC.2022.19},
  annote =	{Keywords: parameterized complexity, vertex cover, feedback vertex set, above guarantee parameterization}
}
Document
Track A: Algorithms, Complexity and Games
The Complexity of Finding Fair Many-To-One Matchings

Authors: Niclas Boehmer and Tomohiro Koana

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


Abstract
We analyze the (parameterized) computational complexity of "fair" variants of bipartite many-to-one matching, where each vertex from the "left" side is matched to exactly one vertex and each vertex from the "right" side may be matched to multiple vertices. We want to find a "fair" matching, in which each vertex from the right side is matched to a "fair" set of vertices. Assuming that each vertex from the left side has one color modeling its attribute, we study two fairness criteria. In one of them, we deem a vertex set fair if for any two colors, the difference between the numbers of their occurrences does not exceed a given threshold. Fairness is relevant when finding many-to-one matchings between students and colleges, voters and constituencies, and applicants and firms. Here colors may model sociodemographic attributes, party memberships, and qualifications, respectively. We show that finding a fair many-to-one matching is NP-hard even for three colors and maximum degree five. Our main contribution is the design of fixed-parameter tractable algorithms with respect to the number of vertices on the right side. Our algorithms make use of a variety of techniques including color coding. At the core lie integer linear programs encoding Hall like conditions. To establish the correctness of our integer programs, we prove a new separation result, inspired by Frank’s separation theorem [Frank, Discrete Math. 1982], which may also be of independent interest. We further obtain complete complexity dichotomies regarding the number of colors and the maximum degree of each side.

Cite as

Niclas Boehmer and Tomohiro Koana. The Complexity of Finding Fair Many-To-One Matchings. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 27:1-27:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{boehmer_et_al:LIPIcs.ICALP.2022.27,
  author =	{Boehmer, Niclas and Koana, Tomohiro},
  title =	{{The Complexity of Finding Fair Many-To-One Matchings}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{27:1--27:18},
  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.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.27},
  URN =		{urn:nbn:de:0030-drops-163680},
  doi =		{10.4230/LIPIcs.ICALP.2022.27},
  annote =	{Keywords: Graph theory, polynomial-time algorithms, NP-hardness, FPT, ILP, color coding, submodular and supermodular functions, algorithmic fairness}
}
Document
Covering Many (Or Few) Edges with k Vertices in Sparse Graphs

Authors: Tomohiro Koana, Christian Komusiewicz, André Nichterlein, and Frank Sommer

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


Abstract
We study the following two fixed-cardinality optimization problems (a maximization and a minimization variant). For a fixed α between zero and one we are given a graph and two numbers k ∈ ℕ and t ∈ ℚ. The task is to find a vertex subset S of exactly k vertices that has value at least (resp. at most for minimization) t. Here, the value of a vertex set computes as α times the number of edges with exactly one endpoint in S plus 1-α times the number of edges with both endpoints in S. These two problems generalize many prominent graph problems, such as Densest k-Subgraph, Sparsest k-Subgraph, Partial Vertex Cover, and Max (k,n-k)-Cut. In this work, we complete the picture of their parameterized complexity on several types of sparse graphs that are described by structural parameters. In particular, we provide kernelization algorithms and kernel lower bounds for these problems. A somewhat surprising consequence of our kernelizations is that Partial Vertex Cover and Max (k,n-k)-Cut not only behave in the same way but that the kernels for both problems can be obtained by the same algorithms.

Cite as

Tomohiro Koana, Christian Komusiewicz, André Nichterlein, and Frank Sommer. Covering Many (Or Few) Edges with k Vertices in Sparse Graphs. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 42:1-42:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{koana_et_al:LIPIcs.STACS.2022.42,
  author =	{Koana, Tomohiro and Komusiewicz, Christian and Nichterlein, Andr\'{e} and Sommer, Frank},
  title =	{{Covering Many (Or Few) Edges with k Vertices in Sparse Graphs}},
  booktitle =	{39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)},
  pages =	{42:1--42:18},
  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.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.42},
  URN =		{urn:nbn:de:0030-drops-158525},
  doi =		{10.4230/LIPIcs.STACS.2022.42},
  annote =	{Keywords: Parameterized Complexity, Kernelization, Partial Vertex Cover, Densest k-Subgraph, Max (k,n-k)-Cut, Degeneracy}
}
Document
Essentially Tight Kernels For (Weakly) Closed Graphs

Authors: Tomohiro Koana, Christian Komusiewicz, and Frank Sommer

Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)


Abstract
We study kernelization of classic hard graph problems when the input graphs fulfill triadic closure properties. More precisely, we consider the recently introduced parameters closure number c and weak closure number γ [Fox et al., SICOMP 2020] in addition to the standard parameter solution size k. The weak closure number γ of a graph is upper-bounded by the minimum of its closure number c and its degeneracy d. For Capacitated Vertex Cover, Connected Vertex Cover, and Induced Matching we obtain the first kernels of size k^𝒪(γ), k^𝒪(γ), and (γk)^𝒪(γ), respectively. This extends previous results on the kernelization of these problems on degenerate graphs. These kernels are essentially tight as these problems are unlikely to admit kernels of size k^o(γ) by previous results on their kernelization complexity in degenerate graphs [Cygan et al., ACM TALG 2017]. For Capacitated Vertex Cover, we show that even a kernel of size k^o(c) is unlikely. In contrast, for Connected Vertex Cover, we obtain a problem kernel with 𝒪(ck²) vertices. Moreover, we prove that searching for an induced subgraph of order at least k belonging to a hereditary graph class 𝒢 admits a kernel of size k^𝒪(γ) when 𝒢 contains all complete and all edgeless graphs. Finally, we provide lower bounds for the kernelization of Independent Set on graphs with constant closure number c and kernels for Dominating Set on weakly closed split graphs and weakly closed bipartite graphs.

Cite as

Tomohiro Koana, Christian Komusiewicz, and Frank Sommer. Essentially Tight Kernels For (Weakly) Closed Graphs. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 35:1-35:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{koana_et_al:LIPIcs.ISAAC.2021.35,
  author =	{Koana, Tomohiro and Komusiewicz, Christian and Sommer, Frank},
  title =	{{Essentially Tight Kernels For (Weakly) Closed Graphs}},
  booktitle =	{32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
  pages =	{35:1--35:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-214-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{212},
  editor =	{Ahn, Hee-Kap and Sadakane, Kunihiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.35},
  URN =		{urn:nbn:de:0030-drops-154681},
  doi =		{10.4230/LIPIcs.ISAAC.2021.35},
  annote =	{Keywords: Fixed-parameter tractability, kernelization, c-closure, weak \gamma-closure, Independent Set, Induced Matching, Connected Vertex Cover, Ramsey numbers, Dominating Set}
}
Document
The PACE 2021 Parameterized Algorithms and Computational Experiments Challenge: Cluster Editing

Authors: Leon Kellerhals, Tomohiro Koana, André Nichterlein, and Philipp Zschoche

Published in: LIPIcs, Volume 214, 16th International Symposium on Parameterized and Exact Computation (IPEC 2021)


Abstract
The Parameterized Algorithms and Computational Experiments challenge (PACE) 2021 was devoted to engineer algorithms solving the NP-hard Cluster Editing problem, also known as Correlation Clustering: Given an undirected graph the task is to compute a minimum number of edges to insert or remove in a way that the resulting graph is a cluster graph, that is, a graph in which each connected component is a clique. Altogether 67 participants from 21 teams, 11 countries, and 3 continents submitted their implementations to the competition. In this report, we describe the setup of the challenge, the selection of benchmark instances, and the ranking of the participating teams. We also briefly discuss the approaches used in the submitted solvers.

Cite as

Leon Kellerhals, Tomohiro Koana, André Nichterlein, and Philipp Zschoche. The PACE 2021 Parameterized Algorithms and Computational Experiments Challenge: Cluster Editing. In 16th International Symposium on Parameterized and Exact Computation (IPEC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 214, pp. 26:1-26:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{kellerhals_et_al:LIPIcs.IPEC.2021.26,
  author =	{Kellerhals, Leon and Koana, Tomohiro and Nichterlein, Andr\'{e} and Zschoche, Philipp},
  title =	{{The PACE 2021 Parameterized Algorithms and Computational Experiments Challenge: Cluster Editing}},
  booktitle =	{16th International Symposium on Parameterized and Exact Computation (IPEC 2021)},
  pages =	{26:1--26:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-216-7},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{214},
  editor =	{Golovach, Petr A. and Zehavi, Meirav},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2021.26},
  URN =		{urn:nbn:de:0030-drops-154096},
  doi =		{10.4230/LIPIcs.IPEC.2021.26},
  annote =	{Keywords: Correlation Clustering, Cluster Editing, Algorithm Engineering, FPT, Kernelization, Heuristics}
}
Document
Binary Matrix Completion Under Diameter Constraints

Authors: Tomohiro Koana, Vincent Froese, and Rolf Niedermeier

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


Abstract
We thoroughly study a novel but basic combinatorial matrix completion problem: Given a binary incomplete matrix, fill in the missing entries so that the resulting matrix has a specified maximum diameter (that is, upper-bounding the maximum Hamming distance between any two rows of the completed matrix) as well as a specified minimum Hamming distance between any two of the matrix rows. This scenario is closely related to consensus string problems as well as to recently studied clustering problems on incomplete data. We obtain an almost complete picture concerning the complexity landscape (P vs NP) regarding the diameter constraints and regarding the number of missing entries per row of the incomplete matrix. We develop polynomial-time algorithms for maximum diameter three, which are based on Deza’s theorem [Discret. Math. 1973, J. Comb. Theory, Ser. B 1974] from extremal set theory. In this way, we also provide one of the rare links between sunflower techniques and stringology. On the negative side, we prove NP-hardness for diameter at least four. For the number of missing entries per row, we show polynomial-time solvability when there is only one missing entry and NP-hardness when there can be at least two missing entries. In general, our algorithms heavily rely on Deza’s theorem and the correspondingly identified sunflower structures pave the way towards solutions based on computing graph factors and solving 2-SAT instances.

Cite as

Tomohiro Koana, Vincent Froese, and Rolf Niedermeier. Binary Matrix Completion Under Diameter Constraints. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 47:1-47:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{koana_et_al:LIPIcs.STACS.2021.47,
  author =	{Koana, Tomohiro and Froese, Vincent and Niedermeier, Rolf},
  title =	{{Binary Matrix Completion Under Diameter Constraints}},
  booktitle =	{38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)},
  pages =	{47:1--47:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-180-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{187},
  editor =	{Bl\"{a}ser, Markus and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021.47},
  URN =		{urn:nbn:de:0030-drops-136925},
  doi =		{10.4230/LIPIcs.STACS.2021.47},
  annote =	{Keywords: sunflowers, binary matrices, Hamming distance, stringology, consensus problems, complexity dichotomy, combinatorial algorithms, graph factors, 2-Sat, Hamming radius}
}
Document
Parameterized Complexity of Geodetic Set

Authors: Leon Kellerhals and Tomohiro Koana

Published in: LIPIcs, Volume 180, 15th International Symposium on Parameterized and Exact Computation (IPEC 2020)


Abstract
A vertex set S of a graph G is geodetic if every vertex of G lies on a shortest path between two vertices in S. Given a graph G and k ∈ ℕ, the NP-hard Geodetic Set problem asks whether there is a geodetic set of size at most k. Complementing various works on Geodetic Set restricted to special graph classes, we initiate a parameterized complexity study of Geodetic Set and show, on the negative side, that Geodetic Set is W[1]-hard when parameterized by feedback vertex number, path-width, and solution size, combined. On the positive side, we develop fixed-parameter algorithms with respect to the feedback edge number, the tree-depth, and the modular-width of the input graph.

Cite as

Leon Kellerhals and Tomohiro Koana. Parameterized Complexity of Geodetic Set. In 15th International Symposium on Parameterized and Exact Computation (IPEC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 180, pp. 20:1-20:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{kellerhals_et_al:LIPIcs.IPEC.2020.20,
  author =	{Kellerhals, Leon and Koana, Tomohiro},
  title =	{{Parameterized Complexity of Geodetic Set}},
  booktitle =	{15th International Symposium on Parameterized and Exact Computation (IPEC 2020)},
  pages =	{20:1--20:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-172-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{180},
  editor =	{Cao, Yixin and Pilipczuk, Marcin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2020.20},
  URN =		{urn:nbn:de:0030-drops-133237},
  doi =		{10.4230/LIPIcs.IPEC.2020.20},
  annote =	{Keywords: NP-hard graph problems, Shortest paths, Tree-likeness, Parameter hierarchy, Data reduction, Integer linear programming}
}
  • Refine by Author
  • 14 Koana, Tomohiro
  • 4 Komusiewicz, Christian
  • 4 Sommer, Frank
  • 3 Kellerhals, Leon
  • 3 Nichterlein, André
  • Show More...

  • Refine by Classification
  • 15 Theory of computation → Parameterized complexity and exact algorithms
  • 8 Theory of computation → Graph algorithms analysis
  • 2 Mathematics of computing → Graph algorithms
  • 2 Theory of computation → Shortest paths
  • 1 Mathematics of computing → Discrete mathematics
  • Show More...

  • Refine by Keyword
  • 3 Fixed-parameter tractability
  • 3 Induced Matching
  • 3 Parameterized Complexity
  • 3 Partial Vertex Cover
  • 3 c-closure
  • Show More...

  • Refine by Type
  • 18 document

  • Refine by Publication Year
  • 4 2020
  • 4 2023
  • 4 2024
  • 3 2021
  • 3 2022

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