Known Algorithms for Edge Clique Cover are Probably Optimal

DOI10.1137/130947076zbMath1329.05216arXiv1203.1754OpenAlexW2496893526MaRDI QIDQ3464061

Marek Cygan, Michał Pilipczuk, Marcin Pilipczuk

Publication date: 20 January 2016

Published in: SIAM Journal on Computing, Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1203.1754

zbMATH Keywords

parameterized complexityexponential time hypothesiskernelizationedge clique cover

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (20)

An overview of graph covering and partitioning ⋮ Compressed cliques graphs, clique coverings and positive zero forcing ⋮ Computational complexity of distance edge labeling ⋮ Known Algorithms for Edge Clique Cover are Probably Optimal ⋮ A Subexponential Parameterized Algorithm for Directed Subset Traveling Salesman Problem on Planar Graphs ⋮ Finding optimal triangulations parameterized by edge clique cover ⋮ On the intractability landscape of digraph intersection representations ⋮ The graph motif problem parameterized by the structure of the input graph ⋮ Parameterized analysis and crossing minimization problems ⋮ Edge-clique covers of the tensor product ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Positive Zero Forcing and Edge Clique Coverings ⋮ On the kernel size of clique cover reductions for random intersection graphs ⋮ Complexity of Grundy coloring and its variants ⋮ On the complete width and edge clique cover problems ⋮ Large-scale clique cover of real-world networks ⋮ Unnamed Item ⋮ On some FPT problems without polynomial Turing compressions ⋮ Tight Lower Bounds for List Edge Coloring

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A \(9k\) kernel for nonseparating independent set in planar graphs
• Lower bounds for kernelizations and other preprocessing procedures
• Applications of edge coverings by cliques
• Strong computational lower bounds via parameterized complexity
• Algorithms for compact letter displays: comparison and evaluation
• On problems without polynomial kernels
• On a clique covering problem of Orlin
• Linear time algorithms on circular-arc graphs
• Can visibility graphs be represented compactly?
• Which problems have strongly exponential complexity?
• Efficiently covering complex networks with cliques of similar vertices
• Bipartite structure of all complex networks
• On the computational hardness based on linear fpt-reductions
• Tight lower bounds for certain parameterized NP-hard problems
• What’s Next? Future Directions in Parameterized Complexity
• Clique Cover and Graph Separation
• Hypergraph Partitioning-Based Fill-Reducing Ordering for Symmetric Matrices
• New Limits to Classical and Quantum Instance Compression
• Known Algorithms for Edge Clique Cover are Probably Optimal
• Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size
• The Complexity of Satisfiability of Small Depth Circuits
• Covering edges by cliques with regard to keyword conflicts and intersection graphs
• On the hardness of approximating minimization problems
• Fast Hamiltonicity Checking Via Bases of Perfect Matchings
• On Problems as Hard as CNF-SAT
• Almost Optimal Lower Bounds for Problems Parameterized by Clique-Width
• Data Reduction, Exact, and Heuristic Algorithms for Clique Cover
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses
• The Representation of a Graph by Set Intersections
• Confluence in Data Reduction: Bridging Graph Transformation and Kernelization
• On the complexity of \(k\)-SAT

This page was built for publication: Known Algorithms for Edge Clique Cover are Probably Optimal