記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

In this paper, we study a type of incremental optimization variant of the Maximum Independent Set problem (MaxIS), called Bounded-Deletion Maximum Independent Set problem (BD-MaxIS): Given an unweighted graph (formula presented), an initial feasible solution (i.e., an independent set), and a non-negative integer k, the objective of BD-MaxIS is to find an independent set such that and |S| is maximized. The original MaxIS is generally NP-hard, but, it can be solved in polynomial time for perfect graphs (and therefore, comparability, co-comparability, bipartite, chordal, and interval graphs). In this paper, we show that BD-MaxIS is NP-hard even if the input is restricted to bipartite graphs, and hence to comparability graphs. On the other hand, fortunately, BD-MaxIS on co-comparability, interval, convex bipartite, and chordal graphs can be solved in polynomial time. Finally, we study the computational complexity on very similar variants of the Minimum Vertex Cover and the Maximum Clique problems for graph subclasses.

DOI： 10.1007/978-3-031-30448-4_4

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85161382364&origin=inward

担当区分：最終著者   記述言語：英語   掲載種別：研究論文（学術雑誌）

This paper studies generalized variants of the maximum independent set problem, called the Maximum Distance-d Independent Set problem (MaxDdIS for short). For an integer d ≥ 2, a distance-d independent set of an unweighted graph G = (V, E) is a subset S ⊆ V of vertices such that for any pair of vertices u, v ∈ S, the number of edges in any path between u and v is at least d in G. Given an unweighted graph G, the goal of MaxDdIS is to find a maximum-cardinality distance-d independent set of G. In this paper, we analyze the (in)approximability of the problem on r-regular graphs (r ≥ 3) and planar graphs, as follows: (1) For every fixed integers d ≥ 3 and r ≥ 3, MaxDdIS on r-regular graphs is APX-hard. (2) We design polynomial-time O(r d-1)-approximation and O(r d-2|d)-approximation algorithms for MaxDdIS on r-regular graphs. (3) We sharpen the above O(r d-2|d)-approximation algorithms when restricted to d = r = 3, and give a polynomial-time 2-approximation algorithm for MaxD3IS on cubic graphs. (4) Finally, we show that MaxDdIS admits a polynomial-time approximation scheme (PTAS) for planar graphs.

DOI： 10.1587/transfun.2021DMP0017

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85138237602&origin=inward

担当区分：最終著者   記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

We study the problem of checking the existence of a step-by-step transformation of d-regular induced subgraphs in a graph, where d≥ 0 and each step in the transformation must follow a fixed reconfiguration rule. Our problem for d= 0 is equivalent to Independent Set Reconfiguration, which is one of the most well-studied reconfiguration problems. In this paper, we systematically investigate the complexity of the problem, in particular, on chordal graphs and bipartite graphs. Our results give interesting contrasts to known ones for Independent Set Reconfiguration.

DOI： 10.1007/978-3-030-96731-4_4

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85127912089&origin=inward

担当区分：最終著者   記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

In this paper, we investigate the complexity of the Maximum Happy Set problem on subclasses of co-comparability graphs. For a graph G and its vertex subset S, a vertex v∈ S is happy if all v’s neighbors in G are contained in S. Given a graph G and a non-negative integer k, Maximum Happy Set is the problem of finding a vertex subset S of G such that | S| = k and the number of happy vertices in S is maximized. In this paper, we first show that Maximum Happy Set is NP-hard even for co-bipartite graphs. We then give an algorithm for n-vertex interval graphs whose running time is O(k2n2); this improves the best known running time O(kn8) for interval graphs. We also design an algorithm for n-vertex permutation graphs whose running time is O(k3n2). These two algorithmic results provide a nice contrast to the fact that Maximum Happy Set remains NP-hard for chordal graphs, comparability graphs, and co-comparability graphs.

DOI： 10.1007/978-3-030-96731-4_13

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85127916934&origin=inward

担当区分：最終著者   記述言語：英語   掲載種別：研究論文（学術雑誌）

In this paper we study the parameterized complexity for the MAXIMUM HAPPY SET problem (MaxHS): For an undirected graph G=(V,E) and a subset S⊆V of vertices, a vertex v is happy if v and all its neighbors are in S; otherwise unhappy. Given an undirected graph G=(V,E) and an integer k, the goal of MaxHS is to find a subset S⊆V of k vertices such that the number of happy vertices is maximized. In this paper we first show that MaxHS is W[1]-hard with respect to k even if the input graph is a split graph. Then, we prove the fixed-parameter tractability of MaxHS when parameterized by tree-width, by clique-width plus k, by neighborhood diversity, or by cluster deletion number.

DOI： 10.1016/j.dam.2021.07.005

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85111074192&origin=inward

担当区分：最終著者   記述言語：英語   掲載種別：研究論文（学術雑誌）

The cut-set ∂(S) of a graph G= (V, E) is the set of edges that have one endpoint in S⊂ V and the other endpoint in V\ S, and whenever G[S] is connected, the cut [S, V\ S] of G is called a connected cut. A bond of a graph G is an inclusion-wise minimal disconnecting set of G, i.e., bonds are cut-sets that determine cuts [S, V\ S] of G such that G[S] and G[V\ S] are both connected. Contrasting with a large number of studies related to maximum cuts, there exist very few results regarding the largest bond of general graphs. In this paper, we aim to reduce this gap on the complexity of computing the largest bond, and the maximum connected cut of a graph. Although cuts and bonds are similar, we remark that computing the largest bond and the maximum connected cut of a graph tends to be harder than computing its maximum cut. We show that it does not exist a constant-factor approximation algorithm to compute the largest bond, unless P=NP. Also, we show that Largest Bond and Maximum Connected Cut are NP-hard even for planar bipartite graphs, whereas Maximum Cut is trivial on bipartite graphs and polynomial-time solvable on planar graphs. In addition, we show that Largest Bond and Maximum Connected Cut are NP-hard on split graphs, and restricted to graphs of clique-width w they can not be solved in time f(w) no(w) unless the Exponential Time Hypothesis fails, but they can be solved in time f(w) nO(w). Finally, we show that both problems are fixed-parameter tractable when parameterized by the size of the solution, the treewidth, and the twin-cover number.

DOI： 10.1007/s00453-020-00789-1

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85099220213&origin=inward

担当区分：最終著者   記述言語：英語   掲載種別：研究論文（学術雑誌）

In this paper we study the approximability of the MAXIMUM HAPPY SET problem (MaxHS) and the computational complexity of MaxHS on graph classes: For an undirected graph G=(V,E) and a subset S⊆V of vertices, a vertex v is happy if v and all its neighbors are in S; otherwise unhappy. Given an undirected graph G=(V,E) and an integer k, the goal of MaxHS is to find a subset S⊆V of k vertices such that the number of happy vertices is maximized. MaxHS is known to be NP-hard. In this paper, we design a (2Δ+1)-approximation algorithm for MaxHS on graphs with maximum degree Δ. Next, we show that the approximation ratio can be improved to Δ if the maximum degree Δ of the input graph is a constant. Then, we show that MaxHS can be solved in polynomial time if the input graph is restricted to block graphs, or interval graphs. We prove nevertheless that MaxHS on bipartite graphs or on cubic graphs remains NP-hard.

DOI： 10.1016/j.tcs.2021.03.023

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85103285503&origin=inward

担当区分：最終著者   記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

In this paper we introduce the Maximum Happy Set problem (MaxHS) and study its parameterized complexity: For an undirected graph G = (V,E) and a subset S ⊆ V of vertices, a vertex v is happy if v and all its neighbors are in S; and otherwise unhappy. Given an undirected graph G = (V,E) and an integer k, the goal of MaxHS is to find a subset S ⊆ V of k vertices such that the number of happy vertices is maximized. In this paper we first show that MaxHS is W[1]-hard when parameterized by k. Then, we prove the fixed-parameter tractability of MaxHS when parameterized by the tree-width, the clique-width and k, the neighborhood diversity, or the twin-cover number.

DOI： 10.1007/978-3-030-39881-1_27

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85080915754&origin=inward

担当区分：最終著者   記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

In this paper we study the approximability of the Maximum Happy Set problem (MaxHS) and the computational complexity of MaxHS on graph classes: For an undirected graph and a subset of vertices, a vertex v is happy if v and all its neighbors are in S; otherwise unhappy. Given an undirected graph and an integer k, the goal of MaxHS is to find a subset of k vertices such that the number of happy vertices is maximized. MaxHS is known to be NP-hard. In this paper, we design a-approximation algorithm for MaxHS on graphs with maximum degree. Next, we show that the approximation ratio can be improved to if the input is a connected graph and its maximum degree is a constant. Then, we show that MaxHS can be solved in polynomial time if the input graph is restricted to proper interval graphs, or block graphs. We prove nevertheless that MaxHS remains NP-hard even for bipartite graphs or for cubic graphs.

DOI： 10.1007/978-3-030-58150-3_27

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85091112536&origin=inward

担当区分：最終著者   記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

We study two variants of Maximum Cut, which we call Connected Maximum Cut and Maximum Minimal Cut, in this paper. In these problems, given an unweighted graph, the goal is to compute a maximum cut satisfying some connectivity requirements. Both problems are known to be NP-complete even on planar graphs whereas Maximum Cut on planar graphs is solvable in polynomial time. We first show that these problems are NP-complete even on planar bipartite graphs and split graphs. Then we give parameterized algorithms using graph parameters such as clique-width, tree-width, and twin-cover number. Finally, we obtain FPT algorithms with respect to the solution size.

DOI： 10.4230/LIPIcs.IPEC.2019.13

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85077468897&origin=inward

担当区分：筆頭著者,　最終著者   記述言語：英語   掲載種別：研究論文（学術雑誌）

In this paper, we study a variant of the Minimum Dominating Set problem. Given an unweighted undirected graph G = (V, E) of n = |V| vertices, the goal of the Minimum Single Dominating Cycle problem (MinSDC) is to find a single shortest cycle which dominates all vertices, i.e., a cycle C such that for the set V(C) of vertices in C and the set N(V(C)) of neighbor vertices of C, V(G) = V(C) ∪ N(V(C)) and |V(C)| is minimum over all dominating cycles in G [6], [17], [24]. In this paper we consider the (in)approximability of MinSDC if input graphs are restricted to some special classes of graphs. We first show that MinSDC is still NP-hard to approximate even when restricted to planar, bipartite, chordal, or r-regular (r ≥ 3). Then, we show the (ln n + 1)-approximability and the (1 - ϵ) ln n-inapproximability of MinSDC on split graphs under P ≠ NP. Furthermore, we explicitly design a linear-time algorithm to solve MinSDC for graphs with bounded treewidth and estimate the hidden constant factor of its running time-bound.

DOI： 10.1587/transinf.2017FCP0007

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85042631622&origin=inward

担当区分：最終著者   記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

For an integer d ≥ 2, a distance-d independent set of an unweighted graph G = (V,E) is a subset S ⊆ V of vertices such that for any pair of vertices u, v ∈ S, the number of edges in any path between u and v is at least d in G. Given an unweighted graph G, the goal of Maximum Distance-d Independent Set problem (MaxDdIS) is to find a maximum-cardinality distance-d independent set of G. In this paper we focus on MaxD3IS on cubic (3-regular) graphs. For every fixed integer d ≥ 3, MaxDdIS is NP-hard even for planar bipartite graphs of maximum degree three. Furthermore, when d = 3, it is known that there exists no σ-approximation algorithm for MaxD3IS oncubic graphs for constant σ < 1. 00105. On the other hand, the previously best approximation ratio known for MaxD3IS on cubic graphs is 2. In this paper, we improve the approximation ratio into 1.875 for MaxD3IS on cubic graphs.

DOI： 10.1007/978-3-319-53925-6_18

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85014231181&origin=inward

担当区分：最終著者,　責任著者   記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

This paper studies generalized variants of the maximum independent set problem, called the Maximum Distance-d Independent Set problem (MaxDdIS for short). For an integer d ≥ 2, a distance-d independent set of an unweighted graph G = (V,E) is a subset S ⊆ V of vertices such that for any pair of vertices u, v ∈ S, the number of edges in any path between u and v is at least d in G. Given an unweighted graph G, the goal of MaxDdIS is to find a maximum-cardinality distance-d independent set of G. In this paper, we analyze the (in)approximability of the problem on r-regular graphs (r ≥ 3) and planar graphs, as follows: (1) For every fixed integers d ≥ 3 and r ≥ 3, MaxDdIS on r-regular graphs is APX-hard. (2) We design polynomial-time O(rd−1)-approximation and O(rd−2/d)- approximation algorithms for MaxDdIS on r-regular graphs. (3) We sharpen the above O(rd−2/d)-approximation algorithms when restricted to d = r = 3, and give a polynomial-time 2-approximation algorithm for MaxD3IS on cubic graphs. (4) Finally, we show that MaxDdIS admits a polynomial-time approximation scheme (PTAS) for planar graphs.

DOI： 10.1007/978-3-319-48749-6_20

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85007188790&origin=inward

担当区分：筆頭著者,　最終著者,　責任著者   記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

The paper studies a generalization of the Independent Set problem (IS for short). A distance- d independent set for an integer d≥2 in an unweighted graph G = (V, E) is a subset S⊂ V of vertices such that for any pair of vertices u, v εS, the distance between u and v is at least d in G. Given an unweighted graph G and a positive integer k, the Distance- d Independent Set problem (D d IS for short) is to decide whether G contains a distance- d independent set S such that |S| ≥k. D2IS is identical to the original IS. Thus D2IS is \mathcal{NP} -complete even for planar graphs, but it is in \mathcal{P} for bipartite graphs and chordal graphs. In this paper we investigate the computational complexity of D d IS, its maximization version MaxD d IS, and its parameterized version ParaD d IS(k), where the parameter is the size of the distance- d independent set: (1) We first prove that for any ε >0 and any fixed integer d≥3, it is \mathcal{NP} -hard to approximate MaxD d IS to within a factor of n1/2- for bipartite graphs of n vertices, and for any fixed integer d≥3, ParaD d IS(k) is \mathcal{W}[1] -hard for bipartite graphs. Then, (2) we prove that for every fixed integer d≥3, D d IS remains NP -complete even for planar bipartite graphs of maximum degree three. Furthermore, (3) we show that if the input graph is restricted to chordal graphs, then D d IS can be solved in polynomial time for any even d≥2, whereas D d IS is NP -complete for any odd d≥3. Also, we show the hardness of approximation of MaxD d IS and the W[1] -hardness of ParaD d IS(k) on chordal graphs for any odd d≥3. © 2013 Springer Science+Business Media New York.

DOI： 10.1007/s10878-012-9594-4

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84893764641&origin=inward

担当区分：筆頭著者,　最終著者,　責任著者   記述言語：英語   掲載種別：研究論文（学術雑誌）

We study the problem of finding a maximum vertex-subset S of a given graph G such that the subgraph G[S] induced by S is r-regular for a prescribed degree r ≥ 0. We also consider a variant of the problem which requires G[. S] to be r-regular and connected. Both problems are known to be NP-hard even to approximate for a fixed constant r. In this paper, we thus consider the problems whose input graphs are restricted to some special classes of graphs. We first show that the problems are still NP-hard to approximate even if r is a fixed constant and the input graph is either bipartite or planar. On the other hand, both problems are tractable for graphs having tree-like structures, as follows. We give linear-time algorithms to solve the problems for graphs with bounded treewidth; we note that the hidden constant factor of our running time is just a single exponential of the treewidth. Furthermore, both problems are solvable in polynomial time for chordal graphs.

DOI： 10.1016/j.tcs.2014.07.008

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84926407099&origin=inward

担当区分：筆頭著者,　最終著者,　責任著者   記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

We study the problem of finding a maximum vertex-subset S of a given graph G such that the subgraph G[S] induced by S is r-regular for a prescribed degree r ≥ 0. We also consider a variant of the problem which requires G[S] to be r-regular and connected. Both problems are known to be NP-hard even to approximate for a fixed constant r. In this paper, we thus consider the problems whose input graphs are restricted to some special classes of graphs. We first show that the problems are still NP-hard to approximate even if r is a fixed constant and the input graph is either bipartite or planar. On the other hand, both problems are tractable for graphs having tree-like structures, as follows. We give linear-time algorithms to solve the problems for graphs with bounded treewidth; we note that the hidden constant factor of our running time is just a single exponential of the treewidth. Furthermore, both problems are solvable in polynomial time for chordal graphs. © 2013 Springer-Verlag.

DOI： 10.1007/978-3-642-40164-0_6

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84883179628&origin=inward

担当区分：筆頭著者,　最終著者,　責任著者   記述言語：英語   掲載種別：研究論文（学術雑誌）

Given a connected graph G = (V, E) on n vertices, the Maximum r-Regular Induced Connected Subgraph (r-MaxRICS) problem asks for a maximum sized subset of vertices S ⊆ V such that the induced subgraph G[S] on S is connected and r-regular. It is known that 2-MaxRICS and 3-MaxRICS are NP-hard. Moreover, 2-MaxRICS cannot be approximated within a factor of n1-ε in polynomial time for any ε > 0 unless P = NP. In this paper, we show that r-MaxRICS are NP-hard for any fixed integer r ≥ 4. Furthermore, we show that for any fixed integer r ≥ 3, r-MaxRICS cannot be approximated within a factor of n1/6-ε in polynomial time for any ε > 0 unless P = NP. Copyright © 2013 The Institute of Electronics, Information and Communication Engineers.

DOI： 10.1587/transinf.E96.D.443

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84878238046&origin=inward

担当区分：筆頭著者,　最終著者,　責任著者   記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）

The paper studies a generalization of the Independent Set (IS) problem. A distance-d independent set for a positive integer d ≥ 2 in an unweighted graph G = (V, E) is a set S ⊆ V of vertices such that for any pair of vertices u, v ∈ S, the distance between u and v is at least d in G. Given an unweighted graph G and a positive integer k, the Distance- d Independent Set (D d IS) problem is to decide whether G contains a distance-d independent set S such that |S| ≥ k. D2IS is identical to the original IS and thus D2IS is in for bipartite graphs and chordal graphs. In this paper, we show that for every fixed integer d ≥ 3, D d IS is -complete even for planar bipartite graphs of maximum degree three, and also -complete even for chordal bipartite graphs. Furthermore, we show that if the input graph is restricted to chordal graphs, then D d IS can be solved in polynomial time for any even d ≥ 2, whereas D d IS is -complete for any odd d ≥ 3. © 2012 Springer-Verlag.

DOI： 10.1007/978-3-642-31770-5_21

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84865023969&origin=inward