Is It Really NP-Hard to Survive in Big-Data?

Prof. Vadim E. Levit
Israel, Department of Computer Science and Mathematics, Ariel University
In order to survive, even in Big Data, one needs a hope. For example,
in computability theory the Church thesis serves us for railing, when it claims informally that a function is computable if and only if it may by programmed in a Turing all-in-one computer. Our thesis reads as follows: “Every intractable problem has its tractable counterpart.” Being more specific, we hint that a reasonable variation of an objective function makes it efficiently computable. On the other hand, we may consider to keep the same objective function and slightly change the data.
In what follows, the protagonist is a maximum independent set of a graph. It may equivalently appear, in the context of our research, as a maximum clique or even a biclique. See, for instance, the maximum vertex biclique problem versus the maximum edge biclique problem. The former can be solved in polynomial time, while the latter is known to be NP-hard [6, 11].
As a primary example of the objective functions exchange we choose the case, when critical independent sets come instead of maximum independent sets.
A set S ⊆ V (G) is independent if no two vertices from S are adjacent,
and by Ind(G) we mean the family of all the independent sets of G. An independent set of maximum size is a maximum independent set of G, and ∝(G) = max{|S| : S ∈ Ind(G)}.
For X⊆V(G), the number|X|—|N(X)|is the difference of X, denoted d(X). The critical difference d (G ) is max {d (X ) : X ⊆ V (G )}. The number max{d (I ) : I ∈ Ind(G )} is the critical independence difference of G, denoted id(G). It is shown in [13] that d(G) and id(G) coincide for every graph G. If A is an independent set in G with d(X) = id(G), then A is a critical independent set [13].
It is known that computing ∝(G) is an NP-hard problem [3]. Each critical independent set is included in some maximum independent set [1]. A critical independent set of maximum size can be found in polynomial time [5].
When our purpose is to modify the data, we invest heavily in König- Egerváry graphs.
A matching is a set M of pairwise non-incident edges of G. A matching
of maximum size, denoted μ(G), is a maximum matching. Recall that if ∝(G ) + μ (G ) =|V (G )|, then G is a König-Egerváry graph [2, 12]. In accord- ance with the celebrated König-Egerváry theorem, each bipartite graph
is a König-Egerváry graph as well. Various properties of König-Egerváry graphs can be found in [4, 8, 9, 10]. Let us also mention that the equality d(G) =∝(G)−μ(G) holds for each König-Egerváry graphG [7].
References
  1. S. Butenko, S. Trukhanov, Using critical sets to solve the maximum independent set problem, Operations Research Letters 35 (2007) 519-524.
  1. R. W. Deming, Independence numbers of graphs - an extension of the
König-Egerváry theorem, Discrete Mathematics 27 (1979) 23-33.
  1. M. Garey, D. Johnson, Computers and intractability, W. H. Freeman and
Company, New York, 1979.
  1. E. Korach, T. Nguyen, B. Peis, Subgraph characterization of red/ blue-split graphs and König-Egerváry graphs, in: Proceedings of the Seventeenth Annual ACM–SIAM Symposium on Discrete Algorithms, ACM Press, 2006, 842–850.
  1. C. E. Larson, A note on critical independence reductions, Bulletin of the Institute of Combinatorics and its Applications 5 (2007) 34-46.
  1. V. E. Levit, An algorithm for nding a maximal perimeter submatrix containing only ones in a zero-one matrix, in the book: «Systems for Transmission and Processing of Data», Vol. 1, Institute for Problems of Information Transmission Science Press, Moscow (1988) 42-45.
  1. V. E. Levit, E. Mandrescu, Critical independent sets and König-Egerváry graphs, Graphs and Combinatorics 28 (2012) 243-250.
  1. V. E. Levit, E. Mandrescu, Critical sets in bipartite graphs, Annals of Combinatorics 17 (2013) 543-548.
  1. V. E. Levit, E. Mandrescu, On maximum matchings in König-Egerváry graphs, Discrete Applied Mathematics 161 (2013) 1635-1638.
  1. V. E. Levit, E. Mandrescu, A set and collection lemma, The Electronic Journal of Combinatorics 21 (2014) #P1.40.
  1. R. Peeters, The maximum edge biclique problem is NP-complete, Discrete Applied Mathematics 131 (2003) 651-654.
  1. F. Sterboul, A characterization of the graphs in which the transversal number equals the matching number, Journal of Combinatorial Theory B 27 (1979) 228-229.
  1. C. Q. Zhang, Finding critical independent sets and critical vertex subsets are polynomial problems, SIAM Journal on Discrete Mathematics 3 (1990) 431-438.