Search
Search Results
-
Maximum Cut on Interval Graphs of Interval Count Four is NP-Complete
The computational complexity of the MaxCut problem restricted to interval graphs has been open since the 80’s, being one of the problems proposed by...
-
Decidability of NP-Complete Problems
An analysis of the undecidability of Diophantine equations showed that problems of recognition of the properties of the NP class are decidable, i.e.,...
-
Recognition of Seifert fibered spaces with boundary is in NP
We show that the decision problem of recognising whether a triangulated 3-manifold admits a Seifert fibered structure with non-empty boundary is in...
-
Cutting Barnette Graphs Perfectly is Hard
A perfect matching cut is a perfect matching that is also a cutset, or equivalently a perfect matching containing an even number of edges on every...
-
Complexity of Maximum Cut on Interval Graphs
We resolve the longstanding open problem concerning the computational complexity of MaxCut on interval graphs by showing that it is NP-complete.
-
On the Power of Counting the Total Number of Computation Paths of NPTMs
In this paper, we define and study variants of several complexity classes of decision problems that are defined via some criteria on the number of...
-
Computation of Grundy dominating sequences in (co-)bipartite graphs
A sequence S of vertices of a graph G is called a dominating sequence of G if (1) each vertex v of S dominates a vertex of G that was not dominated...
-
On penalized reload cost path, walk, tour and maximum flow: hardness and approximation
A meticulous description of a real network with respect to its heterogeneous physical infrastructure and properties is necessary for network design...
-
-
Counting on Rainbow k-Connections
For an undirected graph imbued with an edge coloring, a rainbow path (resp. proper path) between a pair of vertices corresponds to a simple path in...
-
An intractability result for the vertex 3-colourability problem
The vertex 3-colourability problem is to decide whether the vertex set of a given graph can be split into three subsets of pairwise non-adjacent...
-
On a Countable Family of Boundary Graph Classes for the Dominating Set Problem
AbstractA hereditary class is a set of simple graphs closed under deletion of vertices; every such class is defined by the set of its minimal...
-
Limiting the Search in Brute Force Method for Subsets Detection
A set of methods for limiting the complete enumeration of the number of combinations...
-
Degree sequence optimization in bounded treewidth
We consider the problem of finding a subgraph of a given graph which minimizes the sum of given functions at vertices evaluated at their subgraph...
-
The Algorithmic Complexity of the Paired Matching Problem
We introduce a new matching problem originating from industry called the Paired Matching problem. The objective in the problem is to find a maximum...
-
On the oriented diameter of planar triangulations
The diameter of an undirected or a directed graph is defined to be the maximum shortest path distance over all pairs of vertices in the graph. Given...
-
The Hamiltonicity and Hamiltonian-connectivity of Solid Supergrid Graphs
The Hamiltonian path and cycle problems are well-known NP-complete problems. A given graph is Hamiltonian-connected if there exists a Hamiltonian...
-
Domination and its variants in split graphs -P versus NPC dichotomy
We investigate the complexity of minimum total outer-connected domination in split graphs. Given a connected graph G , a minimum total outer-connected...
-
Computational Complexity of Covering Colored Mixed Multigraphs with Degree Partition Equivalence Classes of Size at Most Two (Extended Abstract)
The notion of graph covers (also referred to as locally bijective homomorphisms) plays an important role in topological graph theory and has found...