On Generating Triangle-Free Graphs

doi:10.1016/j.endm.2009.02.008

Electronic Notes in Discrete Mathematics

Volume 32, 15 March 2009, Pages 51-58

https://doi.org/10.1016/j.endm.2009.02.008 Get rights and content

Abstract

We show that the problem to decide whether a graph can be made triangle-free with at most k edge deletions remains NP-complete even when restricted to planar graphs of maximum degree seven. In addition, we provide polynomial-time data reduction rules for this problem and obtain problem kernels consisting of 6k vertices for general graphs and 11k/3 vertices for planar graphs.

References (9)

J. Guo et al.
Invitation to data reduction and problem kernelization
ACM SIGACT News
(2007)
F.N. Abu-Khzam
Kernelization algorithms for d-hitting set problems
N. Alon et al.
Finding and counting given length cycles
Algorithmica
(1997)
J. Gramm et al.
Automated generation of search tree algorithms for hard graph modification problems
Algorithmica
(2004)

There are more references available in the full text version of this article.

Cited by (37)

A survey of parameterized algorithms and the complexity of edge modification
2023, Computer Science Review
The survey is a comprehensive overview of the developing area of parameterized algorithms for graph modification problems. It describes state of the art in kernelization, subexponential algorithms, and parameterized complexity of graph modification. The main focus is on edge modification problems, where the task is to change some adjacencies in a graph to satisfy some required properties. To facilitate further research, we list many open problems in the area.
Feedback edge sets in temporal graphs
2022, Discrete Applied Mathematics
The classical, linear-time solvable Feedback Edge Set problem is concerned with finding a minimum number of edges intersecting all cycles in a (static, unweighted) graph. We provide a first study of this problem in the setting of temporal graphs, where edges are present only at certain points in time. We find that there are four natural generalizations of Feedback Edge Set, all of which turn out to be NP-hard. We also study the tractability of these problems with respect to several parameters (solution size, lifetime, and number of graph vertices, among others) and obtain some parameterized hardness but also fixed-parameter tractability results.
Kernel for K<inf>t</inf>-FREE EDGE DELETION
2021, Information Processing Letters
The parameterized complexity and kernelization of resilience for database queries
2020, Theoretical Computer Science
Given a database instance and a query on it whose result is initially non-empty, the resilience decision problem is to decide if there exist a small enough number of facts in the database instance such that the deletion of these facts empties the result of the given query. In this paper, we revisit the resilience decision problem. We investigate the parameterized complexity for various classes of database queries. We consider the factors including the query size and the number of variables, and present several intractable cases even from the perspective of parameterized complexity. Meanwhile, we refine the characteristics of resilience for self-join-free conjunctive queries containing triads, and show that it is still NP-hard even if the structure of the input database instance is simple. This result implies the hardness essentially comes from the parity of triangle sequence instead of the complicate (non-planar) intersections of cycles. On the other hand, we also obtain some positive results showing that the resilience decision problem is still fixed parameter tractable for an important case through kernelization. Our work demonstrates a new insight for employing resilience computation in database operations.
New kernels for several problems on planar graphs
2020, Theoretical Computer Science
In this paper, we study the kernelization of the Induced Matching problem on planar graphs, the Parameterized Planar 4-Cycle Transversal problem and the Parameterized Planar Edge-Disjoint 4-Cycle Packing problem. For the Induced Matching problem on planar graphs, based on the Gallai-Edmonds decomposition structure, a kernel of size 26k is presented, which improves the previous best result 28k. For the Parameterized Planar 4-Cycle Transversal problem, by partitioning the vertices in a given instance into several parts and analyzing the size of each part independently, a kernel with at most $51 k - 22$ vertices is obtained, which improves the previous best result 74k. Based on the kernelization process of the Parameterized Planar 4-Cycle Transversal problem, a kernel of size $51 k - 22$ can also be obtained for the Parameterized Planar Edge-Disjoint 4-Cycle Packing problem, which improves the previous best result 96k.
Triangle edge deletion on planar glasses-free RGB-digraphs
2019, Theoretical Computer Science
Citation Excerpt :
In this paper, we revisit the problem to break all triangles of a given graph by minimizing edge deletions. Triangle edge deletion problem is a variant of feedback arc set problem (refer to [2,4,5]), and it can be formally stated as follows. We have the following observations on RGB-digraphs,
In this paper, we revisit the triangle edge deletion problem a variant of feedback arc set problem which is one of the Karp's 21 NP-complete problems. Given a graph $G (V, E)$ , it is to find the edge set F such that $| F | \leq k$ and $G^{'} (V, E ∖ F)$ is a triangle-free graph. Yannakakis [1] showed it is hard for simple digraphs as well. The latest results showed that triangle edge deletion problem is still hard even for (a) planar undirected graphs of maximum degree seven [2] and (b) RGB-digraphs [3] which is a special class of digraphs. To make a further step, we show a new result in this paper that triangle edge deletion problem is still NP-complete even for planar RGB-digraphs of maximum degree eight with no glasses. On the other hand, we can find a kernel consisting of $11 k / 3$ vertices for planar RGB-digraphs with no glasses. The results have an interesting application for the derivation of a tighter dichotomy on resilience decision problem in database theory.

View all citing articles on Scopus

¹: Student of the Carl-Zeiss-Gymnasium Jena, Erich-Kuithan-Str. 7, D-07743 Jena.

²: Supported by a PhD fellowship of the Carl-Zeiss-Stiftung.

³: Supported by the Deutsche Forschungsgemeinschaft, project AREG, NI 369/9.

View full text

On Generating Triangle-Free Graphs

Abstract

ACM SIGACT News

Kernelization algorithms for d-hitting set problems

Finding and counting given length cycles

Algorithmica

Automated generation of search tree algorithms for hard graph modification problems

Algorithmica