4 votes
Accepted

Name of graph family defined by modular sum

Your graph class is the class of graphs that are a disjoint union of a clique and a bunch of bicliques, possibly singletons. We can safely assume that the labels $\ell(v) \in [0,T)$, and it is then ...
Pål GD's user avatar
  • 16.1k
4 votes
Accepted

Finding a minimum cut with an upper bound on the set sizes

The problem is called Component Order edge-Connectivity. The edge here refers to deletion of edges. See e.g. Gross et al.. The problem is defined as follows. Given an undirected graph $G = (V, E)$ ...
Pål GD's user avatar
  • 16.1k
3 votes
Accepted

On hardness of finding total dominating sets in triangle-free graphs

The problem is indeed $\mathsf{NP}$-hard on bipartite graphs (which are triangle-tree) of degree at most $3$. See Theorem 6 of this paper.
Inuyasha Yagami's user avatar
2 votes

Seeking a reference for NP-hardness of optimization problems

In my opinion, monographs on approximation algorithms come closest to what you are seeking: Complexity and Approximation, by Giorgio Ausiello et al. Approximation Algorithms, by Vijay Vazirani, The ...
Vincenzo's user avatar
  • 3,302
2 votes
Accepted

Compiler optimization pass joining identical function definitions together (or specializing them)

There's no reason why this can't be thought of as common subexpression elimination, except of course that it's made trickier by requiring some kind of $\alpha$-renaming. Another way to think of this ...
Pseudonym's user avatar
  • 22.1k
2 votes

Resources on Tree Automata Regular Expressions

Here is a master's thesis and an arXiv paper on the topic, which contains some examples.
codeR's user avatar
  • 565
2 votes
Accepted

A pedagogic review on the advantage/drewbacks of distributed computing

Some basic pros and cons are outlined here. There are multiple books on the topic as well e.g. Kshemkalyani, A. D., Singhal, M. (2011). Distributed Computing: Principles, Algorithms, and Systems. (n....
codeR's user avatar
  • 565
1 vote

A pedagogic review on the advantage/drewbacks of distributed computing

Laslie Lamport is very influential in the field of distributed computation, here is his quote: "A distributed system is one in which the failure of a computer you didn't even know existed can ...
math boy's user avatar
  • 353
1 vote
Accepted

NP-hardness of partitioning into k sets

The reduction is simple, so you might not require a reference. Given an instance for $k = 2$, simply add $p$ integers each of value $SUM/2$, where $SUM$ is the sum of all the elements in multiset $S$. ...
Inuyasha Yagami's user avatar
1 vote
Accepted

How to Prepare for Informatics Olympiad and ACM-ICPC?

I believe that a good starting point is the following list compiled by Codechef: https://www.codechef.com/certification/data-structures-and-algorithms/prepare It contains resources and problems for ...
mstou's user avatar
  • 26
1 vote

Is there any computation formalism based on general relativity?

The reason quantum computing is useful is not (just) that the problems in QM are applicable to problems that'd we'd like to solve in computing generally, but because we can physically realize setups ...
redroid's user avatar
  • 143
1 vote
Accepted

Division of Large Numbers with Known Factors

Here is a suggestion for an algorithm that might satisfy your constraints. First, we'll come up with an upper bound $M$ for the quotient $a_1a_2\dots a_n/b_1b_2\dots b_m$. There are many acceptable ...
jschnei's user avatar
  • 364
1 vote

Memory efficient undo data structure

Yes. A relevant technical term is 'persistent data structure'. (See also persistent-data-structure.) There are many techniques for building persistent versions of standard data structures (trees, ...
D.W.'s user avatar
  • 159k
1 vote

Estimating the number of elements shared in two sets using a random sample

The MinHash algorithm is precisely the HyperLogLog-style probabilistic algorithm for approximating the cardinality of the intersection of multiple sets you're looking for.
orlp's user avatar
  • 13.4k
1 vote
Accepted

Looking for all "valid" combinations taken from a set of things, where subsets of "valid" things are always "valid"

This can be formulated as finding all minimal subsets for a monotone function. Here monotone captures your property about supersets and subsets. Or, this can be formulated exact interactive learning ...
D.W.'s user avatar
  • 159k
1 vote
Accepted

On hardness of finding dominating sets in triangle-free regular graphs

We show that the minimum dominating set (MDS) problem is $\mathsf{NP}$-hard on $3$-regular triangle-free graphs. We show this by a reduction from the bipartite graphs of maximum degree $3$. The MDS ...
Inuyasha Yagami's user avatar
1 vote

Introduction to theoretical computer science for research mathematicians

You could look at semantics of programming languages textbooks that rely on category theory. For instance: Check out the books advised [here][1]. This is part of theoretical computer science. Dana ...
ExpressionCoder's user avatar
1 vote
Accepted

Does Sipser's _Introduction to the Theory of Computation_ cover the Chomsky hierarchy?

No, Sipser's textbook does not cover Chomsky hierarchy, a containment hierarchy of different classes of formal grammars. Nor does it cover that hierarchy with a different name. In fact, the book does ...
John L.'s user avatar
  • 39k

Only top scored, non community-wiki answers of a minimum length are eligible