Language：Japanese   Publisher：一般社団法人 人工知能学会  

DOI： 10.11517/jsaifpai.131.0_31

CiNii Research

Publisher：Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)  

We propose a new model for graph editing problems on intersection graphs. In well-studied graph editing problems, adding and deleting vertices and edges are used as graph editing operations. As a graph editing operation on intersection graphs, we propose moving objects corresponding to vertices. In this paper, we focus on interval graphs as an intersection graph. We give a linear-time algorithm to find the total moving distance for transforming an interval graph into a complete graph. The concept of this algorithm can be applied for (i) transforming a unit square graph into a complete graph over L1 distance and (ii) attaining the existence of a k-clique on unit interval graphs. In addition, we provide LP-formulations to achieve several properties in the associated graph of unit intervals.

DOI： 10.1007/978-981-97-7752-5_5

Scopus

Publisher：Theoretical Computer Science  

K-best enumeration, which asks to output k-best solutions without duplication, is a helpful tool in data analysis for many fields. In such fields, graphs typically represent data. Thus subgraph enumeration has been paid much attention to such fields. However, k-best enumeration tends to be intractable since, in many cases, finding one optimum solution is NP-hard. To overcome this difficulty, we combine k-best enumeration with a concept of enumeration algorithms called approximation enumeration algorithms. As a main result, we propose a 4-approximation algorithm for minimal connected edge dominating sets which outputs k minimal solutions with cardinality at most 4⋅OPT‾, where OPT‾ is the cardinality of a minimum solution which is not outputted by the algorithm. Our proposed algorithm runs in O(nm2Δ) delay, where n, m, Δ are the number of vertices, the number of edges, and the maximum degree of an input graph.

DOI： 10.1016/j.tcs.2024.114628

Web of Science

Scopus

Publisher：Information Processing Letters  

Enumeration problems are often encountered as key subroutines in the exact computation of graph parameters such as chromatic number, treewidth, or treedepth. In the case of treedepth computation, the enumeration of inclusion-wise minimal separators plays a crucial role. However and quite surprisingly, the complexity status of this problem has not been settled since it has been posed as an open direction by Kloks and Kratsch in 1998. Recently at the PACE 2020 competition dedicated to treedepth computation, solvers have been circumventing that by listing all minimal a-b separators and filtering out those that are not inclusion-wise minimal, at the cost of efficiency. Naturally, having an efficient algorithm for listing inclusion-wise minimal separators would drastically improve such practical algorithms. In this note, however, we show that no efficient algorithm is to be expected from an output-sensitive perspective, namely, we prove that there is no output-polynomial time algorithm for inclusion-wise minimal separators enumeration unless P=NP.

DOI： 10.1016/j.ipl.2023.106469

Web of Science

Scopus

Publisher：Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)  

The problem of determining whether a graph G contains another graph H as a minor, referred to as the minor containment problem, is a fundamental problem in the field of graph algorithms. While it is -complete when G and H are general graphs, it is sometimes tractable on more restricted graph classes. This study focuses on the case where both G and H are trees, known as the tree minor containment problem. Even in this case, the problem is known to be -complete. In contrast, polynomial-time algorithms are known for the case when both trees are caterpillars or when the maximum degree of H is a constant. Our research aims to clarify the boundary of tractability and intractability for the tree minor containment problem. Specifically, we provide dichotomies for the computational complexities of the problem based on three structural parameters: the diameter, pathwidth, and path eccentricity.

DOI： 10.1007/978-981-97-0566-5_28

Web of Science

Scopus

DOI： 10.1007/978-3-031-63021-7_18

Web of Science

Language：Japanese   Publisher：一般社団法人 人工知能学会  

DOI： 10.11517/jsaifpai.126.0_39

CiNii Research

Language：English   Publisher：The Institute of Electronics, Information and Communication Engineers  

<p>We are given a set <i>S</i> of <i>n</i> points in the Euclidean plane. We assume that <i>S</i> is in general position. A simple polygon <i>P</i> is an <i>empty polygon</i> of <i>S</i> if each vertex of <i>P</i> is a point in <i>S</i> and every point in <i>S</i> is either outside <i>P</i> or a vertex of <i>P</i>. In this paper, we consider the problem of enumerating all the empty polygons of a given point set. To design an efficient enumeration algorithm, we use a reverse search by Avis and Fukuda with child lists. We propose an algorithm that enumerates all the empty polygons of <i>S</i> in <i>O</i>(<i>n</i>²|<i>ε</i>(<i>S</i>)|)-time, where <i>ε</i>(<i>S</i>) is the set of empty polygons of <i>S</i>. Moreover, by applying the same idea to the problem of enumerating surrounding polygons of a given point set <i>S</i>, we propose an enumeration algorithm that enumerates them in <i>O</i>(<i>n</i>²)-delay, while the known algorithm enumerates in <i>O</i>(<i>n</i>² log <i>n</i>)-delay, where a <i>surroundingpolygon</i> of <i>S</i> is a polygon such that each vertex of the polygon is a point in <i>S</i> and every point in <i>S</i> is either inside the polygon or a vertex of the polygon.</p>

DOI： 10.1587/transfun.2022dmp0007

Web of Science

Scopus

CiNii Research

Publisher：Leibniz International Proceedings in Informatics, LIPIcs  

Finding a maximum cardinality common independent set in two matroids (also known as Matroid Intersection) is a classical combinatorial optimization problem, which generalizes several well-known problems, such as finding a maximum bipartite matching, a maximum colorful forest, and an arborescence in directed graphs. Enumerating all maximal common independent sets in two (or more) matroids is a classical enumeration problem. In this paper, we address an “intersection” of these problems: Given two matroids and a threshold τ, the goal is to enumerate all maximal common independent sets in the matroids with cardinality at least τ. We show that this problem can be solved in polynomial delay and polynomial space. We also discuss how to enumerate all maximal common independent sets of two matroids in non-increasing order of their cardinalities.

DOI： 10.4230/LIPIcs.MFCS.2023.58

Scopus

Publisher：Leibniz International Proceedings in Informatics, LIPIcs  

LZ-End is a variant of the well-known Lempel-Ziv parsing family such that each phrase of the parsing has a previous occurrence, with the additional constraint that the previous occurrence must end at the end of a previous phrase. LZ-End was initially proposed as a greedy parsing, where each phrase is determined greedily from left to right, as the longest factor that satisfies the above constraint [Kreft & Navarro, 2010]. In this work, we consider an optimal LZ-End parsing that has the minimum number of phrases in such parsings. We show that a decision version of computing the optimal LZ-End parsing is NP-complete by showing a reduction from the vertex cover problem. Moreover, we give a MAX-SAT formulation for the optimal LZ-End parsing adapting an approach for computing various NP-hard repetitiveness measures recently presented by [Bannai et al., 2022]. We also consider the approximation ratio of the size of greedy LZ-End parsing to the size of the optimal LZ-End parsing, and give a lower bound of the ratio which asymptotically approaches 2.

DOI： 10.4230/LIPIcs.CPM.2023.3

Scopus

Authorship：Lead author   Language：English   Publishing type：Research paper (international conference proceedings)  

Publisher：Proceedings of the 36th AAAI Conference on Artificial Intelligence, AAAI 2022  

Finding diverse solutions in combinatorial problems recently has received considerable attention (Baste et al. 2020; Fomin et al. 2020; Hanaka et al. 2021). In this paper we study the following type of problems: given an integer k, the problem asks for k solutions such that the sum of pairwise (weighted) Hamming distances between these solutions is maximized. Such solutions are called diverse solutions. We present a polynomial-time algorithm for finding diverse shortest stpaths in weighted directed graphs. Moreover, we study the diverse version of other classical combinatorial problems such as diverse weighted matroid bases, diverse weighted arborescences, and diverse bipartite matchings. We show that these problems can be solved in polynomial time as well. To evaluate the practical performance of our algorithm for finding diverse shortest st-paths, we conduct a computational experiment with synthetic and real-world instances. The experiment shows that our algorithm successfully computes diverse solutions within reasonable computational time.

Scopus

Language：English   Publishing type：Research paper (scientific journal)  

DOI： 10.1016/j.tcs.2022.04.048

Authorship：Lead author   Language：English   Publishing type：Research paper (international conference proceedings)  

DOI： 10.1145/3517804.3524148

Language：Japanese   Publisher：Theory of Computing Systems  

A cactus is a connected graph that does not contain K4 − e as a minor. Given a graph G = (V,E) and an integer k ≥ 0, Cactus Vertex Deletion (also known as Diamond Hitting Set) is the problem of deciding whether G has a vertex set of size at most k whose removal leaves a forest of cacti. The previously best deterministic parameterized algorithm for this problem was due to Bonnet et al. [WG 2016], which runs in time 26knO(1), where n is the number of vertices of G. In this paper, we design a deterministic algorithm for Cactus Vertex Deletion, which runs in time 17.64knO(1). As an almost straightforward application of our algorithm, we also give a deterministic 17.64knO(1)-time algorithm for Even Cycle Transversal, which improves the previous running time 50knO(1) of the known deterministic parameterized algorithm due to Misra et al. [WG 2012].

DOI： 10.1007/s00224-022-10076-x

Web of Science

Scopus

Language：Japanese   Publisher：Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)  

Enumerating matchings is a classical problem in the field of enumeration algorithms. There are polynomial-delay enumeration algorithms for several settings, such as enumerating perfect matchings, maximal matchings, and (weighted) matchings in specific orders. In this paper, we present polynomial-delay enumeration algorithms for maximal matchings with cardinality at least given threshold t. Our algorithm enumerates all such matchings in O(nm) delay with exponential space, where n and m are the number of vertices and edges of an input graph, respectively. We also present a polynomial-delay and polynomial-space enumeration algorithm for this problem. As a variant of this algorithm, we give an algorithm that enumerates k-best maximal matchings that runs in polynomial-delay.

DOI： 10.1007/978-3-031-15914-5_25

Web of Science

Scopus

Language：English   Publishing type：Research paper (international conference proceedings)  

DOI： 10.1609/aaai.v36i4.20290

Language：Japanese   Publisher：一般社団法人 人工知能学会  

DOI： 10.11517/jsaifpai.119.0_21

CiNii Research

CiNii Research